Code VS Reborn で作ったAI「Glico」

予選7位(繰り上がり6位)通過で決勝進出🎉

特徴

  • AI
    • Javaで書いた
    • 2ステップのAI。連鎖探索&使う連鎖の決定
    • 線形回帰による評価関数のパラメータチューニング
    • 連鎖のタイミングの決定を同時手番ゲームに帰着してそれっぽい解を求める
  • AI以外
    • クローンクライアント上でのローカル対戦
    • 読みやすいログの生成

シミュレーション

しんどい。
データでは行ごとにlongで押し込む。
シミュレーションするときには一旦byteの1次元配列にコピーする。
シミュレーションでは不要な列を更新しない工夫をした。

連鎖の探索

連鎖の抽出

盤面から最大連鎖数を見つけてそれを評価関数に使うのは大連鎖を作るAIにとってほぼ必須になっている。
前回は1-9のブロックを落とす方法を使ったが、今回は色々試した結果ブロックを削除することにした。また、普通なら消えるはずのないある程度高いブロック(3マス程度)も削除の対象にした。

探索手法とテクニック

ビームスタックサーチ(Chokudaiサーチ)を使った。
重複消去(ローリングハッシュ)
大きな連鎖(10+ お邪魔)が見つかったらそのノードは展開しない(葉になる)

探索のスケジューリング

1ターン目は必ず "4 0" を出力する。1ターン目を固定してもそこまで連鎖力が変化しない(自分調べ)のでそうした。オンライン対戦では入力待ちの間も探索している。
2ターン目や攻撃した/されたターンでは、深さ20、時間11秒で探索をする。
それ以降のターンでは、ターン毎に思考時間を半分にして、かつ深さは前のターンに見つかった連鎖を基準に下げていく。最小値は100msにした。

なぜ毎ターン一定深さ・時間で探索しなかったのか?開発過程での変化を挙げると

  1. 毎ターン一定深さで探索すると、発火ノードを展開しない探索との兼ね合いで、発火ターンが近い時に大きすぎる連鎖を探してしまい無駄が多い。そこで十分大きい連鎖がある深さで探索の打ち切りをする工夫を入れた。
  2. 深さを可変にすると、毎ターン同じ時間で探索するのはおかしいので、深さに比例する時間で探索するようにした。
  3. 深さに比例する時間で探索すると、探索時間が連鎖にかかるターンの2乗に比例してしまうので、時間を見積もりやすい指数関数的にした。探索木を保存するような変更をその前にしていたので、深い部分で探索時間が短くてもちゃんと連鎖にたどり着けた。

評価関数

あるブロックの周りの24マスにどのブロックがあるか?の特徴量を作って、前回のCode VS for Studentと似た方法で線形回帰をして評価関数を作った。
その特徴量は1と9のペアと2と8のペアのようなものを同一視していなかったので、どう考えても無駄なんだけどなんか圧縮しようとしたら性能が落ちたのでやめた。何かがおかしいかもしれない。

連鎖の選択

枝刈りした発火木

連鎖の探索結果を発火木と呼ぶことにする。発火木では葉ノードが大連鎖に対応し、その他のノードは大連鎖を作る過程に対応する。
前者を発火ノード、後者を伸ばしノードと呼ぶ。
発火木から「良い発火ノード」のみを残すように枝刈りして、木を小さくする。「良い発火ノード」とは、しきい値以上の火力であり、同じ深さで最も火力が高いようなノードである。

2つの発火木のゲーム

自分および相手の枝刈りした発火木を作り、それらの木を使って別のゲームをすることを考える。

各頂点に実数が書かれた根付き木A,Bが与えられる。AliceとBobは2人でゲームをする。Aliceは木Aの根から、Bobは木Bの根からスタートする。
各ターン、AliceとBobは同時に子のうちの一つに移動する。移動後どちら一方が葉に到達したとき、ゲームを終了する。ゲームが終了したときに居る頂点のスコアの差をAliceは最大化、Bobは最小化しようとする。
AliceとBobが最適な行動を取ったとき、スコアの期待値はいくつになるか?

ここで言う最適な行動とは、ナッシュ均衡のことである。なので求めるのは期待値になる。

この問題は葉から線形計画問題再帰的に解くことでなんとかなる。これについては、やる気が出たら他の記事で解説したい。
実際にAIに搭載してあるのはもう少し複雑である。頂点には単に実数を書くのではなく、普通の盤面あるいはお邪魔が降り続ける中で3ターンシミュレーションしたときの結果から得られる特徴量を書く。またスコアの差ではなく、それら特徴量から算出される勝率を最大化する。ここはロジスティック回帰を使って勝率を算出することにした。
ここは精度が結構悪い。連鎖火力や爆破火力とスキルゲージの兼ね合いなど非線形性が強いところが多いので、その影響があると思う。

いい感じのログ

公式クライアントのリプレイ閲覧機能は所々不便なところがあったので、AIが出力したログをいい感じに再構築していい感じに見れるようにした。
f:id:piroz95:20190520204624p:plain
左から盤面、枝刈りした発火木(自分/敵)、詳細なログの順で並んでいて、何が起きたのか分かりやすい。
ちなみにこの画像はおそらく対keraさんのログで、敵盤面から大連鎖を見つけられなくてそのうち死ぬ。

AIの名前

グリコ・パイナップル・チョコレートは同時手番ゲームなので実質Code VS
あと自己対戦のときにGlicko2レーティングを使ったので

日記

長期マラソンに参加するときは日記を書いていて、まとめる気が起きたらまとめる。