CodinGameのコンテスト、Green Circleに参加しました。
お題はちょっとゲームバランス偏り気味なゲームAIです。
結果はGoldリーグで、全体1758人中92位でした。
（今回の記事はゲーム内容への言及薄めで、実装寄りのお話が多いです）
問題
システム開発に役立つスキルを取得して使いながら、5つのアプリをリリースしてね。
（デッキを強化して勝利点を5点取ってね）
4リリースまでは技術的負債（ペナルティカード）を受け取ることで条件の穴埋めが出来るけど、5リリース目は完全に条件を満たさないと駄目だよ。
詳しいルールはツカモさんが翻訳記事を書いてくださっています。いつもありがとうございます。
元ネタはボードゲームのSamsaraで、有名どころだとドミニオンなどが近いようです。
私はどちらもやったことが無いのですが、たまたま最近やや近いゲームをやったことがありました。近いと言ってもデッキ構築なだけですが。
考察
これは実装が重いやつ。（明文化されていないルールも多く、調査も辛い…）
そして、勝ち筋が少なくて…ほぼ1本道が2本あるくらいでは？
おまけにジャッジもビジュアライザもバグが多く。何が正しいのか分からーん。
うーん、これは楽しく取り組めそうにない。
ということで、今回はランダムを交えたMCTSの練習として取り組むことに。*1
まず何をどう探索するの？という問題はあるのだが、*2今回は相手の行動を詳しくシミュレートせず、自分の5回リリースの速さを評価する探索とした。ランダム部分については、観測結果を受けて次の行動を決めるという動きにしたかったので、カードをドローしたタイミングでドロー内容で分岐することにした。相手の動きは相互手番風にすると相手がリリースを目指さずこちらの邪魔を目的にする不思議探索になってしまうので、相手の動きもランダムにした。*3
実装（構成編）
まずはシミュレータを書いて、原始モンテカルロ法をするところから。
ゲームシミュレータがとても重いことと、順位を最終目標としていないことから、今回は速度重視でベタ書きな†Technical Debt†コードではなく、メンテナンスしやすいものを考えて作っていく。*4
まず、分岐点となる状態（プレイヤーがコマンドを送信する状態や、ランダムなドローが発生する状態など）をGoFのStateパターンで実装する。GameStateと名前がややこしいのでPhaseと呼ぶ。Phase構成は、以下の通りとした。
Move→Throw→Give→Skill(PlayCard)→Release→EndDraw(ターン終了時のドロー)→OppTurn(相手ターン)→Move
別枠で、SkillDraw（traningやcodingによるドロー）がSkillと相互に遷移する関係として存在する。
各Phase（Throw, Give, Skill, Release）は、行動やゲームエンジン側の判断により飛ばされることがある。基本は一本道なこともあり、遷移先を判断するよりも、遷移先でPhaseが存在するか判断した方が楽そうだった。
Phaseには入口処理であるEnter()と、出口処理であるExit()を作る。
例えばSkillPhase（ルール上での呼称はPlayCard）のEnter()ではMoveによるカードを入手したり*5、ThrowPhaseのEnter()ではThrowが無い場合や強制支払いがある場合に即GivePhaseに行ってねという追い出しを行ったりする。*6
Exit()では次のPhaseへの移行を行う。基本的にはPhaseに応じた行動を何かする度にExit()すべきかを判断するので、その判断を行うTryExit()を用意して、行動の度にそちらを呼び出す。Exitしないケースとしては、SkillPhaseはcodingの効果により使用回数が残っていると、行動後もSkillPhaseに留まる。
終わってみての反省点だけど、SkillPhaseの前にMoveによるカード入手だけのPhaseがあっても良かったかも。別に分岐点でしか状態を作ってはいけないわけではないし、SkillPhaseが始まったら移動によるカードを入手するというのはなんか直感的じゃないので。あとはスキルの使用回数もそっちで初期化すれば、skill使用後も留まるのを自己遷移としても表現できた。*7
少しネックになるのはジャッジ側の指示により途中状態（SkillPhaseなど）から開始されるケースで、この時にEnter()から入ってしまうと行うべきでない処理（移動によるカードの入手やスキル使用回数の設定など）が走ってしまうので、Enter()とは別口で初期状態に遷移しないといけない。複数手をインタラクティブで行う故の問題。特にGiveやPlayCardフェイズは残り回数が入力で与えられないので、ここはかなり美しくない実装になる。
あとは各Phaseは、合法手の列挙（選択用か確率用）、プレイアウトを行うための関数*8を持つ。シミュレータはGameStateのNextPhaseメンバに対してそれらの指示を出す。Phaseはそんな感じ。
各行動（Move, throw, 各skillなど）による効果はGoFのCommandパターン。割愛。
Phaseのプレイアウト関数も別関数からCommandを取得し、それを実行する形にすると良かった。というのも、今回は枝が多そうなのでThrow,Give,Skillなどがほぼルールベースで固定の動きをするだけだったのだが、そうなるとジャッジに出力を返すときにルールベースで同じ判断を行わないといけない。その行動の取得をプレイアウトと共用にすれば、二重管理を防ぐことができる。
こうして原始モンテカルロで動いたら、改めてMCTSに改造する。といういつものパターン。
実装（ゲーム編）
特に工夫した点。
ドローによる分岐
ターン終了時のドローはカード10種類に対して標準4枚（最大9枚）と非常に組み合わせ数が多い。これら全てを分岐すると展開が間に合わない*9ため、20回サンプリングしてそのいずれかに飛ばすことにした。ケースによっては実は20パターンも無いことがあり、その場合は真面目に計算した方がいいのだが、今回はそのままスルー。
他の人の解法を見て
終局まで探索するタイプだと、相手の状態も仮定して動くMCTSが強いようだった。そこまで行くとランダムによる分岐がえぐそうなんだけど、木は全体で1つ作って、ドローによる盤面再生はその都度行うらしい。ばらばらの前提から分岐するので滅茶苦茶になりそうなんだけど、UCBの計算するときに親の探索数をそれらしい値に設定するといいとか。
感想
楽しいコンテストではなかったです。どちらかというとアンチパターン展覧会。
成績も今回はGold止まりでしたが、目的を決めてそれ自体は達成出来たので、たまにはこういう参加スタイルも良いなと思いました。
*1:もちろんLegend行けるなら行きたいの気持ちはあり。
*2:めっちゃ重要。
*3:正直方針としては良くないが、練習なので管理しきれるものにしましょうということで…。
*4:作り始めた時点ではまだバグが酷かったり、バランスの再考の必要性が囁かれていたりで仕様も怪しかった。
*5:Throw, Giveの時点ではまだカードを入手していないため、入手タイミングはここになる。
*6:1択の行動を行って抜けるという方法もあるが、強制支払いはPhaseが存在せず内部的に処理されるという挙動も再現するためこうした。
*7:それが美しいかは別。
*8:メソッド。
