Ocean of Code 参加記 - ヴァルの開発記

f:id:ValGrowth:20200424234743p:plain — Ocean of Code

問題概要

CodinGameのOcean of Codeというコンテストに参加しました。

ゲームの雰囲気は以下のリンク参照↓

潜水艦１隻を操作し、魚雷や機雷を使って敵の潜水艦を攻撃してLIFEを0にすれば勝ち。敵の居場所は自分からは見えないがどんな行動をとったかは毎ターン分かるので、その情報を元に敵の位置の推定が必要な不完全情報ゲームです。

結果

世界３位（日本１位）

ゲームについて考察

このゲームは複数の要素が絡んでいて考えることが多いです。具体的には

・機雷を使った陣取り合戦。自陣が広いほうが長生きでき有利になる。以下の試合が分かりやすい例です。

・上手な移動。動けるマスが無くなるとダメージを受けてしまうので、できるだけ隙間なく移動したほうがよい。しかし、あまりにも隙間なくきっちり移動してしまうと自分の位置がバレやすいので、バレにくいようにもしないといけない。

・魚雷での攻撃。ある程度敵の位置が分かってきたら魚雷を撃ちたくなるが、撃つと自分の位置が絞られて反撃を受ける可能性があるため先に攻撃を仕掛ける判断が難しい。

これらのバランスが重要で、機雷を上手く散りばめつつ、敵にバレないようにかつ移動可能なマスを確保しつつ移動し、攻撃しつつ相手の攻撃は避ける、というかなりの職人技が要求されるゲームになっています。

有効だった戦略一覧

やってみて有効だった戦略を大雑把に箇条書きします。

１．敵位置予測

・敵の移動方向から逆算する（島や画面外やすでに通った経路には移動できない）

・敵魚雷の着弾座標から逆算する

・自分が与えたダメージから逆算する（敵の自爆も考慮する）

・機雷の起爆から逆算して、起爆した座標に機雷を仕掛けることが出来る経路のみに絞る

２．スキルの有効活用

・TORPEDOやSILENCEを無駄撃ちしない、交戦に備えて残しておく

・MINEを撒くが、あまり詰めて置かない

３．移動

・自分が敵からどう見えているかも考えて、あまり位置が絞られないように移動する

・残りマス数も考慮するが、あまり重要ではない。ただし狭い場所に入り込むのはよくない。

４．未来に発生するダメージを考慮

・敵の機雷は避ける（次のターンに起爆される可能性がある場合）

・敵が次のターンに魚雷を撃ってくるか、敵の目線で考える

・敵が避けれない位置に機雷を置く

５．敵位置の予想

・敵の移動経路が妥当かどうか考えて、敵がいそうな場所を重み付けする

最終提出プログラムの内容

先に書いた方針を具体的にどのように実現したのかについて書きます。

１．アルゴリズム

MCTSを改造したものを使用しました。

Legendリーグがオープンしたぐらいまでは１手先読みの貪欲をやってて10位ぐらいでしたが、そこから伸び悩んでいたので思い切ってMCTSに拡張しました。１手先読みの性能を壊したくなかったので、上位互換になるように組みました。具体的には以下のような手順です。

①．１手先貪欲をして、最も評価値の高い行動を見つける

②．①で見つけた行動でシミュレーションをして子ノードを生成

③．①で得た評価値をルートノードまでbackupする

④．ルートノードからUCB1を使って子ノードを選んでいき、①をしていないノードに到達した場合①、②、③をする。

⑤．時間いっぱい④を繰り返す

敵の座標とpathの不確実性をどう扱うかに悩みましたが、以下のように考えました。

・①で評価値を計算するときは、プレイヤーの行動選択を模しているので、敵の位置は不確定なほうが現実的である

・②でシミュレーションするときは、ゲームの状態が遷移するのを模しているので、敵の状態は一意でなければならない

以上のことから、敵の状態を一意に決定するプロセスは②の前に行う必要があります。①で評価値計算をするときはここで決めた敵位置は使用せず、②で子ノードへの状態遷移するときのみ使用します。

ルートノードで①をした後に敵の位置を候補の中からランダムに１箇所選んで決定します。ルートノードで決定すれば子ノードもその情報を引き継げるので、ルートノード以外でこの位置決定をする必要はありません。

どの敵の状態を選択するかによってゲームの状態が変わるので、選んだ状態ごとに子ノードを作る必要があります。ルートノードから子ノードへ遷移するときに毎回敵の位置をランダム選択するので、敵の位置が絞り込めていないような状態だとルートの子ノードの数が多くなり、あまり深く探索できませんでした。（これは後述の敵状態の重み付けによって多少改善されました）

探索の深さ

探索の深さには幅があり、浅いときは（１番深いところの深さが）１～２ぐらい、深いときは20ぐらいです。スキルがいっぱい余っててお互いの位置も未確定な状態だと深さ１～２程度で、スキルを使い切って移動とTORPEDOしか使わなくなったような状態だと15～20手ぐらい読めてます（全探索ではないです、一番深いところの深さ）。

評価回数は1000～3000回ぐらいでした。速度あまり気にしてなかったので安定してないです。子ノードを展開する前の１手先貪欲はちゃんとできてました。

UCB1

UCB1の定数Cは小さめの0.01にしました。C=0にしてもあまり性能は変わらなかったので、今回はUCB1さんあまり仕事してないです。

２．行動選択

今から書く内容は、先に書いた改造MCTSの『①１手先貪欲』で１手先を列挙するときの内容です。

MOVE, TORPEDO, SILENCE

以下を全て試します。

MOVE -> TORPEDO -> SILENCE

MOVE -> SILENCE -> TORPEDO

TORPEDO -> MOVE -> SILENCE

TORPEDO -> SILENCE -> MOVE

SILENCE -> MOVE -> TORPEDO

SILENCE -> TORPEDO -> MOVE

MOVE -> SILENCE

MOVE -> TORPEDO

SILENCE -> MOVE

TORPEDO -> MOVE

MOVE

何もしない

MOVE

全方向。必要ならSURFACEする。

SILENCE

全方向、全距離。必要ならSURFACEする。

TORPEDO

与えるダメージの期待値が最も高い場所へ撃つ（ただし、期待値がしきい値(=0.6)より低い場合は撃たない）

TORPEOD -> MOVE と MOVE -> TORPEDOの大きな違い

MOVE -> TORPEDOの順で行動した場合、行動後の自分のTORPEDOチャージは０になる。もし敵がTORPEDO -> MOVEをすれば移動時にTORPEDOをチャージ出来るため敵のTORPEDOチャージは１になる。その結果相手のほうが１ターン早く次の魚雷を撃てることになり、ライフ1～2の差につながり不利になる。

逆にTORPEDO -> MOVEの順で行動した場合、次のターンの自分のTORPEDOチャージは１になる。敵もTORPEDO -> MOVEをした場合でも自分のほうが先に次の魚雷を撃つことができるため、有利である。

このため、TORPEDO -> MOVEを優先的に調べることにする。

MOVE -> TORPEDOは、移動後でないと届かない座標や、移動前に撃つと自爆になってしまう座標に対してのみ調べる。

TRIGGER, MINE, SONAR

先に挙げた全てのMOVE, SILENCE, TORPEDOの組み合わせに対して、TRIGGER、MINE、SONARの使用を考えます。

TRIGGER

TORPEDOと同様に、与えるダメージの期待値が最も高い機雷を起爆する（ただし、期待値がしきい値(=0.9)より低い場合は起爆しない）

MINE

MOVEやSILENCEの前後で置ける場所を列挙し、最も良さそうな場所へ置く。例えば、MOVE→SILENCEという行動があった場合、

MINE→MOVE→SILENCE、

MOVE→MINE→SILENCE、

MOVE→SILENCE→MINE

の３通りを考えて、最も良いものを選ぶ。MINEを置く場所は、序盤はダメージ範囲が他のMINEと被らないように置き、それができないぐらいマップがMINEで埋まってきたらどこでも置けるところに置く。

また後述の『攻撃MINE』が使える場合はそれを優先する。

攻撃MINE

敵の近くにMINEを置く技。SILENCEが溜まってない敵に重ねてMINEを置けば、次のターンに必ず１ダメージを与えることができる。敵の通ってきたpathによっては、重ねずに隣に置いても確定ダメージを与えらる場合もある。TORPEDOと同時に畳み掛けることで一気に敵のライフを削れる。うまく決まった例→https://www.codingame.com/replay/453264659?f=230

この案自体はコンテスト開始後３日ぐらいで思いついていたけど実装にこぎつけるまでに３週間ぐらいかかりました。実現出来たときは気持ちよかった。

SONAR

１つでも敵の位置候補を減らせる場合は使用する。

SKILLチャージ

チャージするスキルの優先順位は

TORPEDO > SILENCE > MINE > SONAR

の順に満タンにしていく。ただし、開幕直後はMINEを置きたいので、MINEを４つ置くまでは

MINE > TORPEDO > SILENCE > SONAR

の順にチャージする。

３．評価関数

『２．行動選択』で列挙した１手先を評価する関数。

自分のライフと敵のライフの差を基本の評価値とし、さらに以下に挙げる未来のLIFE変動を考慮します。私の経験上、分かりきっている未来のことは評価値に含めてあげたほうが良くなります。

１．次のターンに敵がTORPEDOを実行しそうなとき、それによって受けるダメージ（敵視点でダメージ期待値が最も高い撃ち方を計算し、期待値がしきい値以上なら発射するとして、そのとき自分が受けるダメージ）

２．敵の機雷によって受けるダメージ（自分の位置が15箇所程度以下に絞られている場合に限り起爆するとする）。自分が起爆するときと比べて、ダメージ期待値が低くても起爆するものとして警戒する。

３．敵が避けることができない、自分のMINEによって与えるダメージ（これにより、攻撃MINEが高く評価される）

以下の内容は直接のLIFE変動ではないですが、LIFEに換算して評価に加えます。

４．TORPEDO, SILENCEが使用可能な状態か（=LIFE0.3換算）

５．残り移動可能マス数（15*15マス=LIFE1で換算、0マスならLIFEを１失う）

６．自分の座標が敵にどのぐらい絞られているか（15*15マス=LIFE1で換算、0マスならLIFEを１失う）

４はスキルの無駄撃ちを防ぎます。TORPEDO, SILENCEは大事なスキルなので、ライフ差を0.3も生み出せないような下手な使い方はしないでね、という意味になります。

５と６は移動をいい感じにするための評価で、移動可能マス数が減らないように、かつ自分の位置が絞られないように移動してね、という意味合いです。

４．敵位置の予測

敵座標の正確な絞り込みはみんなやってると思うので省略します。それをやった後、さらにヒューリスティックに重み付けをしました。
敵座標の候補全てでFloodFillを行って移動可能な残りセル数を計算し、それが多いほど高く評価しました。また、島の４近傍や画面端を多く通っているほど高く評価しました。
ゲームの序盤ではこの予測はあまり当たらないので、ある程度位置を絞れた状態になってから使うようにしました。

ここでつけた重みは、MCTSで敵座標をランダムに決定するときや、行動選択でTORPEDOやMINEのダメージ期待値を計算するときなど使用します。