はじめに
CodinGameのコンテスト（CodinGame Spring Challenge 2021)に参加しました
結果は世界466/6,867位（Gold）、日本45/424位でした
Legendに行けなくて悔しい！
終始わからないまま真心を込めたお気持ち評価関数を書いて終わってしまった
日本人参加者が前回より100人くらい増えてていい感じ、もっとこどげ人口増えろ！
ルール
ツカモさんが体調不良とのことで（ご自愛ください）、いなにわさんがルールの日本語訳記事を書いてくださってるのでそちらを参照してください
inaniwa.hatenablog.com
やったこと
評価関数 + ルールベース + 最後の5ターンだけビームサーチ
- 12日目まではCOMPLETEをしない
- SEEDはコストが0のときのみする
- SEEDは自分の木にできるだけ隣接しないところを選ぶ
- 木はサイズ順に最大で$ {1, 2, 4, 7} $ までしか評価しない
- COMPLETEはサイズ2とサイズ3の合計が7以上のときのみ行う
- もしくは、日数が17日目以降でCOMPLETE出来るならする
- GROWはサイズが大きい順に実行する
- ビームサーチは最終日まで1行動1深さで行い最終的なスコア$ (score + \frac{sun}{3} ) $ が最大になる行動を選択
Wood2
スコアが高いものを選択する貪欲
Wood1
richnessが3のところをGROWしてCOMPLETEする
Bronze
初手WAIT -> 2ターン目GROW -> 3ターン目SEEDをして真ん中を取りに行く
GROWの優先順位をサイズの大きい順にする
Silver
一直線に真ん中を目指すと、自分の木が陰になって損することになるのでSEED先を桂馬飛び（陰にならない）箇所にする
木のコストを考えて、盤面の木がサイズ順にそれぞれ $ {1, 2, 4, 7} $ より多くならないように制限
Gold
特に大きな改善はできず
ビームサーチを実装するなどしたが、貪欲に勝てず
序盤は貪欲、最後の詰めだけビームサーチ（ほぼ全探索）をして最終的なスコアが高くなる行動をすると少しだけ強くなったので採用
最終提出は19日目まで評価関数 + ルールベースの貪欲、20日目以降はビームサーチを行ったもの
感想
今回は社会をしながらの参加で、去年より時間取れなかったけど参加してとても楽しかった（疲れた）
やっぱり学生の時より使える時間は減るけど、今回はフルで使ってもレジェンド届いたか怪しい
前回のレジェンド80人で、今回その3倍くらいいるんだけど体感難易度今回のほうが高かった、全人類こどげが上手
日本人参加者も100人くらい前回より増えててこどげ人口の高まってる感があってとてもいい感じ
レジェンド行けなかったの悔しいのでちゃんと復習して次のコンテストでリベンジしたい
やりたかったこと
・初手からビームサーチ（組んだけど貪欲に勝てなかった）
・DUCT（MCTS）
・bitboardなどで高速化
・相手の行動を考慮した探索
知見
感想戦のあと随時追記します
- 1dayの行動をSEED -> COMPLETE -> GROW2 -> GROW1 -> GROW0のように順番を固定する（GROW xはsize xをGROWさせる）
SEED 2 3 -> GROW 4 と GROW4 -> SEED 2 3は最終的には同じ盤面なので順番を固定することで探索空間を減らせる - ビームサーチでWAITしたら次の日に対応する深さに飛ばす
日によって深さを合わせるはやっていたが、WAITし続けるような実装をしていたのでこっちのほうが直感的だしバグらせにくそう - 相手の手もビームで読むの大事、超大事
mini-maxっぽく最悪想定で探索するのがいいっぽい - 評価関数を[0, 1]に正規化するとき、自分の評価を $ g(0) $ 、相手の評価を $ g(1) $ とすると、$ f(x) = \frac{g(0)}{g(0) + g(1)} $ がいいかもしれない？
qLethonさんのメモ 参照
