Wondev Woman

CodinGameの10日間コンテスト。↓こんな感じの二人対戦のボードゲームでした。

https://www.codingame.com/replay/243365172

世界15位/国内1位でした。

ルール

5x5～7x7の盤面を互いに行動しあって得点を稼ぐゲームです。取れる行動は「8方向いずれかに移動して8方向いずれかにブロックを生やす」「相手を押し込んで相手が元いた場所にブロックを生やす」の2種類です。

移動できるのは今いる段より1段上の高さのブロックまでです。高いところから降りる場合は何段でも降りることが出来ます。

3段目の高さまで積み上がったブロックに乗ると得点が入ります。ブロックが4段目まで積み上がると進入禁止の壁になります。

ゲーム性

なるほど3段まで積み上がったブロックに乗りまくって得点を稼ぐゲームやな！っていうのは間違いです。

相手を詰ますことができれば、その後で自分の得点はじっくり稼ぐことが出来るので、いかに相手の行動範囲を絞っていって相手を詰みまで持っていくかみたいなゲームになってます。

アルゴリズム

Minimax法(正確にはネガアルファ)を採用しました。計算時間が1秒くらいあればモンテカルロってたのですが、今回の制限時間である50msでは上手くモンテカルロる自信がなかったのでMinimaxにしました。

基本は3手読み(自分→相手→自分→評価)ですが、計算時間に余裕がありそうなら読む手数を増やしていきました。40msで160000回シミュレーションを回せたので、1手増やしてもシミュレーションの回数が160000回以下に収まりそうなら手数を増やすみたいな手法を取ってました。

評価関数

まず初手時の盤面で「開けた場所が高得点になるような影響マップ」と「相手の行動範囲を削れそうな位置なら高得点になる影響マップ」を作って、

稼いだ得点*1000
+移動可能な方向数*1000
+相手の行動を削る影響マップ点*1000
+開けた場所影響マップ点*100
+今いる高さ
-味方同士が接していたら1000点ペナルティ

みたいな感じの評価関数にしました。

影響マップは初手時の盤面じゃなくて最終手まで読んだ時点でのマップを採用したほうが正確な評価はできると思うのですが、それだと計算量が半端ないことになるので、初手時の影響マップを最終手でも流用することにしました。

影響マップ

この盤面を例にして影響マップの作り方の具体例を示してみます。

開けた場所影響マップ

まずそれぞれのマスについて8方向のうち何方向に移動できるかを出します。そして周囲3マス(ただし移動可能なマス限定)の値を足し合わせると影響マップになります。

これを	足し合わせる

削れそうな位置影響マップ

この影響マップはプレイヤーの人数分だけ生成されます。ここでは下記の赤丸のプレイヤーさん分の影響マップを作ることを考えます。

まず移動可能なマスの数を算出します。今回の例の場合は10マス移動可能です。つづいて下記の星の位置の周囲に壁を生やしたと仮定します。すると移動範囲は3マスまで減ります。

このとき星の位置の得点を10-3=7点とします。これを全マス分計算すると影響マップになります。

これが	こうじゃ

敵位置予測

今の盤面と直前の盤面を比較して、敵の位置としてありうる位置を全て算出しました。予測位置が複数ある場合は、一番評価値が高くなる場所に敵が居ると決め打ちしてMinimaxを回してました。

自作シミュレータ

さて、今回のMVPは間違いなく自作シミュレータです。

今回のパラメータ調整とか評価関数調整は自己対戦を回して強さを確認してたんですが、CodinGame上ではなくて自作のシミュレータで対戦をやってました。

CodinGame上でやるのとは速度が段違いで、数分あれば数千試合は回せるので強くなったかどうかの判定はかなり正確にできてたんじゃないかと思います。

10戦して8勝2敗くらいだったら「強くなったやん！」と思いがちですが、そのあと1000試合回すと400勝600敗とかに平気でなったりするので、強さを測るには少なくとも数百回単位で回さないとダメかなーと思います。

シミュレータの正確性の担保には「CodinGame上で自分vs自分をやって、それと同じ初期盤面で自作シミュレータを回して最終結果が同じになるかチェック」ってのをやってました。

もちろんこのシミュレータはMinimaxのシミュレータとしても使ってました。

反省

ご自慢の自作シミュレーターですが、実は終了直前まで5x5・6x6の盤面しか生成しないバグが仕込まれてました

5x5・6x6・7x7は個別でチューニングすべきだったかも

終わったコンテストで1位を取るくらいの復習をしないともう上には上がれないかも