CODINGAME SPRING CHALLENGE 2021 参加記
codingame spring challenge 2021に参加しました。
全体252位、ゴールド25位でした。
レジェンドに一歩及ばず😭
考えたこと
ビームサーチ
最初は相手の動きを考慮しないビームサーチを実装しました。
評価関数は「100000×スコア+1000×サイズ1の木+1000×サイズ2の木+1500×サイズ3の木+SUN」です。
スコア>木>SUN の順に評価してくれるように雑に決めました。
枝刈り(行動制限)を試行錯誤しているうちにGoldになれました。
この枝刈りは改良しながら最後まで流用しました。
DUCT
Gold昇格後は、だんだんとビームサーチの評価関数を考えるのがしんどくなってきたため、ビームサーチを捨ててTwitterで見かけたDUCTを実装してみました。
ぼくは英語が読めないので図を解読しました
なんとか実装したDUCTですが、プレイアウト回数がうまく増やせず弱かったです。(もしかしたらバグってたかも)
プレイアウト
DUCTを強くする方法が思いつけなかったため、他の実装を試すことにしました。
DUCTの実装を無駄にしたくなかったので、「有向手をプレイアウトして勝率を計算し、一番勝率が高かったものを採用する」というものを実装してみました。
有向手の選択には、UCB1を使いました。
これで252位までいけました。
追記 枝刈り(行動制限)について
最終的な枝刈り(行動制限)は以下のようになりました。
SEED
- 0日目はSEEDしない
- 20日目からはSEEDしない
- サイズ0の木が存在するときはSEEDしない
- 木が7個以上だったらSEEDしない
- できるだけ他の木の近くにSEEDしない
GROW
- サイズ2の木は23日目(最終日)にGROWしない
- サイズ1の木は22日目からはGROWしない
- サイズ0の木は21日目からはGROWしない
COMPLETE
- 0日目から11日までは、サイズ3の木が6個未満だったらCOMPLETEしない
- 12日目から14日目までは、サイズ3の木が5個未満だったらCOMPLETEしない
- 15日目から18日目までは、サイズ3の木が4個未満だったらCOMPLETEしない
- 19日目から23日目(最終日)までは制限なし
WAIT
- WAIT以外に可能なアクションがあるときはWAITしない
感想
楽しかったです