codevs reborn に参加しました
しました。
codevsとは
ゲームAIを作って強い人が優勝。
tl;dr
結果
- 17/112位
- ずっとシルバー(30位以内)をキープしていたようなしていなかったような*1。
- 前回参加した、codevs for student(以下codevsFS)は社会人含めて27~30位ぐらいだったので、多少は上がったかな*2。
戦略
- ビーム風サーチ（幅20+時間ループの通称chokudaiサーチ）で探索。
- 60点程度(ojama3行)の連鎖またはスキルをなるべく早く撃つ。
- 長めのチェインを組もうとする相手に強いが、主にスキルを使う相手にとても弱い。
ルールざっくり
- 幅10、高さ19のフィールド。高さ16を超えると負け。
- 基本的には、数字が書かれたぷよぷよ。
- 落下するパックは事前に全て与えられる。
- 8近傍で隣り合う2つのブロックの数字の和が10のとき、その2つのブロックは消滅する。
- スコアは連鎖数の指数関数に比例する。
- スコアに応じて、お邪魔ブロックを相手にストックする（お邪魔ストックに加算する）。
- お邪魔ストックが10以上の場合、 ターン開始前にお邪魔ブロックを各列に1つ降下させ、お邪魔ストックを10減らす。
- スキル以外の方法でブロックを消すと、スキルゲージが定数増加する。
- スキルゲージがある程度溜まったうえで、スキルコマンドを打つと、「5」とその8近傍のお邪魔でないブロックを消去する。スキルゲージは0になる。
- 対戦相手が3連鎖以上すると、スキルゲージは減少してしまう。
どんな戦略が考えられるか？
要は、早くかつ多くお邪魔ブロックを送りたい。 そのためには、「長い連鎖を組む」「ブロックを貯めてスキルを使う」が考えられる。 上位陣の多くが「長い連鎖を組む」派だったので、この人々に刺さるよう設計。 長い連鎖が発火する前に、お邪魔ブロックで覆ってしまえば良いです。
スキルメインのAIの対策については、3連鎖をかなり短い周期で打つ、しか思いつきませんでした。 連鎖と共存できなさそう・アドホックな対策をしたくない気持ちがあったので、結局無対策でした。
連鎖を組む・評価関数など
codevsFSの知見ですが、譜面探索の評価関数を「発火したいターンのパックを落とした時のスコア」としてビームサーチするとNormalAIに勝てる連鎖が組めます。 細かい改良はあるものの、最後までこの実装でした。
TODO: 大きな連鎖をするコマンド列が見つかったときの、そのコマンド列を評価する評価関数について納得のいく説明が出来ない
該当箇所はここ codevsRB/BattleAI.cpp at master · buyoh/codevsRB · GitHub
やったこと
重複盤面の除去
最初の一手目を左半分のどこかに配置することで、鏡対称の盤面の除去が出来ます。
3列目に投下することと4列目に投下することは大差ないので、固定しちゃった方が良いと思います*3。
これ以外はよく分かりません。僕も知りたいです。
zip提出形式にする。
zip提出形式の場合、コンパイルオプションを指定できます。今回は、-Ofast -march=native -pthread を指定しました。
COPT='-Ofast -march=native -pthread'
if [ ! -e ./codevs ]; then
g++ $COPT -c BattleAI.cpp -o BattleAI.o
g++ $COPT -c CaseGenerator.cpp -o CaseGenerator.o
g++ $COPT -c Exec.cpp -o Exec.o
g++ $COPT -c Game.cpp -o Game.o
g++ $COPT -c Input.cpp -o Input.o
g++ $COPT -c Main.cpp -o Main.o
g++ -O3 Main.o Input.o Game.o Exec.o CaseGenerator.o BattleAI.o -lm -lpthread -o ./codevs
fi
./codevs
マルチスレッド化
ローカルで対戦を回す事を考えて、マルチスレッド化しました。パソッコンは、こちら。
自作PCを組み立てました - shonen.hateblo.jp
ところで、他の競技者の環境のスペックが強すぎます。これは勝てない。
6コア12スレッドのPCなので、計算スレッドを12個立てる。 あとは、ヒープ領域への依存を減らしたり、ヒープ確保やスレッド共有部分への書き込みを一か所にまとめたり。
マルチスレッド化によって、自己対戦では明らかな差は出たものの、他プレイヤーとの対戦ではそこまでマルチスレッド化は効果無かったように思います。 （多分、ビームサーチ・評価関数の多様性の問題だと思ってる）（他の高速化についても同様）
探索後のchokudaiサーチのキューに貯まる1ターン辺りの面数はシングルスレッドで1万行かない程度、12スレッドで5万超える程度？
相手の計算時間を利用する
こちらの記事に書いてあったので、実装。今夜勝ちたい CODE VS for STUDENT 攻略 : KLabGames Tech Blog
メインスレッドで入力を待ち、サブスレッドで計算する。
前ターンのchokudaiサーチに使った優先キューは再利用せずクリアしています、
テストを作る
google testを使って雑なテストを書く。
redmineを使う
最近自分の環境にredmineをお試しで入れたので、戦略やTODO、実装方針は全部redmineに書きました。 外出中に思いついた事をスマホで書き込んだり眺めたり出来るのは便利だった。
やらなかったこと
永続データ構造
使いこなせるほど知識が無い。実装したら逆に重くなった。
ビットボード
TL;DR: std::bitset<N> と std::array<bool, N> を比較するとどちらが高速？
1つのセルは4bitで表現できますが、フィールドへの書き込み・読み込み時間を早くしたかったので、int8_tの8bitで表現しました。 同様にSIMDもしませんでした。
自作allocator
頻繁にメモリの開放・再確保が行われていたので、これを解消するために自作allocatorの実装を考えました。
が、提出サーバ側のメモリ制限1GBが厳しそうだったので止めました（500MBまではよく消費するので）。
ローカル専用でも実装しておけば良かったかも、と終わってから思うなど
つぎやりたいこと
自動チューニング・機械学習を導入したいが有効な適応方法が全く分からない・・・
