はじめに
CodinGameのSpring Challenge 2021というゲームAIコンテストに参加しました。結果は参加者6867人中6位（日本勢3位）。まさかこんな成績が出せるとは思っていなかったので、本当に嬉しいです。
ゲーム概要
種を蒔いて木を育てて、育ったら伐採してその得点を競う二人用ボードゲームです。木を育てると太陽光を受けて行動ポイントが入るので、それを使ってさらに木を育てていく拡大再生産ゲーです。雰囲気を掴むには対戦動画を見てもらうのが早いかも知れません。
何かに似てる？はて……。
詳しいゲームルールはいなにわ（@inani_waon）さんが日本語訳してくださっています。ありがとうございます！
以下ルールを知っている前提で書いていきます。
考えたこと
ゲームAIなのでまずは評価関数を作りたい気持ちになりましたが、何もわかりませんでした。
過去に参加したSpring Challenge 2020やFall Challenge 2020のときは比較的分かりやすい指標があったのですが、今回はルールが複雑で、こんなの人間には不可能だろという気持ちになりました。*1
というわけで、評価関数作成をサボれると噂のモンテカルロ木探索を採用することに。大して考えてないって？はい……。
やったこと
DUCTを使いました。二人同時着手ゲーム用のモンテカルロ木探索ですね。DUCTについては別記事にまとめています。
ただ、何も考えずDUCTを実装するだけだと弱かったです。というのもこのゲームはSEEDコマンドが曲者で、（木の本数）×（種を植える先）個の大量のSEED候補が出てくるので、
- DUCTの候補手が多すぎて全然収束しない
- 何も考えずランダムプレイアウトするとSEEDばかり選ばれて、現実には起こらない種だらけの盤面になりがち
といった問題が出てきて、これをどうするかが悩みどころでした。
紆余曲折ありましたが、最終的に以下のようなAIにしました。
- 評価方法
- 評価関数は使わず、ゲーム終了までランダムプレイアウト（枝刈りあり）を行う。*2
- 勝ちを1点、負けを0点、引き分けを0.5点として報酬とする。ただし僅差で勝ちを確信していたにも関わらず読みが弱くて逆転負けする事態が散見されたため、僅差での勝ちは0.8～0.9点に減点する。
- ノードの選択にはUCB1-Tunedを用いる。*3
- UCB1-Tunedの第2項を自分と相手で交互に0にする。
- 前のターンで展開していたノードを使い回せるなら使い回す。*4
- 選択肢の枝刈り
- 盤面に既にSEEDがある場合はSEEDしない。
- 序盤は自分の木に隣接するマスにはSEEDしない。*5
- 中盤以降は若干条件を緩和し、SEED元の木に隣接するマスにはSEEDしない。
- Σ（木のsize）がターンごとに決められた一定値未満の場合はCOMPLETEしない。
- 最終日は基本COMPLETE。同点の時の競り合い用にSEEDも。
とにかくSEEDの選択肢を減らすことを考えました。SEED以外の枝刈りは最終的にほとんど行っていません。ルールベース的な枝刈りはたったこれだけしかやっていないにもかかわらず、勝手に強い手を打ってくれるようになったので、モンテカルロ木探索すげー！と一人で感動していました。
日記
日記（1-indexed）です。やったこと垂れ流し。
1日目
Woodリーグで既にルールの把握に一苦労。とりあえず適当に動くAIを作った上で、IOや構造体などの環境整備を進めました。
2日目
Bronzeリーグになってルールが全解放されたものの、評価関数をどうしたらいいのか全く分からないので、モンテカルロ木探索を採用する方針に。とはいえモンテカルロ木探索なんて書いたことないので、まずは本を買って勉強から始めました（今更……？）
購入したのはこちらの本。三目並べでモンテカルロ木探索を使うPythonコードが載っていたので、まずは写経から始めました。
3日目
モンテカルロ木探索についてなんとなく理解したので、実装してみます。同時着手ゲームにどう適用するんだと悩んでいたところで、valさんのブログでDUCTの存在を知り、論文とにらめっこしつつ実装。最初は何も工夫していなかったのでめちゃくちゃ弱かったんですが、SEEDの枝刈りを入れたら一気に強くなって4位になりました。モンテカルロ木探索すげーという気持ちに。
4日目
このあたりでSEED時に木と木の間隔を空けるようにした形跡があります。ガチ林業かな？
5日目
だんだん進捗がなくなってきて、git revertが増えてきます。このコマンドには最後までお世話になりました……。
デカめのバグを見付けたので修正すると、弱くなりました。あるあるですね。これはパラメータがバグ前のコードに最適化されていた結果のようで、調整し直すと普通に強くなりました。
6～7日目
微改善を続けます。最後まで残ったものもあり、消えたものもあり。まあ消えたものの方が圧倒的に多いですね。しょうがない。
8日目
DUCTがこわれていることにようやく気付きます。UCB1戦略ではまず最初に全選択肢について1回ずつ試す必要があるのですが、初回実行待ちキューの意図しない要素を削除してしまい、永遠に選ばれない選択肢が発生してしまっていました。
修正することで25位から10位に上がります。むしろなぜこれで今まで戦えていたんだ……？
9日目
UCB1-Tunedを実装。どうなるかなと思っていましたが、思った以上に明確に強くなって驚くなど。一時的に1位を取ってウキウキ。
10日目
reCurseさんが突如圧倒的強さを見せつけて1位へ。コンテスト終了後に聞いた話ではニューラルネットワークを使っているとのこと。かなり研究されていたんだろうなあという気持ちになります。
11日目
最後の悪あがきで自己対戦とパラメータチューニングをして、終わりです。システスが走って6位フィニッシュ。
感想
Codingameの過去2回のコンテストではいずれもGoldリーグ止まりだったので、まさかここまで戦えるとは思っていませんでした。しかも付け焼き刃の知識で……。運良く早めに当たり方針を引けたので、試行錯誤したりバグ取りしたりバグ取りしたりする時間が取れたのが大きかったですね。あと日本勢的には開催期間がGW終盤にかぶってくれていたのもプラスに働きました。
今回初めてモンテカルロ木探索を勉強して実装したわけですが、想定していたよりも圧倒的に賢くてかなり驚きました。例えばこのゲームでは、相手の木を自分の木の陰に入れるとSUNポイントの妨害ができておいしいのですが、ルールベースで教えずともいいポジションに種を蒔いて育てて相手を妨害し、相手に妨害し返される前に伐採する……なんて動きを勝手にやっていて感動しました。
あと今回はTwitter上の情報交換が活発でしたね。自分自身もbit演算の活用法など色々と勉強させてもらいました。界隈のレベルアップにも繋がりますし、自分としてもどんどん情報発信して盛り上げていきたいところです。
次は秋ですね。一発屋にならないよう秋も頑張ります……！
*1:と思うじゃん？実は評価関数作れる人は作れちゃうんですねえ。
*2:序盤でだいたい3000プレイアウト/100msくらいになりました。
*3:UCB1より計算が重くはなりますが、収束性が良くなる分特にDUCTでは有効な気がしています。
*4:だいたい7～8割くらいはキャッシュヒットしていた印象です。ただ、「一度でも展開したことがある」と「その子孫ノードを深く読んでいる」の間には大きな乖離があるので、展開していたからといって思っていた通りの展開になるとは限りません。それでも、1ターン目は1000ms探索に使えること、序盤の選択肢は比較的少なく展開がばらけづらいことから、それなりに効果はあったのではないかと思っています。
*5:初手WAITがTwitterで話題になっていましたが、この条件を入れることで自動的に満たされます。初手WAITが強いというよりも、隣接位置に種を植えるのが弱いのかなあという気がします。
