CodinGame Fall Challenge 2020

CodinGame でやっているゲームAIのコンテストに参加した。 このサイトは年に数回コンテストを開催していて、各期間は10日ぐらい。次は2021年5月6日かららしい。なぜゴールデンウィーク最終日の翌日から……。

今回はこんな感じのゲーム。 ルールはこちらでまとめられている。 結構いい順位が取れたので方針などをまとめておく。

最終的な方針

基本的な戦略は、相手の状態は気にせずにビームサーチでなるべく速く点数を稼いでいくというもの。

ビームサーチは

• 幅 1000
• 深さ 20 ターンまで (時間が足りなくてそれより少ないときもある)

ビームサーチの各状態は

• 持っている素材の数 (8bit整数 * 4)
• 各呪文が使えるかどうか (32bit整数)
• 獲得したポーションといつ獲得したか
• 自分が/相手が習った呪文 (32bit整数 * 2)
• (最初のターンの行動)

で、取りうる自分の行動を元に次の状態に遷移する。 ただし、相手がどう呪文を習うかはわからないので、直前の相手の行動がLEARNだったら最初のものから順番にずっと取り続けていくというふうに仮定した。 また、まだ見えてない呪文やポーションも次に何が出るかわからないので、考えないようにした。

各状態の評価値は

• (獲得した点数)
• レベル k (0~3) の 素材の個数を x として min(x, 4) * k
• (獲得したポーションの個数) * 5
• (最初の獲得したターン / 現在のターン) * -1
• (最後に獲得したターン / 現在のターン) * -1
• min(12, 習った呪文の数)
• 獲得したポーションの個数が6個なら inf * (最終スコア) (inf は適当な大きい数)

を足し合わせたもの。

ビームサーチの重複削除は (持っている素材, 呪文使用可能状態, 習った呪文) が見たことあるものだったら無視する、というふうにやった。ビームサーチは多様性の確保が大事らしいけどちゃんと見るのを忘れていた。

その他細かいこととして

• 2ターンの全探索で確定勝ちを見つけたらそっちを使う
• 負けが確定するものは評価値を -inf
• 評価値が inf 以上なら、そこでビームサーチを止める

などをやった。

雑多な感想

• Twitterを見てる感じでは自分の方法はビーム幅/深さが大きめだったらしい。特に最適化などはしてないので謎。
• 序盤にシミューレーターを書いておいて、自己対戦で有意に強くなってるときだけ変更を取り入れるようにした。提出だと評価に時間がかかるからこの方針は良かった気がする。
• 途中までLEARN行動を固定してたせいでずっとゴールドボスに勝てなかった。これをビームサーチを使うようにしたら一気に強くなった。
• TLE問題は自分にはほとんど起きなかった。たまに 52 msec とか表示されてるのにTLEにならないのは謎だった。
• Rustはマラソン用の言語として優秀。
• Kotake, Koume とか書いてあるけど任天堂に怒られないんだろうか。