Code Royale 参加記
ゲーム概要
CodinGameのCode Royaleというコンテストに参加しました。
クイーン１体を操作して、鉱山を採掘したり兵士を戦わせたりする１vs１のゲームです。
勝利条件は以下のいずれかです。
・敵クイーンの撃破
・400ターン経過時点で自クイーンのHPが敵クイーンより多い
２人合わせて400ターンなので１人200ターンです。
ゲームの流れとしては、
１．鉱山を建ててお金を稼ぐ
２．兵舎を建て、貯まったお金で兵士を生産
３．タワーを建てて敵兵士から身を守る
といった感じです。
結果
世界１２位（日本１位）
最終提出プログラムの内容
１．戦略
ナイトを出し続けることで敵クイーンを奥に撤退させ、その間にタワーや鉱山を建てつつ前線を上げて最終的には敵クイーンの敵HPを削るという戦略です。
ユニットにはナイトの他にアーチャーやジャイアントもいますが、扱いが難しかったので今回は使用しないことにしました。
２．戦術
開幕は前線を上げるために出来るだけ横に進み、鉱山を２つぐらい建てたらナイト兵舎を出すようにしました。あとは戦況に応じて、最寄りの空き地にタワーか鉱山を建てます。敵ナイトが近くに迫ってきたときは回避する行動をとるようにしました。また自クイーンのHPが相手より多いときも、HP有利の状態を維持したいので回避に徹するようにしました。
味方ナイトは概ね常に生産し続けるようにしましたが、お金がいっぱいあるときはある程度お金を貯めてからまとめて攻撃をしかけるようにしました。強い人たちはナイトを回避するロジックが非常にうまく出来ていて、ナイトを出してもほぼダメージを与えることは出来ませんが、ナイトがいることで相手クイーンの動きを制限することができるので、ナイトを出し続けることは結構大切です。
３．アルゴリズム
枠組みはルールベースで組みました。if (○○ and ×× and △△ and ... and □□) みたいなのが大量にある感じです。先に紹介した戦術を実現できるようにif文を並べました。
数あるルールのうち、特に効いたやつは以下の３つ
・残りゴールド0の空き地は無視する（わざわざタワー建てに行かない）。たいていフィールドの端の方にあり、戦略上無意味な場所にあることが多い
・敵兵舎がナイト生産の準備中のときは離れる
・今ある兵舎より敵に近い位置に兵舎を建てられる場合は建てる。そして敵に最も近い位置にある兵舎以外はタワーや鉱山に建て替える
敵ナイトを避ける動作はChokudaiサーチで探索しました。クイーンの行動は上下左右斜めの８方向の移動とタワーの建設(or強化)で合計９つの行動で、探索の深さは４ターン、敵クイーンは動かないものとしました。評価関数は自クイーンのHP、敵ナイトの数・HP、敵ナイトへの距離、自タワーのHPなどを適当に組み合わせました。また、建物を障害物としてうまく使いたかったので、距離計算の際に敵ナイトと自クイーンを結ぶ直線上に建物や空き地がある場合、その長さに応じて加点するようにしました。
赤線部分の長さ×２をプラス評価
これでだいたい良い感じにナイトを避けてくれるようにはなったのですが、明らかに無駄な動きもあったのでまだ改善の余地はありました（調整する時間がなかった）。
４．移動の最適化
近くの建物へ移動するとき、直線距離で移動するのではなく、途中にある障害物を避けて進む経路を考える必要があります。目的地に素早く辿り着くためには、以下の画像に示すように障害物の接線方向に向かって進むのが良さそうです。
上の画像で黒の直線は現在地と目的地の間に引いた直線で、黒の円は障害物にクイーン(の中心)が近づくことのできない範囲です。赤線はクイーンから障害物の円に対して引いた接線で、どうやらこの方向に進むのが速そうです。
クイーンは毎ターン距離60ずつ進むので、そのようにクイーンを動かすシミュレーションをします。この赤線の端に辿り着くまでは接線は変化せず、赤線の端を越えると接線が変化します。その状態が以下の画像↓
この例では分かりにくいですが接線が微妙に変化しています。このゲームではクイーンは毎ターン60ずつまっすぐ進むので、接線方向に60動かした後の場所が以下の画像
衝突が無くなったので、あとは目的地へまっすぐ進むだけです。
これを実際にやってみたときのクイーンの軌道は以下の画像↓
この場合、目的地到達までに７ターンかかっていることが分かります（クイーンの残像が８個で最初の１つは初期値のためカウントしない）
これを使って『どの建物が一番近いか』を計算することが出来ます。全ての建物と空き地に対して到着までにかかるターン数を計算し、そのターン数が最も短い場所が最近傍の建物であるということが分かります。
さらに、この円を接線方向に避ける動作は敵タワーの攻撃範囲を避けて移動するときにも使えます。例えば↓のリプレイの終盤で、敵タワーの攻撃範囲に入らない経路を算出して移動しています。（青が自分で赤が敵）
感想
コンテスト中盤は５位ぐらいにいましたが、その後探索を実装したAIがたくさん出てきてあっという間に下位に落とされてしまいました。探索が有効だと気づくのが遅すぎたのが大きな敗因だと思います。次にルールベースで組むときは、探索が有効かどうかを考えながら取り組みたい。
