CODEVS2.1予選に参加しました。

CODEVS2.1に参加しました。予選で何をやったかについて書いて行きたいと思います。

[予選開始]
ルールを、消えたブロックの周囲の邪魔ブロックが消えることと、点数計算式の計算方法の部分だけ読みました。参加登録も行いました。
CODEVS2.0が非常におもしろかったし、今回は社会人も決勝に出れるという事もあり、やりたいなという意識だけはあったのですが、実際に行動に移すことができませんでした。
平日は仕事で11時以降に帰宅することが多かったので、そこからコーディングする気力というか、まだ自分の中に火がついていない感じでした。

[予選終了3週間前]
ざっくりと方針を考え始めました。この時点ではtekさんが1位を独占していた頃だと思います。
コーディングする時間は無くとも、点数計算式だけを頼りに間違っていない方向の方針を立てることはできます。
具体的な点数計算式は公式ルールを見て頂くとして、大量のブロックの同時消し爆弾が大前提にあって、そこから線形に連鎖数とFc(それ以前の中起爆回数)が掛かる感じでした。

方針としては、
1.Fcを出来るだけ溜める
2.爆弾(大量の同時消しができる形)を作る
3.連鎖を作る
4.起爆する
という方針が高得点を狙えそう。2と3は作りやすい順番でいこう。
と考えました。

2.0予選で不定形連鎖よりも定形連鎖（システム連鎖）の方がつよかったこともあり、今回もシステム爆弾が強いに決まっているだろうと予想していました。

とりあえずSmallに向けてコーディングを開始

2.0のコードを少し修正して邪魔ブロックの消しに対応、点数計算式を修正、ランダムに落とすAIをつくってスコアが完全一致することを確認しました。
幅優先探索を使ってFcを溜めるAI(以後チャージAI)を作ったけれどFcが１増える前にノードが爆発してしまいうまく行きませんでした。
幅優先探索で、深さが増えるたびにノード数が一定以下になるまで減らす（ビームサーチ?)を初めて実装してみて、汚いコードになったけどそれっぽく動いてくれました。
システム爆弾をつくるための前準備として、とりあえず決め打ちした形に落とすAIを作りました。smallで100を超える同時消しが出来てテンション上がりました。
gitでソースコードを管理しようとして、

git init
git add codevs21/* (あ、不要なファイル追加しちゃった)
git reset --hard

とやって、ソースコードが全消滅しました。皆さん気をつけましょう。
VisualStudioで開いていたファイルや、2.0のコードの再利用で大体が復元出来ましたが、システム爆弾の部分は全て消えてしまいました。

[予選終了2週間前]
tekさんの点数を逆算して、方針を盗んでやろうと考えましたが、どう考えても数十倍足りませんでした。勝てる気がしない。
なんかどこかで見覚えのあるHNの人が1位をとっている。なんなんだこのおじいさんは。twitterみたら「ちょっとやってみた」とか言っている。頭おかしい。勝てる気がしない。

システム爆弾を作り直すの結構だるかったので、チャージAIをコピペして評価関数だけ書き換えて爆弾を作るAIを作りました。
数十ターンでシステム爆弾を上回る同時消しが生成されてテンションが上がりました。(システム爆弾とは何だったのか)

チャージAIをまたコピペして評価関数を変えて連鎖AIを作りました。

結局以下の3つのAIが出来ました。
・Fcの値をできるだけ溜める(チャージAI)
・連鎖尾爆弾を作る(ボムAI)
・連鎖を作る(チェインAI)

同時消しの小さい連鎖の連鎖尾として大きい同時消し爆弾を爆発させたいのですが、どうやったらうまく作れるのか分からず試行錯誤をしました。
結局、発火点を中央-1の列に固定して、フィールドの右半分で爆弾を作った後、発火点を一番左の列に固定して、左半分でとにかくスコアが大きくなるように探索する方針がうまく行きました。
ある程度大きな爆弾を作ってしまい、あとは連鎖でしかスコアが伸びにくい状況を作った上で探索すれば自然と連鎖が出来てくれます。

探索幅の制限を広くして、1回1時間程度のAIを走らせてみたところ、Smallで7e12点位(Small 当時6位)が出て、近いところまで来たという感じがしました。

ビームサーチの書き方がとても汚かったので、2.0のShoheiさんのコード(Githubに上がってる奴)を参考にさせて頂いて3つのAIを書き直しました。再帰で書くとか目から鱗でした（もしかしてとても基本的な書き方)。
AIの中のあらゆるパラメータを抜き出して定数化し、設定ファイルとして読み込めるようにしました。
余っていたノートPCがあったので、会社で覚えたJenkinsCIをインストールし、のJobでパラメータ付きビルドとしてAIのパラメータを選択できるようにして、仕事中や飲み会の途中にパラメータとスコアの関係を調べていました。

こんな感じでiPhoneからポチポチできます。

少しだけパラメータ変えて基本的に同じプログラムをMedium、Largeで走らせて6位に入りました。

[予選終了1週間前]
GOLDランクに入ってしまったからか新しい方針を考える思考がなくなってしまい、ずっとパラメータ変えて時間を浪費していました。
探索幅を広げて時間かければしっかりスコアが伸びていくのが確認できたので、シミュレータを高速化しました。

windowsで使いやすいプロファイラを知らなかったので、会社のMacBookAirでビルド出来る環境を作ってTimeProfilerを走らせました。すごくわかりやすいですこれ半端ないです。
想像通り連鎖の消去判定が実行時間の7割を占めていたので、ここを中心に高速化を行いました。
大体やったことは
・2.0のkusanoさんのコード(Githubに上がってる奴)のシミュレータを参考にして、STLを排除してテンプレートでシミュレータ全体を書き直し
・再帰で実装していた消去処理もしゃくとり法の定数回ループに置き換え
・落下したブロックのバウンディングボックスの範囲だけ対してだけ消去判定を行うように書き換え
ぐらいです。かなり早くなりました。

[予選終了直前]
パラメータ調整や軽い評価で枝刈りの範囲を広げたりしつつ何度も実行していました。
高速化の甲斐もあってか、4位に入っていてさすがに安全圏。欲がでてきて、
「僕は...あの人(3位のおじいさん)に...勝ちたい!!」
とか考えながらMedium抜いた瞬間おじいさんもスコア上げてきて全然勝てませんでした。

[予選終了当日]
4位で終了。と思ったら
給料日を迎えた課金勢のkusanoさんが突如現れ、気づいたら5位になっていました。

[工夫した点]
これをやっていなかったらGOLDランクに入れなかったなという点
・点数の概算
パラメータ調整の際、実際に何時間も走らせずに点数を概算することによって時間を節約し、反復回数を増やしました。
例えば、Fcの値は大体100-120位まで溜めるとしてあるので、ゲーム開始直後に(Fc=0の時に)爆弾->起爆のAIを走らせて、それを100-120倍すれば、大体Fcを溜める時間を省略して点数を概算する事ができます。
このように短い時間で強くなっているか測る判断基準を作ることが非常に大事です。
あと、点数計算式から、上位陣が何やってるのかを予想する事は非常に大事です。明らかに足りない場合は何か見落としている点があります。

・Git
バージョン管理システムGitです。
高速化用にブランチ切って、詰まったら一旦止めて元のブランチに戻ってAIの考察とか、
Large用にブランチ切って、ハードコードでひたすら調整し実行。そのまま何点取ったかをタグ打ち
のような使い方が出来てホント便利です。学生時代の僕に教えてあげたいです。

[おまけ]
予選動画 Small