Fall Challenge 2020 参加記
2020/11/25 追記:
・１手先全探索について書き忘れていたため追記しました。
・後日談１を追記しました。
問題概要
CodinGameのFall Challenge 2020というコンテストに参加しました。
ゲームの雰囲気は以下のリンク参照↓
おばあちゃんにポーションを作らせるゲーム。中央にある本から呪文を習得し(Learn)、呪文を使って材料を強化し(Cast)、材料を調合してポーションを作って客に売り(Brew)、ルピー(=Score)を得る。どちらかのおばあちゃんが６つ売った時点でルピーをたくさん持っているほうが勝利。
元ネタは『センチュリー：スパイスロード』というボードゲームらしい。
ルールの詳細は以下のツカモさんの記事に全て書いてある。圧倒的感謝。
結果
世界３２位（日本５位）
ゲームについて考察
どんな探索木を使うか
相手の行動が探索にどのぐらい影響するのかちょっとよく分からないが、影響を受ける行動はLearnとBrewだけなので影響は小さそう*1。とりあえずChokudaiサーチ＋敵の行動予測で書いてみる。
盤面評価をどうするか
スコアが高いほうが勝ちなので、スコアを最大化すればよいことはすぐに分かる。スコアが変動しない行動をどう評価するかは、以下のように考えられる。
ポーションのスコアをよく見ると『必要素材のTier-0～3をそれぞれ1～4点とした合計点』とほぼ同じに設定されている*2。よって、イベントリにある素材のTierを１つ上げることは将来的にスコア１点を得ることに繋がると考えることが出来る。
以上のことから、イベントリを１ターンにたくさん強化出来る行動が優秀と判断できる。この考え方で呪文の評価値も決められそう。
Brewは手持ちのイベントリの価値をスコアに変換し、イベントリに空きを作るための行動と考えることができる。
最終提出プログラムの内容
先に書いた考察をふまえ、最終的に出来上がったプログラムの内容を紹介する。
１．アルゴリズム
Chokudai Search１５ターン読み。
まず相手視点で5msだけ探索を行う（自分の行動は全てWAIT）
次に自分視点で探索を行う。このとき相手の行動の１手目だけを実行する。（２手目以降は実行はしないが、評価関数や終了時の勝敗判定で使う）
盤面評価は１ターンに25000～40000回程度だった。
２．行動選択
Learn、Cast、Brew、Restを全て含む。
回復する呪文が１つも無いときにRestはしない。他は特に制限はかけていない。
2020/11/25追記：
Chokudai Searchをする前に１手先全探索を行い、自分が負ける可能性がある行動は除外した。ただし、何をやっても負ける可能性がある場合は除外しない。
３．シミュレーション
ほぼ変えてなくてそのまま実装しただけ。
ゲーム終了時の勝利判定だけは変更を加えており、相手のターンごとのスコアは先に相手視点で探索したときに計算済みのため、それを使って勝敗判定をする。
４．評価関数
以下の８つの評価値を計算した。
①勝利したターン
勝利ターンの早さ×5000兆点。早いほうがよい。
②実スコア
実スコア×1.1倍。1.0倍だとポーション購入のメリットがなさすぎて全然ポーションを買ってくれなかったため
③イベントリの評価
Tier-0～3を1～4点として評価。ただし、イベントリが高Tier素材で埋まることを避けるために、Tier-2は8つまで、Tier-3は6つまでしか評価しない（有効だったかどうかは不明）
④呪文評価
呪文評価＝基本評価×max(1, 6-購入ターン)÷5.7333
基本評価＝Tier-0～3を1～4点として評価×最大Repeat回数
基本評価は例えばDelta={-2,2,0,0}の呪文は5回Repeat出来るので(1*-2+2*2+3*0+4*0)*5=10点となり、かなり強い呪文。
購入ターンはゲーム開始時を0ターン目として、開始６ターン以内に取得した呪文の評価を大きく上げる役割。
5.7333は全ての呪文の基本評価の平均値で、実スコアと呪文の価値のバランスをとるための定数。
⑤イベントリの空き
-0.5×abs(5-イベントリの空き)
空き５つのとき0点，4つや6つのときは-0.5点，...
イベントリ満タンのときはポーションを買って空きを作るが、イベントリ５つとかのときにポーションをあまり買わないようにする。イベントリが空になるとその後弱いため。
↓↓↓以下は効果が小さかったもの↓↓↓
⑥素材種類ボーナス
イベントリに素材が３種類あれば＋１点、４種類あれば＋２点
ポーションの価値がそうなっているのでイベントリもそうしたが、有効だったかどうかは不明。
⑦詰みペナルティ
詰んでたら-50点
詰み判定は、『初期呪文をどれだけ使ってもどのポーションも購入できない状態』を詰みとした。
⑧妨害ボーナス
探索開始ターンから５ターン以内に敵が購入予定のポーションを先に購入できたらボーナス。逆に敵に先に買われる場合はマイナスにする。ボーナスの値は控えめに『ポーションスコア×0.2点』。
５．Learnの先取り
ゲーム開始６ターン以内のみ、シミュレーションの結果を見て、そこから５ターン以内にLearnをする予定がある場合、それをこのターンに実行する。
シミュレーションでは相手の行動をほぼ考慮していないため、使いたい呪文は使う直前にとるという感じになっていた。しかしそれだと欲しい呪文が相手に先にとられてしまうため。
６．盤面重複除去
Zobrist Hashingを使った。これをやったらかなり強くなった。このゲームは盤面重複がとても多く、例えば無コスト呪文は他の呪文と入れ替えても同じ結果になるし、RestやBrewと関係ない呪文Castの位置が入れ替わっても結果は同じになる。
試したけどダメだったこと
Decoupled UCT
同時着手ゲーム用のMCTS。敵の動きを全部考慮すると深く読めないので弱かった。終盤にだけ使うとかしてみたけど、終盤はもうほぼ勝負が決しているので意味がなかった。
ビームサーチ
なにも変わらなかった。priority_queueの出し入れのコストが減るぶん速くなるかと思ったが、なにも変わらなかった。（なぜ？）
敵が勝利するターンで探索を切る
強くなりそうなのに、なぜ効かなかったのか不明。もしかしたらこれも、敵が先に勝利出来るという時点で負けがほぼ確定しているからかもしれない。
負けそうになったら妨害に特化
終盤に不利が分かってから足掻いても無駄。相手が欲しいポーションを先に買っても、ポーションの選択肢は５つもあるので他の作られておしまい。
Tomeにある呪文をそのまま使用可能としてシミュレーションし、その結果を見て必要そうな呪文をこのターンに取得する
実装が破滅（先読み税ぇ…）
感想
盤面重複除去をやって満足してしまい高速化をまともにやらなかったのが敗因かなと思います。強い人の半分以下の盤面しか読めていませんでした。
今回のゲームは相手プレイヤーとの相互作用がかなり小さく、どちらかと言えばゲームというよりマラソン寄りの問題だったように思います。私は対戦ゲームにおいては相手の妨害をすることしか頭にない人なので、今回のゲームは少し相性が悪かったかなという感じです。
いつもと比べたら結果はあまり振るいませんでしたが、思いついたことは全部試したし全力は出せたので悔いはないです。
あと日本人参加者がめっちゃ増えてて素晴らしい。
後日談１ (2020/11/25)
コンテスト終了後に改善を行い、順位が９位に上がった。
以下の２つの改善をした。
１つ目は、他の人の参加記でよく見かけた『ポーションの醸造にボーナスを与える』というもの。これはそのままやっても強くならなかったが『３つ目以降のポーションの醸造にボーナスを与える』としたら強くなった。ボーナスの量は
３つ目：＋３点。
４つ目：＋５点
５つ目：＋１０点
６つ目：＋２０点
とした。全部＋５点にしてもだいたい同じ強さだったのでボーナスの量はあまり関係ないらしい。
これがなぜ効いたのかはっきりとは分からないが、おそらくポーションの醸造回数で相手に負けないようになったためだと思う（醸造数が相手より少ないことは明らかに不利なため）。一方で序盤からこれをやると、早くポーションを作ろうとすることは長い目で見ればスコアを得る最短経路ではないため、スコアを稼ぐスピードで負けてしまうので結果的にスコアで追いつけずに負けてしまう。
これをやって順位が30位→15位に上がった。
２つ目は呪文の価値の変更。pb4さんのPost-Mortemにあった呪文の価値に書き換えた（単体のほうのみ。複合のほうは未使用）。この評価値はローカル環境で自己対戦を繰り返して決定したらしい。ランダムに７つの呪文を与えて２２ターンのゲームを行う、これを50万回繰り返し、各ゲームで得たスコアをそのゲームで持っていたスペルの評価に加えていく、というようにしたとのこと。私はその結果をコピペしただけで何も偉くないので、同じような結果を自力で導けるように挑戦したい。
これをやって順位が15位→10位に上がった。
