CODE VS Rebornで作ったAIの解説
目次
実行環境
ビームサーチ
盤面評価
カウンター
シミュレーターの高速化
探索の効率化
やってないこと
実行環境
機器：MacBook Pro 15 inch (2016)
言語：java
スレッド数：１
ビームサーチ
クライアント上
turn=0：深さ15、幅4200
turn!=0：深さ10~15、幅1200
１ターンで20秒を超えそうな場合（特にturn=0）は動的に幅を狭めてるので、平均すると実際の幅は上記の0.8倍くらいです。
ちなみに、サーバー上のaiは幅を25%にしてます(省メモリ化用の処理が追加されたため)
盤面評価
共通
r：一様乱数（0~0.001）
連鎖数３未満の時
c：潜在的連鎖数（後述）
p：パターンマッチ数（後述）
score = c × 0.1 + p × 0.003 + r
連鎖数３以上の時
c：連鎖数×1.04^（max深さ-今探索してる深さ）
s：黒魔術スケール（いい感じにするために25日間かけて微調整を繰り返した値）
score = c × s + r
基本的には「大連鎖したい vs 早く連鎖打ちたい」のトレードオフの調節を担っています。
潜在的連鎖
その盤面にどれくらいの連鎖能力が秘められてるのかを表したものです。潜在的連鎖の定義は、全列に全数字の1x1ブロックを落としてみてそこから発生した連鎖数のうち、落とし方の全パターンの中での最高連鎖数です。
しかし、これはとても重い処理となり探索幅数が稼げません。でもこれをサボると盤面評価の質が下がります。このトレードオフの最適解を探す必要があります。
最終的には左右の端から2列目の２箇所のみに落とすようにしました。
パターンマッチ
発火が発生しうるパターンは限定的です（下図）。これがある数が多いほどよい（潜在的連鎖が上がりやすい）盤面だと考え、以下のパターンの数だけscoreを加算してます。ちなみにk=13まで調べています。
このパターンがあるだけでは連鎖にはなりません。連鎖はこれらのパターンがいい感じに隣り合ってる必要があります。しかし、これを導入するだけで高速に大連鎖が組めるようになりました。やっぱりこのゲームはよくわかりません。
カウンター
カウンターのロマン
基本的に連鎖数はターンが経過するほど多くなります。しかし、相手に先に発火されてしまうとお邪魔ブロックだらけになってしまい自分の大連鎖が台無しになります。
しかし、うまくカウンターができれば後出しになるため、ターン数の恩恵を受けてより大連鎖を跳ね返すことができます。ロマンですね。
さらに、同連鎖数のカウンターでも恩恵があります。カウンター後、自分の盤面ではお邪魔は降りませんが、相手の盤面には振り続けます。そのターン中は相手は連鎖が組めない状態です。自分だけ連鎖が組めるターンを稼ぐことができるので、2発目を自分が優位の状態で発動できます。ロマンですね。
カウンターの実現方法
発火位置を高いとこに持っていけば実現できます。きつい崖の途中に発火点があるような状態です。
わざと高い位置で潜在的連鎖を調べる
上記の潜在的連鎖で記載した1x1ブロックを落とす位置を、実際に落下が停止する位置ではなく下に４マス開けた位置で停止するように落としました。これだけで高い発火位置を生み出すことができます。
盤面の上部の確保
いくら発火位置を４マス確保しても、デンジャーラインギリギリまでブロックを積み上げてたら１ターンも時間を稼げません。そのため、上空４マスは空けるようにペナルティを与えました。
降ってくる回数の多い数を起爆ブロックにする
せっかくカウンターを組んでも、欲しいタイミングで起爆剤が来ないとカウンターできません。それで結構やられました。
そこで、15~23ターンの間で登場回数の多い上位３つの数で発火させるようにしました。
カウンターの現実
実際やってみると色々デメリットがありました。
・連鎖の組む速度が遅くなるため、結果的に後出しの恩恵が中和
・連鎖後のゴミが多くなるため、2発目が組みにくい（山形状のゴミの上にお邪魔4段がのっかるので、食らったお邪魔数以上の被害を受ける）
シミュレーターの高速化
アルゴリズム的な面
アルゴリズムと書きましたが、特に難しいアルゴリズムを実装したわけではありません。基本的な思想は「徹底的な無駄の削除」です。ただひたすら無駄な処理をしないようにしました。
本当に様々なことをしてきましたが、これを文で紹介すると大変なことになるのでソースコードでご勘弁ください。
条件分岐の削除
条件分岐は重い処理です。ループの最も深い場所のif文を１つ減らしただけで130%の速度になったこともあります。
割り算の削除
割り算は重い処理です。ループの最も深い場所の割り算を１つ減らしただけで130%（略
割り算は主に剰余で使っていましたが、ビット演算で代用することができたので割り算を減らすことができました。
前turn時のシミュレーション結果の再利用
15ターン先まで読むので、前ターンで読んだ2~15ターン先の先読み結果は今ターンで読んでも同じです。なので、うまく保存して再利用しました。結構効果あります。
キャッシュヒット率
メモリのキャッシュ特性を考慮すると非常に高速になります。
今回の例では盤面を縦ではなく横向きでデータを扱ってました。
探索の効率化
重複盤面の削除
同じ盤面を評価する意味はありません。そして、シミュレーションは深さが進行すれば盤面数は指数関数的に増加します。すると例え同じ盤面が２つしかなくても無駄なシミュレーションが指数関数的に増えます。なので重複盤面は削除する必要があります。
が、実際のところ効果は薄かったです。微妙に強くなったかな？くらいでした。
連鎖した盤面は次の深さに持ち込まない
自分は３連鎖以上した盤面は次の深さに持ち込みません。限られた演算資源は一度発火した盤面よりまだ発火せずに連鎖を溜め込んでる盤面に当てるべきです。
全大会での知見ですが、これをするだけで途端に大連鎖するようになります。それくらい強力です。（だったと思います）
前turn時のシミュレーションで最高スコアの盤面の確約
乱数要素が多いので、前ターンのシミュレーションで得た15ターン先の良い盤面を今ターンでも引き当てる確証はありません。そのため、良い盤面に行き着くまでのコマンド列を保存し、そのコマンド列に適合した盤面はscore+=10000とすることで必ずたどり着けるようにしました。
やってないこと
相手の盤面を見る
相手の盤面を見ることで、相手が発火しそうなタイミング・連鎖数を推測することができます。それに合わせて自分の発火タイミングを早めたりなど、戦いを有利に持っていくことができます。
しかし、カウンター前提で連鎖を組んでると急に発火させることができません（経験上）。そのため、相手の発火状況がわかったところでその情報をうまく使えなかったのでやめました。
SIMD
SIMDをやれば更に高速化できるが、知識と経験が皆無で断念しました。（javaは自動でSIMD化してくれるってどこかの記事に書いてあった気がしますが...）
並列化
並列化をやれば更に高速化できますが、モチベーションが上がりませんでした。並列化を想定したコーディングをしていないため全体的な大改修が必要だったこと、サーバー提出AIは１スレッドであることが主な要因です。
しかし決勝もサーバー提出と同環境であったため、結果的には並列化に工数を当てなくてよかったように思います。
