はじめに
CodinGameのコンテスト（CodinGame Fall Challenge 2020）に参加しました
結果は世界59/7,036位（Legend）、日本15/320位でした
今回のゲーム終始なにもわからない状態だったのでとてもつらかった
前回に引き続きLegendになれたので満足、いつかは上位争いしたいね
ルール
例のごとくツカモさんがルール要約を書いてくださっているのでそちらを参照してください
呪文で素材を生成してポーションを作成して相手よりスコアを稼いだほうが勝ちです
tsukammo.hatenablog.com
やったこと
最終的にやったことをまとめます
1. ビームサーチで最大15手探索を行い最も良い評価の行動を行う
2. 初手6ターンは評価関数で最も価値の高い呪文をlearnする
3. 7ターン目以降はビームサーチを行い、探索の1ターン目のみlearnも含めて探索を行う
4. 敵が各BREWを行えるのに必要な最短ターンを探索し、それよりも遅くBREWする行動は探索の評価から外す
5. 自分が5個すでに作っていて、敵の最大スコアを超えるなら確定killを取る、逆に相手が6個目を取れる状況でBREW出来なかったらtier-1以上の素材を最大化するようにする
以下、リーグごとに順を追って考察改善したこと、もといポエムです
Wood2
貪欲に一番高いものを取れば昇格
Wood1
難しくありませんでした？
インベントリに複数種類の素材があると強いと思ったので、素材の種類数が減らないようにCASTをするようなルールベースでやってみる
また、行動しないよりもしたほうがいいので素材の種類数が減る場合でもCASTするように使える呪文をランダムに使う
BREW出来るときは優先で取ったほうが良さそうなのでBREW出来るならCASTよりBREWを優先するようにした
結構ギリギリ？昇格で今回難しいな〜ってなってました
Bronze
learnが解禁される
learnは取らないよりも取ったほうが自明に強そうなのでとりあえずlearnを実装
この時点での上位陣のリプレイを見ていると初手10ターンくらいlearnをしてたので同じように10ターンくらいlearnをする
BREWとCASTはWood1のときのものをそのまま使うと初日は30位とかそれくらいで就寝
CASTの探索を効率的に行いたいので考察をする
インベントリの状態は$ _{14} C _{4} = 1001 $通りとかなり少ないので全探索しても良さそう
$ dp[a][b][c][d] := $ インベントリの状態がtier-0がa個、tier-1がb個、tier-2がc個、tier-3がd個あるときの価値が最大のものとしてbfsを行う
インベントリの評価には各素材の価値$ [1.5, 2.5, 3, 4] $とBREWのpriceに早いターンに取ったほうが価値が高くなるように重みを付けたもので評価する
tier-0とtier-1がちょっとだけ価値高いのは、呪文で消費するときに使いやすいくてインベントリにあると強そうだなと思ったため
探索パートの処理が結構重かったので†定数倍高速化†をしたら結構軽くなって敵のシミュレートを出来るくらいの余裕が生まれたので良かったかな（この時点ではやってない）
Silverが解禁されてそのまま昇格
Silver
TLで初期呪文縛ったほうが強いんじゃね？みたいな話題が流れてたのでとりあえず試してみる
$ [2, 0, 0, 0] $の呪文は結構強いのでこれ以外のもの使わないようにしてみる
これが意外と強かった
とりあえず実装！で初期呪文縛っただけなので詰んだ状況になると†直立不動†するお婆ちゃんの情報がTLに多く流れたとかなんとか
結局、初期呪文を含めた探索をすることになるのですが、初期呪文を縛るメリットに探索の効率があったかなーと思います（40msとかだったのが5~10msくらいに減少）
探索に余裕ができたので、敵の各BREWまでの最小ターンシミュレートを実装
大体これくらいのことをやってGoldが解禁されそのまま昇格
Gold
Silverのときに敵のBREWに必要な最小ターン数を実装したので評価に組み込む
具体的には、次のターンに敵の取れる価値が最大のBREWを自分が今のターンに取れるなら取るようにする（相手の邪魔をする）
相手が今のターンで取れるもので次のターン以降に自分がBREWをするような探索は枝を刈る
敵がすでに5回BREWをしていて、敵が今のターンでBREWを取れるもので次ターン以降に取ろうとする探索は意味がなさそう（取れるときにはだいたい取りそうなので）、これも枝を刈る
また、探索をbfsでやっていたものをpriority_queueでダイクストラっぽく価値の最大のものを探索するようにした
chokudai searchとかも試してみたんだけど評価関数が悪いのかあんまりいい動きをしなかったのでボツ
このくらいのときにLegendが開放されて初動で20人くらいで今回やべ〜となっていた、やべえ〜（語彙消失）
やっぱりビーム系の探索で探索に多様性を持たせたほうが絶対強いのでビームサーチを実装してみることに
今まで使ってたダイクストラっぽいものをベースになんちゃってビームサーチ（多分挙動はビームサーチと変わらないはず）を実装
これを投げるとGOLD3位とかで誰かボスたおしてくれ〜となっていた
誰かキャリー頼んだ！ｗ pic.twitter.com/b8ktH9jO6s
— ボンド@競プロ (@bond_cmprog) November 21, 2020
結局見守っていてもボスとレート差1.5とかついてしまったので伝家の宝刀†リサブガチャ†を敢行
何回かやってると上がれそうな雰囲気になってテンションがおかしなことになってスクショを連打しながら奇声を発していた（隣室の人ごめんなさい…）
以下、スクショの様子
感動のフィナーレ
泣いた pic.twitter.com/XTQkDFWkY4
— ボンド@競プロ (@bond_cmprog) November 21, 2020
今回ほんとにきつかったので上がった瞬間叫んじゃいました
Legend
正直Goldでもう案も出し尽くしてサブミットガチャしてたのでこれといって改善できたものはないんですよね（前回もそんな感じだった）
一応パラメータをガチャガチャしてビーム幅を少しだけLegend昇格時のものより大きくしたものが一番良さそうだったのでそれを最終提出
こんな感じでシステス前の暫定順位が55位
最終順位は59位でフィニッシュ
前回同様10日間フルでやり続けたので疲れました
今回は本当に最初からわからなくて苦戦しそうだなあと思ってたし、案の定何もわからない状態が続いてしんどかったなあ
最終的にはLegend到達出来たしよかった、やっぱり楽しいんだよね
最終提出のコードは706行で前回よりちょっとだけ実装多かった
今回は色々書いたり消したりしてたので書いた量自体は前回の倍くらいは書いてそう
やりたかったこと
・learnをもう少し詰めたかった、持っている呪文との相性とか（探索である程度なんとかなりそう感はある）
・高速化を頑張って探索の幅や深さを広げたかった
知見
・Zobrist hashとかで重複盤面を省けるらしい
・ビーム幅と探索の深さを広げるだけでも結構強くなるっぽい？
・相手のターンがnターンで終わるとき（ゲームが終局するとき）自分の手の深さをnにするといいかも？（余計な深さがいらない）
感想
いつの間にか10日間くらい吹き飛ばしたけどやっぱり楽しかったね
†人生†をやらないといけないのでやらないとね…
こどげ前にハル研プロコンとかもあったんだけどこどげに全ツッパするために発表資料作成とかに費やしたので参加できなかったのはちょっと残念だけど致し方なし
次の開催は多分社会人になってからとかかな？今ほど時間で殴れないだろうけど社会人になってからも参加したいね
