CODE VS Reborn
2019/4/15～2019/5/10にあったゲームAIコンテスト。ぷよぷよみたいな落ち物パズルゲー。
決勝の様子(が見れる予定)：https://live.nicovideo.jp/gate/lv320076507
予選3位/112人・決勝◯位でした。
参加人数は少ないですが参加面子を考えると日本最高峰のゲームAIコンテストだったでしょう。
ルール（適当説明）
基本ぷよぷよですが、4つ揃えるんじゃなくて数字の和を10に揃えたらブロックが消えるみたいなルールです。 連鎖すると敵の盤面にお邪魔ブロックを降らせます。相殺もぷよぷよと同じ仕様です。 ぷよぷよと大きく違うのはスキルがある点です。ブロックを消すとスキルゲージが溜まって、溜まると数字の5を爆発させて連鎖したときと同じように攻撃ができます。
アルゴリズム概要
目標連鎖数を決めてchokudaiサーチで探索して、発火が近くなったら色々考える感じです。
全体フローチャート
連鎖数決定
基本12連鎖を狙います。
敵がスキル型だったら15連鎖を狙います。敵が6連鎖以上組めてなかったらスキル型と判定してます。
敵を殺せそうだったら殺せるぐらいの連鎖を狙います。例えば敵が3行のお邪魔で死ぬなら大体11連鎖(お邪魔33個)を狙う感じです。
探索
心臓部です。
探索の重要性
単純な探索では絶対に負けないようにしました。敵が先に12連鎖撃ってきてるリプレイを発見したら、最低でも同じ速度で撃てるように徹底的に改良しました。 探索で負けていてもカウンター等の戦略で勝つことはできますが、それはじゃんけんに例えると「パーを出せないからグーとチョキと戦略で勝つ」みたいな発想です。 上位層で戦うにはグーチョキパーすべてと戦略を組み合わせないと話にならないと思ったので、妥協は絶対にしないようにしました。
探索の概要
10秒間のchokudaiサーチで探索しました。初手だけ18秒です。
MAX15ターンですが予定の連鎖数が見つかったら探索を打ち切ってるので15ターンまで読むことはほぼ無いです。（言い変えると15ターン以内に連鎖が見つかるように調整した）
こういうサーチ系を強くするのに重要なのは
- 評価関数改良
- 高速化
- 探索の質を高める
ですが、評価関数はほぼ弄ってないので残り２つ中心の改良が中心でした。（評価関数を弄らないで正解だったかは不明）
評価関数
連鎖数 * 100 + ブロック数 * 0.1 - 消えたブロックの数/連鎖数 - 15行積み上げていたらペナルティ - 2ターン前から連鎖数が伸びてなかったら超ペナルティ
連鎖数は1ブロックを仮で落としてみての連鎖数です。
ブロックの落とし方ですが、最初は左端から右端まで落としてチェックしますが、1度連鎖を発見したら以降は発見ポイントから前後1マスだけ落とすように縛ってます。
高速化
多分皆やってたと思うんですが、1マスに4bitを割り当てて盤面をlong long[WIDTH]で表現して、ひたすらbit演算しました。
ざっくりすぎるのでいつもやってる高速化の手法を紹介します。これはどんなコンテストでも使える汎用的な方法です。
1. visual studioでパフォーマンスプロファイラーを起動します。
2. ボトルネックを見つけます
3. ボトルネックをカスカスになるまで高速化します。
よくある話ですがボトルネック以外は高速化してもほぼ意味がないです。
実際にどう高速化するかはtomerunさんの高速化の記事を読みましょう。 https://topcoder.g.hatena.ne.jp/tomerun/20171216
探索の質を高める
基本は「無駄な探索を排除する」です。
まずはこんなツールを作ります。
これはchokudaiサーチの中身をダンプしたものを表示するツールです。これとにらめっこして改良していきました。
主にやったこと
１．ブロックを落とす場所を連鎖群に隣接する範囲に絞る
この縛りを入れないと、離れたとこにポツンと落とすパターンが生まれるので潰しました。
２．１ターン目は落とす場所を真ん中に固定する
この縛りを入れないと、形が横にずれただけみたいなパターンが生まれがちなので縛りました。
３．重複盤面除去
ダンプした結果を見ると重複盤面がそこそこあったので排除しました。
発火間際の諸々
発火１・２手前になると諸々考えて、前倒しで発火するか普通に発火するかさらに連鎖伸ばすかを判断します。
以下が入れた処理です。カッコ内は判定タイミングです。
・カウンター警戒（連鎖発動ターン）
カウンター戦術使ってくる人が多かったので入れました。
敵にお邪魔ブロックを降らしてみた上で敵の盤面を７手読みchokudaiサーチします。 で、こっちがかました連鎖数以上のカウンターが飛んでくるようだったら、連鎖を撃っても意味ないので連鎖さらに伸ばします（目標連鎖数はそのカウンターの連鎖数）。
・目標連鎖数に達していたら発火（連鎖発動ターン）
変にバグって発火しなかったら困るのでこの処理入れました。
・対ボマー対策１（連鎖発動2手前以内）
敵があと2手でスキルゲージが溜まる状態かつ、こちらが2手以内に12連鎖以上発動できる場合は発火します。
・対ボマー対策２（連鎖発動3手以上前）
敵があと3手でスキルゲージが溜まる状態かつ、こちらが3手以内に連鎖を発動しない場合3連鎖を狙います。
・連鎖潰され対策（連鎖発動１手前）
敵が連鎖を発動させたと仮定して自分の盤面にお邪魔ブロックを降らせます。で、次のターンの自分の連鎖数が激減する場合は前倒しで連鎖を発動します。
・まだ舞える（連鎖発動ターン）
敵の盤面を2手全探索してもしょぼい連鎖(11連鎖以下)しか見つからない場合、自分の盤面を2手全探索します。で、連鎖が伸ばせるなら自分の連鎖を伸ばします。
・敵の連鎖つぶし（毎ターン）
敵が次のターンに12連鎖以上発動させることが出来る場合、ためしに自分の連鎖を発火させてみます。で、お邪魔ブロックを降らした結果、敵が2手かけても5連鎖以下しかつくれない状態になるなら連鎖を発動します。
小ネタ
死亡間際のボマームーブ
基本は足掻いてもそのまま死ぬんですが、たまーに刺さるのでやり得でした。 雑に３手呼んで、スキル攻撃力を上げつつゲージ溜め優先といった感じです。
並列化はやってない
最後２日くらいでやろうと思ったんですが、やろうと思ったときには上位キープしてたし、決勝も1スレッドだろうからまあいいかなって感じでした。
反省点
余裕で決勝で行けたのでまあ満足です。
