CodinGameのFall Challnege 2020に参加しました。
www.codingame.com世界 190/7036位
日本 56/320位
でした。日本人がおかしい。
ゴールドリーグのやや上位といったところで、残念ながら目標のレジェンドには届きませんでした。
ゲーム概要
tsukammo.hatenablog.com企業系Wiki、もといツカモさんのブログが詳しいです。いつもありがとうございます。
ボードゲームのセンチュリー：スパイスロードのパクリオマージュでしたね。ただし先手後手の概念を外して同時着手ゲームになっています。
ゲーム分析
基本的にボードゲームの攻略がそのまま流用できそうです。CASTでデルタ評価を増やしていき、途中でポーションという形に清算するゲームだと思いました。最速でポーションを作るよりも、上位デルタを残しておいて分解呪文で復帰するのが強いですね。
ポーションの先取り合戦要素もあり、同時着手の中で読むのは難しかったです。
私はこのゲームのコンセプトは「価値が流動的に変わる環境の中で最善を選ぶ問題」だと考えていて、評価関数による静的な評価が難しいことから探索部分の作りこみが肝だと思っていましたが、LEARNについては先が見えない状態で評価しないといけないことや、枝刈りもしないといけないことから評価関数も頑張らないといけない問題でしたね。
私は最終的にビームサーチ（BFS系列）で挑みましたが、コドゲ公式のタグはMonte Carlo tree search、BFS、graph traversalとなっており、好きなアプローチで挑める問題だったようです。
やった事
Wood2
一番高い注文をこなす。
Wood1
先頭の注文をこなす。
低Tierデルタからチェックし、それ以上のデルタが不足していたら生成・アップグレードする。出来ることがなければRESTする。
Bronze
ここでシミュレータを書く。
ついでに原始モンテカルロでシミュレートできるようにして、各コマンド毎に勝率計算して一番勝てるものを採用。CASTはRepeat回数毎に分解して別コマンドとした。
シミュレータではBREWやLEARNの補充はランダムに行った。（補充ルールは明記されていなかったのでサーバを解析した）
序盤はターン毎に100戦弱、50ターン目で300戦程度シミュレートできた。
先頭5ターンはLEARN固定にしてみたけどさほど効果は無かった。
Silver
10ターンLEARN→ビームサーチ(幅400)→4回BREWしたらモンテカルロという方法を取った。これはビームサーチに終盤の勝敗を考慮する機能を積んでいなかったため。
評価関数は[獲得済点数＋デルタ＋呪文]とした。デルタはターン毎に減衰し、Tier2とTier3は注文も考慮して一定数以上は評価しないようにした。*1呪文評価は最大Repeat時に何点稼げるかと、4点行動で獲得済点数＋デルタが80点取るには何回呪文をCASTする必要があるかで決定。*2Tierの偏りを防ぐため、Tier毎の生成数と消費数をチェックして偏りをもつ呪文にペナルティを与えた。*3
ビームサーチシミュレータは相手は動かず自分だけ動くシミュレーションで、BREWやLEARNの補充は行わなかった。
Gold
重複する枝の抑制のため、直前の行動から次の行動を制限した。ノードを合流する方法はオブジェクトの生成自体を抑えられないため行わなかった（言語と速度的な都合）
基本的にはBREW、LEARNは急がないと相手に取られてしまうケースがあり、ビームサーチにおいては評価の低い行動が枝狩りされやすい。そのためBREW・LEARN＞強いCAST＞弱いCAST＞RESTの優先順で行動するようにした。
以下のルールにより、初期呪文の1点行動も探索への影響を小さくしつつ考慮できるようになった。ビーム幅400で、毎ターン10000ノードで10手くらい。
- REST直後はRESTにより復活したCASTしか行わない
- 順番を前後可能なCAST→CASTは、稼げる点数が多い順にしか行わない（同点はidが若いものを先に使うことにした）
- CAST→LEARN、CAST→BREWはCAST実行前にも可能なら行わない
- RESTから2ターンはREST禁止（これは重複ではないが、あまりに弱そうなので省いた）
ゲーム終了の概念を入れる。とはいえ、ゲーム完了と未完了を上手く区別しながらビームサーチする方法は浮かばなかった。そのため、6個BREWしてシミュレーション開始時の敵点数に負けていたら絶対に勝てないので-100点。逆に勝っている場合は、1ターン早く終わらせるごとに相手の行動を1個減らせるのでターン毎に+4点（自分はRESTしかしない）とした。
探索中のゲーム終了判定とは別に、１手詰めや２手詰めもある程度行った。これが出来るようになったので、モンテカルロシミュレータは廃止した。モンテカルロは原始的なものだと勝率100%になり、負けの可能性が出てくるまで緩い手を打ち続けて負けてしまう弱点があった。
ポーション先取り合戦の要素として、相手の行動をそれとなく考慮した。そのターンに可能なBREWは次ターンでは不可、そのターンに可能なBREWがなく次ターンに可能なBREWがあれば２ターン後に不可とした。
やりたかった事
ポーションまでの距離数を、 もう少し長い距離まで探索したかった。
ビームサーチで多様性を残すための工夫を入れてみたかった。
何も分からんだった事
LEARNの評価。何を何回使うのが最善か、を計算できればもう少しリアルな評価関数が書けた気がする。動きを制御するための作りこまれた評価関数も美しいと思いますが、個人的には評価関数は事実に近いのが良いと考えています。
没戦略（噛み合わなくて廃棄）
呪文評価(1)
インベントリのパターン1001通りに対しての呪文評価を付け、その平均を呪文評価とする。また、同様に呪文同士のシナジー*4を計算し、手持ちの呪文同士のシナジーの総和も評価に加える。3色構成みたいな歪なLEARNになりやすく、また1001パターンも出現頻度が違ううえに呪文はRepeatできるように工夫して使うものなのでリアルじゃなかった。
呪文評価(2)
呪文評価に応じて重みを付け、想定使用回数を強力な呪文ほど多くする。ついでに下位互換互換の重みを低くしたり、個人的に気に入らない呪文を補正したり。これは上位に刺さりやすい一方で下位に負けやすく、大成功と大失敗に偏りやすいようだった。
没戦略（ネタ寄り）
３色デッキ
あえて１色を捨てて３色で統一する。デルタのTier混成状態はRepeat呪文の効率が悪いため。しかしポーションに特定の色を含むかはほぼ半々なので、注文の半分をこなせなくなるのは痛く、特に相手の状況を読んで先回りするタイプには弱いと判断。
魔導書をTier0銀行的に利用する
引き出しが面倒くさいし結構盗まれる。普通に探索中に考慮するので没ではなかった。
何もしない
実は何もしないのが正解のケースがあり、相手がトライフォース職人で行動不可かつ自分が獲得済み得点で勝っている場合は、下手にBREWしてTier3の消費先を出すよりもCASTとRESTだけして待ち続けた方が強い。しかしまあ、Gold上位ではなかなか無いケースだし相手が固まっていればそもそも自分有利だしで、優先して実装するものではなかったよねと。
総評
デルタのTier毎に[1,2,3,4]点という基準があり、適当にビームサーチを書くところまでなら楽で面白かったです。LEARNの構築やBREW争奪戦になると一気に想定できない域に入ってしまい、相性もあるのでここで完全に足止めされてしまった。
上位の人の考察を聞いてもLEARNはやっぱり何も分からんという感じで、実装要素はありながらも考察ゲーの部分が大きかったのかなと思いました。考察力を鍛えにはどうしたらいいのかな。
シミュレートの確度が下がるごとに報酬を下げるというのは前回のPACでもあったパターンなので、数をこなしてパターンを覚えるというのも１つの手段ですね…。
蛇足
お婆ちゃんネタ
このゲームは自キャラであるお婆ちゃん*5を操るゲームであり、開催中のTwitterではこの設定に乗っかったネタ発言が多く見られました。お婆ちゃんが動かなくなった、お婆ちゃんを改造する、お婆ちゃんの感度を上げる、etc…。
凝ったキャラ設定*6とビジュアライザがあり方針の言及も出来るコンテストなので、こういった楽しみ方も出来るのはいいですね。
TCGネタ
開催中、TwitterではこのゲームをTCGに例えて戦略を話す光景がよく見られました。元々TCG用語でもデッキタイプに厳密な定義は無いことが多いのですが、私はこんな感じで使ってました。
アグロ：相手のLEARNが済む前に動き始め、相手が回り始める前に決着を付けるタイプ。*7
ランプ：膨大なデルタを操り、特にBREW後に残したTier3から再始動するタイプ。*8
パーミッション：相手が取りたいBREWやLEARNを取り、相手の動きを妨げるタイプ。*9
実装は苦しい点もありましたが、お祭り的にわいわい楽しめるコンテストでした。
以上となります。
