AIコンテストに参加してきました。
ぼくのかんがえたさいきょうのAI
10/16に品川シーサイド楽天タワーで行われた楽天テクノロジーカンファレンス2010のイベントとして開催されたAIコンテストに参加してきました。
概要
ゲーム説明
CastleAttackというゲームのAIを作りました。
詳しいゲーム説明は公式ページのゲーム説明ドキュメントを参照
> http://www.washi.cs.waseda.ac.jp/rakuten-waseda-pc2010/question.html
図：ゲーム説明ドキュメントより
手前から時計回りに配置された赤、青、緑、黄の４チームがこの順で行動するターン制で、自分のターンには、自分の色のタイルと兵士を動かすことができます。
全員が行動したのを1フレームとし、一試合は1000フレームで行われます。
カーソル
カーソルは2x2の大きさを持っていて、位置座標と回転方向(時計回り、反時計回り)を定めることで、カーソル内の4つのタイルを時計回りまたは反時計回りに回転させることができます。
ただし、自分のタイルがカーソル内に存在しなかったり、兵士がカーソル内に存在するような位置にカーソルを持ってきても回転させることはできません。
図：ゲーム説明ドキュメントより
兵士
自分のタイルまたは、門の上を、毎ターン左右上下に１歩ずつ動くことができます。
相手の小門または大門に入ることで相手のScoreを削って自分のものにすることができます。
相手の門に入ったあと、その兵士は消滅し、自国の大門に新しい兵士が現れます。
残りフレーム数が150を切ったあと、自国から出現する兵士はスーパー兵士となり、
相手国の門に入ったときに獲得できるScoreはそれまでの2倍となります。
スコア
すべてのチームが初期スコア100を持った状態から開始します。相手の兵士に攻めこまれた国は以下に定める倍率の分のScoreを失い、攻め込んだ国がその分のScoreを得ることができます。
図：ゲーム説明ドキュメントより
結果
予選
グループ1位通過(1位4回,2位5回,3位1回)
決勝トーナメント
1回戦1位
準決勝1位
決勝(２本先取）
決勝1回戦 1位
決勝2回戦 2位
決勝3回戦 2位
というわけで、準優勝でした。やった！
優勝以外特に賞品はないみたいです。
戦略
カーソルの移動
ゲームの状況を評価する関数を作り、自分のターンに、すべてのカーソルの動かし方を試した時に最も評価値が高くなるような行動を取るようにする（いわゆる一手読み）
すべての盤面について、その盤面が自分がどれくらい有利な配置になっているかを定めることが出来れば、それが大きくなるようなものを選択していくことで自動的に理想的な形に近づく
評価の方法はいろいろあるが、自分から見た盤面位置の一つ一つにScoreを割り当て、自分の色のタイルがある位置のScoreの総和を評価関数とした。
盤面の位置にポテンシャルを持たせて高くなる方向に推移するため、アリ地獄のように勝手にタイルが集まってくる。
理想の形
左右の門と自国の門の近くはScoreが高くなるようになっている。
兵士の移動
カーソルと違ってこだわるところは少なく、基本的に相手への門が完成していれば、そこを目指すようなものを作ればよい。
詳しい仕様はソースを参照。
評価関数を使うかどうか
今回のAIではカーソルは1フレーム毎に評価をしたが、兵士AIは評価関数を使わずに、経路を保持してそれを進むようなアルゴリズムだったが、
もし、兵士の動きを評価関数で定めるとしたら、「獲得できるScoreをその門までの距離で割ったものが大きくなる方向に進む」などとすれば良いかもしれない。
先読みについて
オセロや将棋など、二人ゲームでは評価関数を先の方の手まで調べることで、より正確な強さを評価できるようになる。
今回は一手にそんなにたくさんの処理を行えないということとと、４人が行動するため先読みが難しいこと、
さらに、一手で形成がひっくり変わるオセロや将棋などと違って、形成が有利かどうかは大体線形に変化することから*1、先読みは行わなかった。
実装すれば、あと２手動かしたら経路が完成するとか、そういうのを調べたりできたかもしれない(が、時間がかかったりうまく動かないかも)。
バグ
「敵兵士のいる位置を評価対象に含めない」を実装したつもりだったが、提出したソースでは消してしまっていた。
[10/10/11 20:22:05] とこはる: 基本のできてないＡＩは負けるよ…
ごめんなさい
[10/10/15 0:17:32] とこはる: やっぱり他プレイヤーの動きをカーソルの動きに考えなかったことの被害は甚大で、優勝は無理だろう
わかったからそんな責めないで...
このバグのせいで、崩された自国のタイルを修復する時に相手の兵士のいるカーソルを選んでしまい、結局防げないままになることが多く、Uriboさんのように、相手正門に兵士ごと突撃するアルゴリズムにはめっぽう弱くなった。
あっさりと正面が崩される...。
本番で見られた動き
序盤に得点の高いチームを狙うようなアルゴリズムを持った他のチームに狙われることを防ぐために、序盤は攻撃を控えたほうが良いというのをウサギィさんが実装していた。
最初は取られた分の得点は後で取り返せば良いと考えていたけれど、決勝２回戦ではWantzが最初にScoreを取ることで他のチームに狙われることで良い形を作れなかったりしたので、
ものすごく効果を発揮していた。
この辺りも調整が難しそうなところだけれども。*2
ソース
本番で使われたものから上記のバグを修正したもの。
Wantz2.java
http://w125.sakura.ne.jp/wiki/index.php?plugin=attach&pcmd=open&file=Wantz2.java&refer=CastleAttack
