Codingame Fall Challenge 2020 参加記

2020年 11/12(木) ~ 11/23(月) に開催された Codingame Fall Challenge 2020 に参加しました
最終結果は 41/7043 位でした

やったこと

ビームサーチ

幅1 で時間制限まで回す
深さは max(20, 35 - turn)
- 浅い読みだと LEARN の価値が低く見積もられると想定して深くした
- 35 ターンでゲームが終了するとざっくり想定
- 20 は最低読む深さで調整の結果だが長過ぎる気もする
12 ターン以降は LEARN を遷移から外す
- リプレイを見る限り後半 LEARN を必要としない場面が多いため探索効率を優先
相手が常に一番下を LEARN すると想定して適宜 LEARN を遷移から外す
- あとで取れば良いと判断して一旦取らないでおくような操作を弾く

評価関数

「BREW でスコアに変換される素材」と「ゲーム終了後まで残る素材」で価値が異なる為、
現在累計で何回 BREW を行ったかでどちらに属する素材なのかざっくり判定することにした

5 回目の BREW をまだ行っていなければ現在のインベントリを「BREW でスコアに変換される素材」と判定
- 評価値は score + (tier-0 + tier-1 * 2 + tier-2 * 3 + tier-3 * 4)
- 実際には終了後まで残る素材もあるが判定できないので無視
5 回目の BREW を行っていれば「ゲーム終了後まで残る素材」と判定
- 評価値は score + (tier-1 + tier-2 + tier-3)
- 実際にはこの中から一部が「BREW でスコアに変換される素材」になるが判定できないので無視

上記の評価関数だと LEARN を行うことの価値が低く見積もられてしまい、
LEARN せずに CAST する操作が優先的に探索されてしまう。
LEARN してから CAST する操作を優先的に探索する為に以下の補正を加えた

15 ターン目までは習得済み CAST の個数を補正値として評価値に加える
15 ターン目以降は補正を外す
- 15 ターン辺りからは LEARN してから CAST する操作のほうが素で評価値が高くなるだろうと想定

またゲーム終了となる操作列の場合は厳密なスコア計算を行い

相手より自分のスコアが高い場合は評価値を +INF - turn * N + score
自分より相手のスコアが高い場合は評価値を -INF - turn * N + score

とした (N は取りうる score より十分に大きい値)
できるだけ早くゲームを終わらせて、その上でスコアが高い状態を探すイメージ

相手側の探索

相手の行動により自分の将来の行動が制限される場合がある
これにより発生する不利をできるだけ無くすために、相手側から見た状態でビームサーチをして、
その探索結果に基づき自分の探索を行うことにした
探索で得られた N ターン先までの相手の状態をターン毎に持っておき、自分の探索を行う際に以下のような処理を行った

相手が使用した BREW は遷移から外す
相手が使用した BREW を自分が使用していた場合は妨害が成功したとみなして評価値を少し良くする
相手がゲームを終了させた場合はこちらもゲーム終了とみなす

N ターン目の自分の状態を評価する場合は N ターン目の相手の状態を参照する
ゲーム終了とみなした状態はそれ以上探索しない
探索で得られた結果とは異なる操作を行われた場合のことを考えるとあまり良い手ではなかったかも

重複盤面の排除

ビームサーチの探索の中で同一の状態を複数回探索してしまうのを防ぐために、以下のような形で重複盤面の排除を行った

以下の値で同一な状態かを判定する

操作集合
- 同一である場合、例外を除いて同一な状態になる
使用済みの CAST
- 操作集合が同一でも REST のタイミングによって変化
インベントリの tier-0
- 操作集合が同一でも LEARN のタイミングによって変化
スコア
- 操作集合が同一でも BREW のタイミングによって変化

スコアが低いものは探索する必要がないと判断し、以下の key, value でメモ化した

key: (操作集合, 使用済みの CAST, インベントリの tie-0)
value: スコア

同一の key がメモに存在し、メモのスコア >= スコア であればその状態はそれ以上探索しないようにした
操作集合については各操作をハッシュ値に変換して足し合わせたものを用意することで計算が重くならないようにした
(遷移のたびに操作に対応したハッシュ値を足して更新する)

操作順序による無駄な探索を減らすために導入したが、操作集合が異なるが同一の状態という場合に対応できないので改善の余地がありそう

高速化

使用済み CAST, 取得済み LEARN などの集合を BitSet で管理するようにした
(事前に ID を圧縮しておくことで 32bit の整数値に十分収まる)
また BREW のボーナス計算や LEARN の先読み税計算のためのカウンタも BREW、LEARN それぞれ一つの整数値に収まるようにした
(愚直にやると BREW では 2つ LEARN では 6つのカウンタが必要になる)

やったけどだめだったこと

並列化

コンテスト中 twitter で Codingame は並列化可能っぽい？というのを見かけたので mpsc を使いビームサーチの並列化を試したが、実際に動かした際に探索回数が並列化前よりむしろ悪化した為、Codingame の実行環境ではマルチスレッドが使用できないと判断し、あまり調査せずそこで切り上げてしまった
(もしかしたらできるのかも)

LEARN の価値推定

LEARN の取得がその後どの程度スコアに貢献するのか推定できれば min_max 法でいい感じにできる気がしたので
LEARN の価値推定を試したがうまくいかず

以下が CAST が貢献する 1 ゲーム当たりの平均スコアになるだろうと想定

(CAST した回数) / (LEARN した回数) x (CAST により加算されるインベントリの価値)

ローカル環境で自己対戦を回して上記を記録し
それを調整しつつ評価値として用いてみたが、あまり芳しくなかったので切り上げた

本質とは関係ないこと

ローカルでの実行環境の構築

テスターのリポジトリが公開されているので、若干コードをいじりつつ手元でビルドしてローカル実行できるようにした
これは主にベンチマーク用の入力ファイルを生成するときに役立った
全然関係ないけど issue を立ててる人がいたのでコメント返したら解決したっぽくて良かった

CI

元々マラソン用に Github + AWS CodeBuild の構成を用意しており手元のコードを push すると CI が動いて
slack に通知が行く感じになっていた
あまり活用できてる感じは無かったが、一応少し書いたテストが毎回実行されてるので良かった気はする

Rust

Clion でデバッグ機能使っても C++ 無限にバグらせる自分が、
Rust だとほぼバグなく実装に専念できたので、マジで良い言語だと思います
最近はコンパイル通すのも苦でなくなった感がある

感想

学生時代ぶりに長期間の AI コンテストに参加しました
あの頃と比べてアルゴリズム的な能力は全く成長してないですが、それ以外の部分が多少なりとも社会で鍛えられたのでそれなりに良い結果が出せた気がします
あと今は無職なのでフルで参加でき、時間を使いきれたのも大きいです
社会で生活をしながらこういう長期コンテストに参加して結果を出せる方は本当に尊敬の気持ちです

[おまけ] 危なかった話

ビームサーチで状態同士の価値を比較する必要があり、以下のようなコードを書いていました
これは self.value と other.value を比較し、比較に失敗した場合 (値が NaN だった等) に except 内をエラー出力としてプログラムが落ちる感じです

impl<S> Ord for StateWrapper<S>
where
    S: Clone,
{
    fn cmp(&self, other: &Self) -> Ordering {
        self.value.partial_cmp(&other.value).expect(
            format!(
                "Failed compare f64 (value0={}, value1={})",
                other.value, self.value,
            )
            .as_str(),
        )
    }
}

自分としては比較に失敗した場合のみエラー用の文字列が生成されてほしい気持ちだったんですが、
上記だと常に文字列が生成されるコードになっています
そのためビームサーチ内の状態比較のたびに上記のエラー文の生成が走りパフォーマンスが劇的に低下していました
最終的に以下に修正して事なきを得ました
以下のコードでは比較失敗時のみエラー文の生成が行われます

impl<S> Ord for StateWrapper<S>
where
    S: Clone,
{
    fn cmp(&self, other: &Self) -> Ordering {
        self.value.partial_cmp(&other.value)
            .unwrap_or_else(|| {
                panic!(
                    "Failed compare f64 (value0={}, value1={})",
                    self.value, other.value,
                )
            })
    }
}

rust-clippy という rust の静的解析ツールがあり、 Legend に上がった後になんとなくかけてみたんですが、指摘事項を修正した後にベンチマークを取ると異様に速度が向上しており糞ビックリという話でした
clippy ありがとう