COVE VS Reborn 参加記録

ゲームAIコンテスト「CODE VS Reborn」に参加し、予選6位、決勝3位でした。

https://codevs.jp/

決勝提出版アルゴリズム概要

カウンターを狙うため発火点を高めに構えた状態を維持しながら連鎖を延ばす。連鎖の探索はビームサーチ。左から2列目にお邪魔4つと1から9の数字ブロックをそれぞれ落としたとき発生する連鎖数を評価関数に含めた。

18ターン目まで考える。最初はビーム幅4000くらい。最後の数ターンはビーム幅100くらいまで減らす。こうすることで、早い段階でのつぶしに強くなる。なぜなら、ビーム幅が広いと、「一時的に連鎖数が伸びていないが最終的に連鎖数を最大化できる」ような手を選んでしまい、連鎖数が伸びていないタイミングで相手に発火されるたときカウンターで返せる連鎖を作れなくなってしまうから。ビーム幅をあえて狭めることで、常にそこそこの連鎖数を維持しながら伸ばせるルートを見つける。

18ターン目に近づいたら、「2ターン先まで全探索、3ターン先からビーム幅100で5ターン先まで読む」に切り替える。相手が自分に合わせて連鎖をどんどん伸ばしてきたときにも対応できるようにした。

自分の解答にオリジナリティーがあるとしたら、ビーム幅をわざと狭めることでカウンタ―成功率を上げている点だと思う。相手の盤面を見る手を変えるなど、調整に時間がかかりそうなことをせずに決勝に行けたのは良かった。

経緯

最初と最後で5日ずつくらいしか時間がとれなかったので、いかにコスパの良い戦略を取るかが重要でした。最初の5日間で探索部分をほぼ完成させて、最後の5日間で戦略的な部分を頑張るという方針にしました。

残り5日の時点で上位陣の対戦記録を見ると、keraさんが明確なカウンター戦術を成功させており、僕も真似することにしました。すでに作ってある評価関数は、各位置に数字ブロックを落としたときの連鎖数を見ていたのですが、落ちる位置をnつ上にずらすだけでそれなりにカウンターの動作をするようになりました。

この時点で30位くらいまで落ちていたのですが、上記の変更を加えるだけで一気に13位あたりまで戻りました。

その後はひたすら自己対戦でパラメータ調整を行い、運よく予選6位に滑り込みました。

時間がなかったこともあり、ビット演算や並列化による高速化、相手の盤面を見て手を変えるなど、実装や調整のコストが大きそうなことには全く手を付けられませんでした。それでも予選通過できたのは、カウンター戦術を取り入れることができたことが多いと思います。

決勝では初撃の連鎖数をみんな大きくしてくるだろうという読みから、より大きな連鎖に対してもカウンターをできるよう、より受け身になりました。それ以外は特に変更してません。

決勝で学んだこと

評価関数にも人ごとに少しずつ差異があって面白かった。評価関数として8近傍に空白があるブロックを消してみたときの連鎖数を見ている人が多かったなか、tanzakuさんはすべてのブロックを消してみたときの連鎖数を見るということをしたらしい。これで一度発火点を埋めてから連鎖を延ばすみたいなパターンを検知できるらしい。また、ケイマ、大ゲイマの位置関係に消滅するブロックの対があるかパターンマッチを評価関数に入れている人が多かったが、keraさんは縦の段差をすべて見ている。

どのように連鎖力を評価するかという点も話に挙がった。僕は時間がなくて自己対戦でしか評価していなかったが、これは良くない。例えばビーム幅を増やすと連鎖力は上がるかもしれないが、カウンター発火の成功率は低くなる。連鎖力は連鎖力として量るべきだろう。ターン数固定でできる連鎖数を評価基準にしている人が多かった。また、y.sさんなどは、ツモを実際の試合からサンプリングしたようだ。公式の記述とは異なる分布から生成されているらしく、割と性能評価に影響があるらしい。

予選でサーバーを借りてやっている人、どうやってクライアントを動かしているんだと思っていたけど、ローカルでクライアントを立ち上げて、実行コマンドのところでsshすればよいというのをnyashikiさんに教わった。言われてみれば当たり前だけど全然気づかなかった。