シミュレーションRPG 敵AIを（非）線形計画法で

この数日　線形計画法の本を読んでたのだけれど、シミュレーションRPGの敵AIに使えないかなーー、という思いつき（だけ）のメモ。

最近の遊んでないのでわからないけど、昔みたいなターン制のシミュレーションRPGの敵モンスターのAIについて考えてみた。

線形計画法（シンプレックス法など）で解くとしてと思ったのだけれど、目的関数に敵味方の座標の差の絶対値が入ってる＝２次の項になるし、いろいろと非線形だから、線形計画法とは違うかも

目的関数としては

• 全敵モンスターが全プレイヤーキャラに与える攻撃の合計を最大化
• 全敵モンスターが全プレイヤーキャラから受けるダメージの合計を最小化
• ダメージが大きくても、それ以上に攻撃力があがればそれを評価

実際には、両方のピークが一致しないだろうけれど、そのへんも適当に合算してひとつのスカラの評価値にするとして。

なのですが、もう少し具体的には

• 攻撃力の計算は、敵モンスターとプレイヤーキャラとの距離(の反比例)から推定
• キャラが近づくほど、大きな攻撃を与える「機会が上昇する」と考える（次のターンでは射程外でも、さらに次のターンでは攻撃できるから）
• 離れるほど大きなダメージを受ける「機会が上昇する」
• ターン制なので、プレイヤーキャラの位置は固定（定数）

こう考えると、最大化したい全攻撃、　最小化したい全ダメージは、　敵モンスターの位置によって一意に決定される「連続な関数」となります。

そう考えると、　なんとなく線形計画法が使えそうな気がしてくる気がします（気がするだけかもしれませんが）*1

制約条件としては

• 移動可能な範囲　（敵キャラの移動力）

あとは、、、、何かな（汗

で、まずは線形計画法で敵モンスターのざっくりした位置を仮決定、そこから数歩以内で一番条件が良さそうなところに最終的に決定。

上の計算では連続な評価関数を想定しましたが、　実際のターン制のシミュレーションRPGだと、一歩違うと結構攻撃／ダメージの値が大きく違うので。

実際に計算してみると

Ａ
				Ｃ
					Ｂ
							Ｄ

キャラ	攻撃力	防御力	X	Y
敵A	7	7	1	1
敵B	7	7	6	6
味方C	8	3	5	5
味方D	15	6	8	8

敵から味方への攻撃を、現在位置で計算してみると
今回はシンプルに
（攻撃力-防御力）/(abs(X1-X2)+abs(Y1-y2))

攻撃	C	D
A	(7-3)/(4+4)=0.50	(7-6)/(7+7)=0.07
B	(7-3)/(1+1)=2.00	(7-6)/(2+2)=0.25

同じ攻撃力、防御力ですが、C Dと離れてるA よりも、近いBのほうが値が大きくなります

次に、敵が味方から受けるダメージを計算すると

ダメージ	C	D
A	(8-7)/(4+4)=0.125	(15-7)/(7+7)=0.57
B	(8-7)/(1+1)=0.50	(15-7)/(2+2)=2.00

味方から離れてるAよりも、C Dに近く、はさまれているBのほうが断然大きくなっています　

（このぐらいの規模だと全マスについてしらみつぶしに調べてもよさげですが）

と、前進推定よりは　比較的単純なアプローチで、よさげな行動を選択できそうな　そうでもないような。。。

まあ、実装してみないとなんとも言えないのだけれど、すぐにやる時間なさそうなのでメモのみ

*1:フィールドに地形があるので、リニアでない空間だからダメかもしれない