1. はじめに
これはチームラボ株式会社・株式会社リクルートが主催するプログラミング大会であるCODE VSの参戦記事です。
2. 競技内容
2人対戦型の落ち物パズルゲームのAIを作成し、参加者同士でオンライン対戦を行います。
以下はゲームのルール詳細(PDF)からの引用です。
ゲームの目的
このゲームは、フィールドの一定の高さまでブロックを積み上げないようにしながら、相手のフィールドをブロックでいっぱいにするゲームです。ブロックは条件を満たすと消えます。消えたときの条件次第では相手に消えないブロックが送られ、妨害できます。うまくブロックを積み上げ消すことで、相手より長く生存することを目指しましょう。
ゲームの画面
対戦動画
NormalAIに100-0したし、オンライン参戦しよう pic.twitter.com/6DI9TdomCq
— ブロコロン (@burokoron_) 2019年4月21日
3. PythonでCODE VSに参戦する
CODE VSのJavaアプリ上でPythonで上手く実行できなかったので、
その解決方法をここに記述します。
動作環境
- Windows 10
- Python3.6 (Anaconda)
最近であれば、おそらくたいていの人はAnacondaを使用してPythonをインストールしていると思います。その場合、PythonはAnacondaの仮想環境上にしか入っていないため、普通にjnlpを起動すると、pythonコマンドが使えずにエラーになります。
Anacondaの仮想環境上でjnlpを起動すれば問題なくpythonコマンドを使用できます。
4. AIを作る
ソースコードはGithubにアップロードしています。
4.1. 戦略方針
このゲームに勝つには相手に大量のプロックを送り付けなければいけないわけですが、主な戦略方針として、
- 大連鎖をする
- スキルを使用する
2種類が考えられます。
大連鎖をするには高度な探索技術が必要なので、今回はスキルを使用してブロックを大量生成を狙う通称ボマーを選択しました。
4.2. 探索
探索はビームサーチを使用しました。
ビームサーチは基本的には幅優先探索ですが、各階層のノードのうち評価値が上位N個のみ探索を継続し、残りは枝刈りする探索手法です。深くまで探索したいが、探索空間が広いときにしばしば用いられます。ただし、評価関数の精度がとても重要になります。
探索は自分のフィールドだけ探索して、相手のフィールドは完全に無視しました。今回は幅10、深さ4でビームサーチしました。(ビームサーチの意味がない気はしなくはないが、深さ2の全探索よりは強かった。)
さすがに探索できてなさすぎるので、今日から使えないビット演算（CODE VS Reborn編）などを参考に高速化とか頑張りたいですね。(そもそもpythonを使うべきじゃなかったということには目をそらしつつ……)
4.3. 評価関数
全探索できないゲーム＆探索量がかなり少ないので評価関数の精度はとても重要です。
評価は以下の要素を考慮しました。上に書かれている要素ほど重要視しました。
-
プラス評価
- 数字ブロックを消した(スキルを上昇させるため)
- 5ブロック(ボム)がある(これがないと何もできない)
- 数字ブロックがある(スキルを効率良く使用するため)
-
マイナス評価
- ブロックの高さが一定値を超えた(ゲームオーバーなので……)
- 最もブロック積みあがった列と最もブロックが積まれてない列に差がある(事故死を防ぐため)
- フィールドの任意の3×3の領域において5ブロック(ボム)の数が2個以上ある(スキル使用の効率が落ちるため)
- 5ブロック(ボム)の周りに数字ブロックがない(スキル使用の効率が落ちるため)
- 座標(x, y)と座標(x+1, y+2)のような位置関係にある数字ブロックの合計が10(連鎖が起きにくくするため)
4.4. スキルの使用
5ブロック(ボム)を爆発させるタイミングは相手がブロックを相殺しなかったら、負けになるブロック量を送り込めるときとしました。ちなみに評価関数の評価値でだいたい送り込めるブロック量がわかったので正確な爆発スコアを計算せずに、評価値でブロック量を推定しました。(爆発スコアを計算するのがめんどくさかっただけ)
5. 結果
最終的な予選結果は48位でした。ゴールデンウイーク前の時点では25～30位くらいをうろうろしてたのですが、ゴールデンウイークでずるずると順位が落ちていき、諸事情によりAIも改良できず……といった感じでした。
CODE VS 5.0では38位だったので、このときより順位を上げたかったのですが、叶いませんでした。もし次回大会があればもっと実力を上げて挑みたいを思います。