解法概要

EMアルゴリズム（Expectation-Maximization algorithm）により AI の内部パラメータを推定しました．
M-step での最適化には Adam（Adaptive moment estimation）を用いています．
また， 最適化するパラメータと選択確率とを結びつける関数としては，温度付きsoftmax関数を採用しました．

自分の手の決定は UCB1（Upper Confidence Bound 1）を使用した MCTS（Monte Carlo Tree Search）により行いました．
その際 AI の行動予測に EM で推定しているパラメータを活用しました．

（AHC061 - AtCoder Heuristic Contest Statistics の \(M,U\) （プレイヤー数，レベル上限）別ヒートマップによると，入力によってかなり得意不得意に差があったようです．
\(M=2\) では 300 位前後，\(U=1\) では \(M\ge 4\) で 1 桁順位，\(M=7,8\) で 2 位となっていました．）

解法詳細

状態管理

情報の持ち方

盤面に関する情報のうち，01 で表せるものについては __uint128_t の下位 100bit で管理します（以下 \(b\) で表します）．
各マスのレベルと所有者に関する情報は array<uint8_t> の 4bit ずつで管理します．

盤面全体で

• レベル最大のマス \(b_{max}\)
• プレイヤーが存在するマス \(b_{exist}\)

の情報を持ちます．

また，各プレイヤーで

• 現在地とスコア
• 所有するマス \(b_{owned}\)
• 現在地と連結する自陣マス \(b_{connected}\)
• 到達可能なマス \(b_{reachable}\)

の情報を持ちます．

選択可能なマスを \(b_{reachable} \And \sim b_{exist}\) で取得したり，そこから \(b_{max}\) を除いて価値のあるマス \(b_{worth}\) を抽出したりできます．

情報の更新

\(b_{connected}\) を得るためのBFSは，現在地 \(b_{pos} (1 \ll pos)\) からはじめ，変化がなくなるまで上下左右への全体移動を意味するビットシフトなどと \(\And b_{owned}\) とを繰り返すことで行えます．

あるマスを自陣に加えたとき，その4隣接に \(b_{owned} \And \sim b_{connected}\) が存在した場合には更新が必要です．
\(b_{connected} \mid b_{pos}\) からスタートし，BFSを行います．

一通り加えた後，削除を行います．
あるマスが自陣から削除されたとき，更新が必要であればその8隣接の連結状態が変化します．
一通り削除し更新が必要な人についての情報をまとめた後， \(b_{pos}\) からスタートし，BFSを行います．

8隣接の連結状態の変化については，前もって \(2^8\) 通りそれぞれで変化するかどうかを計算し，埋め込みました．
また，8隣接の状態については，中心を \((1,1)\)（11bit目）へとビットシフトすることで 23bit 以内に情報が収まり，必要な場所だけマスクをした後，7bit シフトと 14bit シフトによって 9bit へまとめることができます．
各マスに対応する必要なシフト数とマスクについては，あらかじめ計算をし埋め込みました．

また，環境依存ですが _pext_u32 を使用することでより簡潔に求められるようです．
（横幅を 11bit として扱うよう変更する必要がありそうだったため，変更コストが上回ると思い断念しました．）

EMアルゴリズム

AI の行動原理を，温度付きsoftmax関数に従う貪欲選択とランダム選択との混合モデルとして考え，E-step と M-step とを交互に繰り返すことでパラメータを推定します．
（はじめは粒子フィルタによる推定を行っていたのですが，最終的にこちらの方が推定の挙動が良く，正しく推定できているようだったので変更しました．）

E-step で潜在変数として各選択がランダム由来であった確率を計算し，それを元に M-step でパラメータを更新します．
1回の EM ごとにパラメータはその生成範囲でクランプします．

各ターンで観測した情報は

• 合法手内でのマスの価値のカテゴリ毎の最大値 \(/1000\) （\(=:v\)）
• 選択されたカテゴリ
• カテゴリ内で最大のマスの価値の場所が選ばれたか
• 合法手数

に変換し，履歴として保管します．

E-step

ターン \(t\) での選択がランダム由来であった（\(z_t=1\)）か，パラメータを元にした貪欲によるものであった（\(z_t=0\)）かを推定します．

具体的には，パラメータ \(\boldsymbol{w}, e\) のもとで，ターン \(t\) での選択 \(a_t\) がランダム選択によるものであった確率

\[ \gamma_t = P(z_t=1 \mid a_t, \boldsymbol{w}, e) \]

を計算します．
（\(a_t\)がその時のカテゴリ内最大価値の行動でない場合は，貪欲選択の対象となり得ないため \(\gamma_t = 1\) です．）

ここで，\(z_t=1\) であった場合や \(z_t=0\) であった場合に，（カテゴリ内最大価値の行動である）\(a_t\) が選択される確率は，選択肢の数を \(n_t\)，カテゴリを \(c\) とし，温度（\({\beta}\)）付きsoftmax関数を採用すると以下のようになります．

\[ \begin{aligned} P(a_t \mid z_t=1) &= \frac{1}{n_t} =: p_{1,t} \\ P(a_t \mid z_t=0, \boldsymbol{w}, e) &= \frac{\exp (\beta w_{c_{a_t}} v_{c_{a_t}})} {\sum_{c} \exp(\beta w_c v_c)} =: p_{0,t} \end{aligned} \]

これを使用し，

\[ \gamma_t \leftarrow \frac{ep_{1,t}}{(1-e)p_{0,t}+ep_{1,t}} \]

によって \(\gamma_t\) を更新します（ベイズの定理）．

M-step (\(e\))

履歴のサイズを \(T\) とし，

\[ e \leftarrow \frac{1}{T} \sum_{t=1}^T \gamma_t \]

によって \(e\) を更新します．

M-step (\(\boldsymbol{w}\))

ランダム由来確定の選択しか行われていない場合には実行しません．

一連の選択をより良く説明できるような \(\boldsymbol{w}\) について考えるため，各ターンの対数尤度をそのターンの選択が貪欲によるものであった確率（\(\boldsymbol{w}_{old}\) をもとに E-step で考えたもの）で重み付けした以下の期待値について考えます．

\[ Q(\boldsymbol{w} \mid \boldsymbol{w_{old}}) = \sum_{t=1}^T (1-\gamma_t)\ln p_{0,t} \]

これを各パラメータで偏微分した勾配は，（softmax の式を入れて計算をすると）

\[ \frac{\partial Q}{\partial w_c} = \sum_{t=1}^T (1-\gamma_t) \beta v_c(\mathbf{1}_{\{c_{a_t}=c\}} - p_{0,t}) =: g_c \]

となり，実際に観測された選択とパラメータからの予想との差に重み付けをして足し合わせた形になっています．
勾配のスケールを履歴サイズに依存させないため， \(\sum(1-\gamma_t)\) で割って重み付き平均の形にしておきます．

この勾配をもとに Adam を用いて \(\boldsymbol{w}\) を更新します．

過去の更新時の情報を引き継ぎ学習率などを調整してくれる勾配の一次モーメント \(m_c\)， 二次モーメント \(v_c\)，過去の更新時の情報の利用度合いを調整する \(\beta_m\)，\(\beta_v\)，学習率 \(\alpha\)，EMステップの実行回数 \(t_s\) を使用し，

\[ \begin{aligned} m_c &\leftarrow \beta_m m_c + (1-\beta_m)g_c \\ v_c &\leftarrow \beta_v v_c + (1-\beta_v)g_c^2 \\ \hat{m_c} &= \frac{m_c}{1-\beta _m^{t_s}} \\ \hat{v_c} &= \frac{v_c}{1-\beta _v^{t_s}} \\ w_c &\leftarrow w_c + \alpha \frac{\hat{m_c}}{\sqrt{\hat{v_c}}+\epsilon} \end{aligned} \]

によって \(\boldsymbol{w}\) を更新します．

ハイパーパラメータ等

• \(\beta = 10.0\)
• \(\alpha = 0.005\)
• \(\beta_m = 0.87\)
• \(\beta_v = 0.995\)
• \(\epsilon = 10^{-8}\)

とし，カテゴリ内最大価値の選択が来るたびに \(\beta\) を 1.03 倍，\(\alpha\) を 1 / 1.02 倍しました．
\(\beta\) を上げることで徐々に softmax から argmax に近づけ，きつくなる勾配に合わせて学習率を少し下げています．

一つの観測ごとに EM は 20 回繰り返しました．

MCTS

各ターンで現在の状態を根として探索木を構築します．
（前ターンでの探索を（減衰させるなどして）引き継ぐことも試みましたが，スコアが下がっているような雰囲気があったため取り止めました．）
木の構築では自分の手のみを基準とし，基本的に価値のあるマス（\(b_{worth}\)）のみを対象とします．

1回の探索で，

1. 根から UCB1 に従って子ノードを選択していき，未展開の手が存在するノードを探す（Select）．
2. 未展開の手から1つを選び，その手に対応するノードを付け足す（Expand）．
   
3. ノードは増やさず決められた深さまでシミュレーションをする（Rollout）．
4. 評価値と訪問回数を経路に加算する（Backpropagate）．

を繰り返します．

ロールアウトは根からの深さ 12 までとし，ターンごとの実行時間を等間隔に区切ったところ，各ターン 2000 回ほど探索を行えました．
（プログラムの内容によって変わりますが，実行速度が体感 AtCoder の半分ほどであるローカル環境での計測です．）

状態を進める際の AI の挙動について

その時推定されている各 AI の内部パラメータに基づいて，問題設定と同じように選択を行わせます．

ランダム選択であった場合は，環境に依存しますが _pdep_u64 を使用することで立っているビットからランダムな1つを高速に選択することができます．
（上下 64bit ずつに分割し，popcount の総和以内で何番目を選ぶかを抽選し，対応する方で _pdep_u64(1<<k,mask) を行うと， mask 内で下から \(k+1\) 番目に立っているビットを残したものを得ることができます．
その後 countr_zero を使用すれば位置に変換できます．）

念のため同じ出力をする関数（\(k\) 回 mask &= mask-1 を行い mask & -mask を返す関数）にフォールバックするようにしましたが，コードテストでは正しく _pdep_u64 を使用できていました．

Select

根から（木に適用した）UCB1 が最大となるノードに対応する手で状態を進めつつ木を進んでいき，未展開の手が存在するノードを探します．

UCB1 は，現在いるノードの訪問回数を \(N\)，子ノードの訪問回数を \(n\)，評価値の和を \(value\) ，探索の幅広さを調整する定数を \(C\) として，

\[ \frac{value}{n}+C\sqrt{\frac{\ln N}{n}} \]

で表されるものです．

自分の手のみを基準に木を構築しているため，同じノードでも根から状態を進める際の AI の行動によって選択できる手は異なります．

Expand

未展開のものからランダムに選択します．

Rollout

根である状態から 12 ターン経過するかゲームが終了するまで状態を進めます．

自分の手の選択はランダムに行い，

• 50 %の確率で \(b_{worth}\) の外周から選択
• 35 %の確率でそれプラスひと回り内側から選択
• 15 %の確率で \(b_{worth}\) 全体から選択

とします．
そのような選択肢がない場合は下位の選択に移ります．
（広くなりがちな自陣において実際に各マスの評価を行うと時間がかかるため，このような選択になりました．）

Backpropagate

Rollout後の状態のみを基準に評価値を計算し，経路のノードに加算します．
（経路の状態についての評価を（重み付けするなどして）加算することも検討しましたが，スコアが下がっているようだったため取り止めました．）

評価値としては，AI トップとのスコア比の対数や自陣内・外の境界長さ， AI 同士の選択がぶつかり合う確率，AI トップの陣地と自陣との距離など，様々な要素を重み付けして足し合わせています．
（スコアのブレが非常に大きかったため正解がよく分からず，「こういうのが良さそう」の詰め合わせになりました．）

自分の手の決定

根の子のうち，最も多く訪問されていた手を選択します．
訪問回数が等しい場合は評価値の合計が大きいものを選択します．