CODE VS for STUDENT決勝で提出したAIの解説
CODE VS for STUDENTに参加し、決勝３位を取ることができました。（嬉し悔しい）
決勝で提出したAIプログラムについて詳しく書いていきます。
（初ブログなんでたくさん記事修正してくかも）
やったことリストは以下のようになります。
・ビームサーチ
・評価関数
・盤面の選択方法
・高い評価値を記録したコマンドリストの保存
・同スコアの盤面を間引く
・発火タイミング
・高速化
ビームサーチ
ゲームAIを作るときに定番のアルゴリズムで、強くなるためにはほぼ必須のものです。
私個人的には、高さはゲームによって変わるが、幅は広く、いかに多様性のある盤面を選定することが強さにつながると理解しています。
今回のAIでは大体高さ２０、幅３００となっています。
評価関数
このゲームで強くなるには、素早く大連鎖を作ることが求められます。そのためには「連鎖がどんどん伸びてゆく」状態の時に評価値が高くなるような関数をうまく作る必要があります。
採用したのは「ブロック１つを落とし、そこから発生した連鎖スコア」です（連鎖スコア：スコア+連鎖数）。これを１〜９の全番号のブロック・盤面中の１〜１０列目の全列にやるので、合計９０回調べます。９０個の連鎖スコア中もっとも高いものを評価値に加算します。
これで現在どのくらいの連鎖能力を持っているかが分かるので（個人的には潜在的連鎖スコアと呼んでます）、もし更に連鎖が伸びる一手を見つけた場合そちらの方に進化します。この進化を複数回やっていくと大連鎖にたどり着けます。
盤面の選択方法
上の評価の仕方では、「一見連鎖には関係ないように見えるが、あとあと大連鎖につながる一手」というパターンを評価できません。
これを評価する方法が全く思いつかなかったため、ランダムに盤面を選定することで偶然見つけることを期待することにしました。
盤面を評価値で降順でソートした時、上位は評価関数により「たった今連鎖が伸びた盤面」が来ます。そのため後半のものを集中的にランダムで選択しました。
また、実際に連鎖させた盤面からは更に先に探索しないようにしました。
このゲームのスコアは指数乗に上がっていきます。そのため同じブロック数で１０連鎖を２回よりも２０連鎖を１回やったほうが強いです。
そのため連鎖させたあと２発目をどう考えるかよりも、いかに１発を強くするかに思考時間を使うべきだと考えたため、連鎖させた盤面は選定をやめ、まだ連鎖させてない盤面（後出しのほうが更に強い連鎖を持っている）のみを次の探索に持っていくようにしてます。
高い評価値を記録したコマンドリストの保存
標準出力で送るパックの列・回転数をコマンド、２０ターン先読みした際の２０個分のコマンドをコマンドリストと個人的に呼んでます。
ビームサーチ時の盤面の選定には乱数要素を用いてるため、前のターンのコマンドを現在のターンでも探索で見つけてくれる保証がありません。せっかく乱数で偶然見つけた大連鎖の盤面も、全く同じ乱数を召喚しないとその盤面にたどり着けません。
これを回避するため、高い評価値を記録した盤面のコマンドリストは保存し、次のターンではそのコマンドまでの盤面は評価値を補正することで必ず生き残るようにしてます。また最初は２０ターン後での最高評価値のコマンドリストを保存してましたが、多様性を持たせるため各ターン後での最高評価値の分も含め合計２０個保存してます（直感なので、理論的に多様性が生まれるのかは不明です）。
また潜在的連鎖スコアとは別に、単なる発火でのコマンドリストも同じように２０個保存してます。
同スコアの盤面を間引く
これは偶然見つけたもので、
score += random()*0.01 → score += (int)(random()*10)*0.001
としただけで強くなったため採用したものです。
理論的には不明だったため、結果から憶測で「同じくらいの盤面をたくさん所持するより、数を限定することで探索を一点集中できるから強くなるんだろう」と思っていました。
しかし、あとで気づきましたがこれは「重複盤面の削除」を間接的にしていたことが関係しているかもしれません。これは強くするには重要で、一言で言うと多様性が上がります。（あまり詳しくないです）
また強いコマンドも間引く可能性があるので、結果的に強いときは強く弱いときは弱いAIが出来ました。（練習・評価用に作った「絶対に攻撃しないAI」を追い込み、大連鎖を打たせるくらい弱い）
発火タイミング
基本的には、１連鎖増えるたびスコアは1.3倍になるはずなので１ターン後に1.3倍以上増えなければ今連鎖させたほうがお得である、という考えです。
しかし実際は１つパックを落としても１連鎖増えないこともあるので、1.1~1.25の値を探っていました。
最終的には1.0+(ojama*0.0009)（→A）という形で落ち着き、nターン後は
score += point*(pow(A, 20-n))
というものになりました。
高速化
高速化することはビームサーチの幅を増やすことにつながるので、強くするには必須の要素です。
コード全体的に高速化できるか見てましたが、中でも評価関数の「９０回連鎖させる」というのが演算時間の９９％（直感）を使ってたので、ここを重点的に高速化しました。
「９０回連鎖させる」のうち、実際に連鎖するのは大体４分の１ほどでした。そのため１連鎖あるか調べることの出来る軽量のシミュレーターで判定し、実際に連鎖するものだけを実際の連鎖シミュレーターに投げました。
また、ブロックの落下点周辺以外のところや、２連鎖目以上のとき１連鎖前で消えたブロックから遠い場所では絶対に発火が起こらないため、そのような場所では発火判定を行わないようにしました。具体的には落下・発火ポイントから左右下方向に４マスまでの範囲しか調べてません。厳密にはこれでは発火判定されないパターンもありますが、あまり影響はありませんでした。また上方向には省略できないと考えたため上まで調べてます。
あとは条件分岐の数を工夫してできるだけ減らしました。一番ループの深い場所のif文を別の方法に替えただけで１秒早くなったこともあり、正直そこまで影響があるのかと驚きました。
あとは小さなムダを１つずつ削ってましたが、それは割愛します。
その他の高速化としては、連鎖シミュレーションした盤面を保存することで、次ターンでまた現れた場合はその盤面をそのまま取り出すことで無駄にシミュレーションさせないようにしてます。
決勝で提出したソースコードはgithubにあげてます。（初guthub）
