A Code of Ice & Fire 参加記
問題概要
CodinGameのA Code of Ice & Fireというコンテストに参加しました。
ゲームの雰囲気は以下のリンク参照↓
ユニットを生産、移動して多くのマスを確保する陣取りゲームです。先に敵の拠点を攻撃したほうの勝ちです。
結果
世界６位（日本１位）
最終提出プログラムの内容
１．戦略
・序盤はとにかく陣地をたくさん確保する。
その際、敵陣に近い方向へ優先して移動する。
・中盤は陣地がたくさんとれる場合はとり、あまりとれない場合はGoldを貯める
・終盤は陣地よりもGoldを貯めることを優先し、
連続ユニット生産で敵本陣(HQ)を直接攻撃することを狙う
２．アルゴリズム
敵HQを攻撃できる場合
攻撃します。びゅぅうううーーーんっ！（TRAIN TRAINの音）
敵HQを攻撃できない場合
自分の行動を焼き鈍しで決定しました。敵の行動シミュレーションは無し。
（ただし、後述の敵の攻撃範囲計算はしています。）
まず自分のターンを『移動』と『ユニット生産とタワー設置』の２つのフェーズに分け、それぞれ焼き鈍ししました。最初の10msで移動について焼き鈍しをして、残り時間で生産と設置について焼き鈍しをしました。評価関数は両方とも同じものを使用しました。
当初は移動と生産・設置の連携を狙って全て同時に焼き鈍していましたが、微妙だったので分けてみたら強くなりました。状態空間が広すぎたのかもしれません。
ちなみにこの逆の手順『ユニット生産してから移動』が役に立つ場面も一応存在していて、ユニット生産で敵陣を切ってタワーを無効化してからそのタワーに守られていたセルに移動する、という強い行動パターンがありますが、あまり頻出する場面でもないので無視してもさほど問題なかったと思います。
焼き鈍しの状態遷移
移動の状態遷移は
・ユニット[i]とユニット[j]の移動順を入れ替える
・ユニット[i]の移動方向をランダムに変化させる
の２種類です。移動が成功するかどうかは考えておらず壁方向とかにも移動させようとしますが、移動が失敗したユニットはその場で静止します。
生産と設置の状態遷移は
・ユニットを自陣の外側のランダムな位置に１体生産
・ユニット生産を１つ削除
・TOWERを敵陣に近いランダムな位置に１個設置
・TOWER生産を１つ削除
ユニットやタワーの生産候補位置は状態遷移が成功する度に計算しておきました。
焼き鈍しに関してはこれだけです。実は上で説明した以外にもいろいろな状態遷移を試したけれど、あまり順位が変わらなかったので結局この内容で落ち着きました。
それよりも、今回は評価関数の調整に多くの時間を使いました。
３．評価関数
評価関数に時間を使ったとは言っても実装したものがハズレ方針ばかりだったので結局採用した評価値はあまり多くないです。
評価値
① 確保セル数(自分-相手) + Gold係数 × 所持Gold(自分-相手)（大きいほうがよい）
② 自分の確保セルのうち、相手が次のターンにユニットを生産することで
取られる可能性のあるセル数（小さいほうが良い）
③ 自分のユニットの自陣外への距離(自分-相手)（小さいほうが良い）
④ 自分のユニットの敵HQへの距離(自分-相手)（小さいほうが良い）
(自分-相手)と書いてあるところは、（自分の評価値 - 相手の評価値）を計算します。
評価値の優先度は①+②＞③＞④です。
まず①+②を比較し、同じなら③を比較し、同じなら④を比較します。
つまり、③は①+②のタイブレーク、④は③のタイブレークとして機能します。
Gold係数
①のGold係数はゲームが進行するに従って大きくなっていく数値です。ゲーム序盤は0.01に設定していてGoldはほぼ評価されませんが、終盤は最大0.5まで上がり『１マス=２Gold』という状態になります。こうなると、Level1ユニット１体生産(=10Gold)で５マスも確保しなければ釣り合わない計算になり、よほどのことがない限りGoldを使わなくなります。中盤はGold係数=0.15とか程よい値になるようにしていて、『獲得マス数 / 消費Gold』がそこそこいい感じの行動を選択して戦ってくれます。
敵の攻撃範囲計算
②は要するに敵の攻撃範囲内に入っている自分のセルは無かったことにする、という評価です。本当はMinMaxのようにして敵の攻撃を何パターンも試したいけれど、それでは時間がかかりすぎるので敵の攻撃可能範囲内の全てを取られることにしてしまって計算時間を節約しています。この評価を入れたことで被害が最小になるようにTOWERを建てるようになったので、たぶんうまく機能してます。
ちなみに敵の攻撃範囲は敵HQからダイクストラ法をすると求まります。『ダイクストラ法で使用する１マスの移動コスト』=『そのセルに生産できるユニットのうち、最も安い生産コスト』です。ただし、敵陣内の移動コストは0とします。
気をつける点としては『４近傍に味方がいる場合はその味方を移動させれば良いのでコストは０』とか『敵タワーを通過した後は（敵タワーは壊れているので）Level1ユニットで良い』とかありますが、この辺はまぁゆっくり冷静に考えれば分かります。
ちなみにこの計算は敵HQを直接攻撃する際の経路計算と同じです。
③と④について
③は自陣の中の方に残ってしまったユニットが陣地拡大のために外に向かうようにするための評価値です。
④は序盤に陣地確保する際に敵陣方向へ優先的に進むようにするための評価値です。
４．弱点
敵の攻撃範囲計算のときにエリアの切断を検知していないので、自HQ付近の陣地をぶった切りされる攻撃を検知できずに負けるパターンが目立ちます。なので連結性更新をしてみたんですが弱くなってしまって、バグってたのか計算時間かかりすぎだったのか、謎です。
感想
このゲームを見たとき最初に思ったのが『CodeVS4.0に似てる』で『そういえばGrunを作った人が懇親会かなんかのときに焼き鈍しって言ってたな…』というのを思い出し、焼き鈍しを実装してみました。頭の片隅に辛うじて残っていた記憶が、思いもよらぬところで役に立つもんだなぁ…と少し感慨深いものがありました。
私の所感では『対戦ゲームで焼き鈍しって使えるの？なんか微妙そう』という感じだったので、充分通用する場合もあるということが分かり１つ良い経験になりました。
ちなみに今回のコンテストで通算５回目の日本一位でした。嬉しい！
