Ghost in the Cell の参戦記

GhostInTheCellというCodingame内のコンテストに参加した際の記録？感想です

CodinGameとは

プログラミングの学習問題を作成、掲載しているフランスのサイトです。
最近では、1~2ヶ月に一回ゲームAIのコンテストを開催してます。
(次回は4月の頭あたり)
問題やコンテストに参加する際、ブラウザ内でIDEが使えるので中々便利

Ghost in the Cell

今回のコンテストは2月26日から8日間に渡り行われました
ルールとしては、お互い1つの工場からスタートし生産したユニットを使って陣取り合戦を行うゲーム
各工場には生産力が設定されていて、制圧することによって自軍のユニットを生産できます
(その他 細かいルールとしてボムや生産力アップなどもあります)

感想

コンテストの結果は3508人中 324位でした(ランキング)。
レジェンドリーグに行きたかったけど、ゴールドのボスが倒せなかった 悔しい…

やったこととしては：

• シミュレータの実装
• そのターンに実行可能なコマンドを列挙
• 列挙したコマンドから実行可能な組み合わせをランダムで作成し20ターン先までシミュレート
• ↑の組み合わせの探索方法を完全ランダムとか焼きなまし法とか試行錯誤
• 評価関数は自軍のユニット数,自軍の生産力*50,各ユニットが相手の初期拠点にどれだけ近いかどうか　
• その他、コマンドの組み合わせの重複除去の為にZobristHashとチェック用にWeakHash

ヒューリスティックではなく 出来る限り探索でなんとかしようとした感じです  
1ターン目にコマンドをセットして、20ターン先まで見るので、複数のターンに跨がる効率的なコマンドの組み合わせが出来てなかった感がある  
(2ターン後に工場に到達するユニットを、攻撃を受けている工場に再送する…等)

あとは、距離6以上離れている工場にはユニットを送らないようにしたら劇的に強くなった  
↑ 各工場間の距離は直線距離以上に早い区間が存在して、別の工場経由なら２倍以上早くなる経路があるのを完全に考慮してなかった  
↑ これ、強くなった時に気づいておくべきだった

ソースコード

コンテストで最終コミットしたコードをgithubに上げました
nosnosnosnos/GhostInTheCell