CODINGAME SPRING CHALLENGE 2021 参加記

CodinGameのSPRING CHALLENGE 2021に参加しました。

twitterが盛り上がっていて楽しかったです。

結果

世界66位日本12位でした。

TLの知見ツイートにかなり助けられました。

学校別では世界11位日本2位でした。

11人参加していたんですが、10人がゴールド以上で凄い。

ルール

いなにわさんの記事が分かりやすいです。

inaniwa.hatenablog.com

最初に実装したものを書いた後、改善したことを説明しようと思います。

最初に実装したもの

UCB1のDUCTで、プレイアウトはうまくいかなかった（時間がかかり過ぎるし、高速化しても強くなる気がしない）ので、評価関数を使いました。

評価関数

得点=(この後ずっとwaitすると仮定した場合の最終的なsun)/3+

(スコア+(自分の木がある場所のrich-1)×s[その木のサイズ])×日付×3/23

s[4]={0.2,0.7,1.2,1.8}

自分の得点と相手の得点を計算して、

自分の得点>相手の得点の場合、1

自分の得点=相手の得点の場合、0

自分の得点<相手の得点の場合、-1

今後取得できるsun、現在のスコア、木がある場所のrichを得点に入れたい気持ちになった感じです。

高速化

使える場面が多そうで、自分的には非自明だった高速化を1つ紹介します。

DUCTで使うノードの構造体のメンバに、手ごとの累積ポイントを記憶する配列が欲しくなると思います。

これのサイズはノードによって違うので、速度が遅いvectorを使うか多めにサイズを取った生配列を使うかになってしまいそうなのですが、下のように大きな配列をグローバル変数に持っておけば必要な分だけ生配列を使えます。上手い構造体を書けばvectorと同じ使い心地で使えそう。

改善したこと

評価関数

早々に試合を諦めてWAITをしまくるのを直したかったので、評価関数が返す絶対値をmin(1.5,大きい方の得点/小さい方の得点)にしました。狙い通りに諦めるのが減った気がします。

seedの制限

高速化と、探索の質の向上のために現在のターンor１日の初めのターンのみSEEDをするのを許可しました。

行動の順番を決める

DUCTの探索中、1日の中では、

SEED→COMPLETE→GROW(2→3)→GROW(1→2)→GROW(0→1)→SEEDの順番で行わせるようにしました(例えば、GROW(1→2)をやった後は、その日の中では左３つはやらない)。

seedの範囲制限

自分の木が隣接しているマスにSEEDをするのを禁止しました。  

これがLEGEND入りの決め手になりました。LEGENDに入った後、同じ方向で2マス進んだところに自分の木があるマスも禁止したらさらに強くなりました。

感想

自己対戦を自動で行ってくれるツールが流れてきたおかげで素早く強さを測定できてとても便利でした。ただ、自分で作ったものではないので不便な点が多かった（エラー出力が闇に消える、時間制限の変更ができない、測定が遅いなど）ので、自分で作れるようになりたいな〜〜

MCTSを高速化以外で改善するのは初めてで楽しかったです。