CodinGame Spring Challenge 2021 参加記録
CodinGame Spring Challenge 2021に参加しました。
リアルタイムのコンテストでは初Legendです。とても嬉しい。
ルール
下記記事参照。
考察
手法
ルールベースや評価関数系を作るにはゲームパラメータが多く複雑で、MCTS系を作るには有効手が多すぎ探索も深くなる。
→何も分からん。
→センスが無くてもなんとかなるMCTS系で行くか…。
栄養素
戦略性がある。同じ回数ずつCOMPLETEするとして、先にCOMPLETEすると[相手の残りCOMPLETE数]分のアドバンテージを稼げるっぽい。序盤に纏めて行うと乗算で効いてくるけど、相手もCOMPLETEを挟んでくると効果が薄くなる。自分のSUN収入源である木を失うので、攻めるのにもリスクがある。
影
3日後には反対方向から日が当たるので、相手を妨害できるパターン≒自分が妨害されるパターンとなる。そのため盤面を木だけで評価することは難しく、翌日や以後何通りかの日当たりから評価する必要がありそう。具体的には翌日に相手の木が影に入るようにしたり、影になる位置のSize3は枯死させてしまう等。
戦略
木を成長させるとSUN収入が増えて更に木を成長させられるので、とにかく序盤ゲー。土俵に立てるか否かでそのまま勝負が決まることも多い。探索するとしても、序盤はルールベース埋め込みにする手はあり。
最終的にやったこと
DUCTのみ。
プレイアウト数は最初のターンに900msで6000プレイアウトくらいで、高速言語勢と比べると少なめ?またMCTS系の問題点として、プレイアウトに全ての有効手を一様乱数で選ばせると、現実味の無いプレイばかり行い結果が信用できないというものがあった。今回のゲームはSEEDコマンドの使用頻度が低い割に列挙した場合のコマンド数がとても多く、特にプレイアウトの精度が低くなりがち。
そのため工夫点として、プレイに現実感を持たせるため、一定条件で特定コマンドを強制、または禁止した。前向き枝刈りというらしい。*1
プレイルールは以下のようなものを用意した。以降、日付は0日目~23日目という表記。
・0日目はWait
・4日目まではSize0,Size1の木がどちらも存在しない場合のみSEED可能
・4日目まで、木同士を隣接させない
・7日目まで、SEEDは桂馬飛びで行う
・12日目まで、長さ4の直線上に自分の木を3つ並べない
これらは初動の良い動きはほぼ固定となるため。
・木(種を含む)は9本まで
・Size毎の木は、小さい順に{2, 3, 4, 6}本まで
同じサイズの木を持ちすぎるとGROWコストが苦しくなるため。
また、木は多すぎても影のせいでパフォーマンスが伸びないため。
・SUNが15以上ならSEEDは使わない
これはGROWの後にSEEDすることでが目的で、
種を減らしてSEEDコストを下げるのと、SEEDの考慮回数を減らすため。
・Size1の木はSEEDを使わない
これはLegend勢のリプレイを見たらそうなっていたのでSEED考慮抑止に。
・16日目まで、SUN収入(理論値)18未満の場合COMPLETEしない
これは中盤までに無理にCOMPLETEして後が続かないのを避けるため。
・Size3の木が6本かつSUN16以上あれば必ずCOMPLETEする
・木が9本かつSize3の木が3本かつSUN16以上あれば必ずCOMPLETEする
これらは中盤でCOMPLETEさせ、栄養素の争奪を表現するため。
・最終日は栄養素が2以上あれば必ずCOMPLETEする
・Seedは19日目まで、Grow(0→1)は20日目まで、…
(最終日COMPLETEが間に合うように)
これらはサイズ3の木を持ったままゲームが終わることを避け、
プレイアウトの精度を上げるため。
これらのルールは自分で考えたものや自明なもの、上位のリプレイの特徴を目視で分析したもの。まだまだ改善の余地はありそうだけど、コンテスト期間中にやれることは頑張ったかな。
リーグ別やったこと
Wood2, Wood1
貪欲っぽいルールベースをしました。各木の違いは生えている場所の土壌品質だけなので、土壌品質が高い順に(GROW→)COMPLETEすると最大の得点を得られます。実は中央ほどCellIndexが小さいので、土壌品質の降順でなくCellIndexの昇順に処理することができます。
Bronze
自分の点だけを考慮するMCTSを書きました。
5日目までは桂馬飛びとか、簡単な枝抑止は入れました。
Silver開放と同時に昇格。
Silver
序盤の土俵入りが弱かったので、4日目までの動きをルールベースにしました。
(この辺でプレイルールを整備しないと先が無いことに気付く)
あとはTimeoutが多すぎたので、探索時間を90ms→80msに短縮しました。
リーグ開放から1日くらい遅れて昇格。
Gold
MCTSをDUCTに変更しました。
式はよく分からなかったので、互いにUCB1-Tunedで手を選ぶようにしました。
Legend勢のリプレイを見て、プレイルールをゴリゴリ埋め込みました。
まだTimeoutが多かったので、最初に5000個作ったノードを使いまわすようにしました。
最終日に昇格。
Legend
残り時間がほぼ無かったので新しいことは何もしていないです。
後日談
Seedを2個までにしていたのを、1個までに変更したところ100位上がりました。
もっと思い切って調整すれば良かった…。
感想
取っ付きやすくはないけど、それが故に解法が自由で面白い問題だったなと思います。
DUCTやノードの全使いまわしを新しく覚えたり、
MCTSのプレイ矯正をやりこんだりと得られるものも多かったです。
今回はTwitterでの技法の情報交換も活発でしたね。
今後も楽しみながらスキルアップ出来るコンテストとして推していきたいです。
*1:有効手を列挙する関数内にif文がいっぱいあります。