【Suphx論文解説⑧】pMCPA
今回はSuphxの３つ目の機能であるpMCPAの解説です。
・Global Reward Prediction
・Oracle Guiding
・pMCPA(run-time policy adaption) （👈今回はココ！）
前半部分は麻雀プレイヤー向けの直感的な説明、後半はガチ勢向けの技術的な説明です。
まずは直感で理解する
麻雀プレイヤー向けのゆるーい解説を先に出しておきます。
突然ですがみなさん。配牌何切るです。
東3局東家、32000点持ちトップ目です。
みなさん、この配牌を見て何をイメージしますか？
「マンズや字牌が伸びればホンイツも見えるなー」
「3pを持ってくれば135のリャンカン形になるなー」
「バラバラだから安全牌を出来るだけ抱えておこうかなー」
こんな感じでいろんなルートを想像しますね。麻雀というのは配牌に大きく左右されるゲームです。好配牌ならブクブクで行きますが、配牌がバラバラなら引き気味に打つでしょう。
このように人間は単純な牌理だけでなく経験則やツモの伸び方を想像して最適解を選ぶことが可能です。
それに対して麻雀AIはどうでしょうか？
結論から言えば、Suphxも人間と同様に配牌からのツモの伸びをシミュレーションしてその局の方針を決定します。
未知の配牌にどうやって対応するのか
これまで解説したようにSuphxは人間の牌譜を学習データとして用いていますが、それだけでは未知の事象に対応できません。特に配牌時は情報が少ないため判断が困難です。
学習データに含まれていないような「バラバラな配牌」や「異常に整っている配牌」に対して一体どう対処すればいいのでしょうか？
これを解決するのが今回紹介する「pMCPA(Parametric Monte-Carlo Policy Adaptation)」というテクニックです。このような技術は一般的に”run-time policy adaptation”と呼ばれます。
run-time : プログラム実行時に（※ここではSuphxの起動時）
policy : 打牌選択の方策を
adaptation : 適応させる
という意味です。
このテクニックを導入することで
配牌に応じて打牌の方針を変化させる
ことが可能になります。
シミュレーションに応じて打ち筋を変化させる
ピンと来ない方はポケモンのイーブイの進化をイメージしてください。
詳しい説明はここでは省略しますが、イーブイというポケモンは進化の際にノーマルタイプから様々なタイプに変化することが出来ます。
Suphxはここまで極端に変化しませんが、開局時の配牌から数巡先をシミュレーションすることで与えられた配牌に対して最適な方針をとるように適合します。（この例え微妙かな…）
🤖「シミュレーションの結果、ホンイツに伸びる可能性がやや高いので字牌を残します」
🤖「シミュレーションの結果、ターツが少なくメンツが出来にくいので七対子本線で行きます」
🤖「シミュレーションの結果、メンタンピンが最短ルートなので役牌を先切りします」
こんな感じです。このシミュレーションは一局ごとに毎回行われます。前局のSuphxと次局のSuphxの打ち筋は同じではないということですね。
ちなみに先程の問題の答えは「9s」です。
見覚えのある牌譜だったかもしれませんね。最終的にこうなります。
Microsoftのプレゼンでも紹介されているSuphxの大三元です。
配牌時に「受け入れが少ないから」と字牌に手をかけるとここまで辿り着けません。pMCPAによって役牌が重なった未来を見ていたのでしょう。この大三元はpMCPAの賜物であると言えそうですね。
pMCPAはオーラスで真価を発揮する
「大三元なんて極端な例を出されてもいまいちピンとこないなぁ😗」と思う方もいるでしょう。
このpMCPAは実は
半荘終盤の条件戦に必須のテクニック
です。ラス前、オーラスで特に効果を発揮します。
これは論文中で取り上げられているシーンです。ダンラスで向かえたオーラスですが、着順アップのためには少なくともハネマンが必要です。
アガリだけ考えれば「西」を切るところですが、ハネマン条件となるとメンホンを見て「西」の重なりに期待した方が良さそうですね。Suphxも人間と同様なシミュレーションを行い、「西」ではなく「6m」を切ります。
このようにpMCPAは半荘終盤の駆け引きで真価を発揮します。Suphxのオーラス配牌何切るなどを研究してみると面白いかもしれません。
ゆるふわな説明はここまで。
ここから先は技術的な説明です。
モンテカルロ木探索
”モンテカルロ”というのはざっくり言えば
ランダムなシミュレーションによって解を求めるアルゴリズム
のことです。
モンテカルロ法で円周率の近似値を求める「ビュフォンの針」という問題が有名です。高校理系数学くらいの知識が必要ですが面白いので是非読んで見てください。
このモンテカルロ法を用いて最善手を求める手法がモンテカルロ木探索です。モンテカルロ木探索ではランダムにゲーム進行をシミュレーションすることで最善手を求めます。
Monte Carlo Tree Search (MCTS) in AlphaGo Zero | by Jonathan Hui | Medium
囲碁やチェスなどのゲームAIではよく用いられる手法ですが、麻雀は探索木の分岐数（盤面のパターン数）が膨大なため、そのまま適用することはできません。鳴きによるツモ順変更などを考慮すると特に大変そうですね。
何らかの対策が必要となりますが、このような問題に対してSuphxではpMCPA(parametric Monte-Carlo Policy Adaptation)という独自の手法を導入しています。
pMCPAによる方策適合
pMCPAというのはざっくり言えば、
配牌からのシミュレーションよって最適な打牌選択の方針を見つけよう
というテクニックです。
pMCPAの具体的な手順は以下の通りです。
1. シミュレーション（Simulation）
他家の捨て牌と次ツモ牌をランダムに抽出し、方策によって牌譜をシミュレーションする。これを全部でK通り行う。
2. 適合（Adaptation）
シミュレーションの結果をもとに、初期状態の方策をアップデートする
3. 推論（Inference）
改善したパラメータを強化学習エージェントに導入して対局を行う。
方策というのは事前に用意した学習データを用いて学習させた「5つの戦術モデル（のパラメータ）」のことです。論文中では"offline-trained policy"と表記されています。
上記のリンクによると、パラメトリックというのは「解析の対象データが何らかの分布に由来すると考える」という意味です。
おそらく、「方策（という確率分布）」によってシミュレーションするため、”パラメトリックな”モンテカルロ方策適合と名付けたのでしょう。これなら膨大な盤面パターンを全部調べる必要はなく、K通りのシミュレーションで何とかなります。
これで従来のモンテカルロ木探索の問題を解決出来ましたね。
数式で見るpMCPA
パラメータ更新は以下の数式によって行われます。
argmaxというのは「最大となるような変数を求める」という意味です。ここではθaが最大となるような変数θを考えようという意味です。
θは方策（5つの戦術モデル）のパラメータを表します。θoは"offline-trained policy"であり、更新前の方策パラメータです。θaは更新後の方策のパラメータです。（おそらくθaの"a"はadaptationの意味）
"τ（タウ）"というのは「行動の系列(trajectory)」のことで、麻雀で言えば「1. シミュレーション」で再現した「打牌パターン」のことです。牌譜の一部分を切り出してきたツモと打牌の並びをイメージしてください。”τ〜θo”は「パラメータθoという条件下で生成された打牌パターンτ」を表します。
hは配牌を表していて、τ(h)は配牌hからシミュレーションした打牌パターンの集合を意味しています。この集合は全部でK通りなので、ΣはK通りの総和となります。
Σの中のR(τ)は強化学習で出てくる報酬Rです。p(τ;θ)は方策θで再現した打牌パターンτに対する確率を表します。ざっくり言えば打牌に対する評価値だと考えてください。
与えられた数式のargmaxを考えるということは、要するに「K通りの報酬R(τ)の総和が最大となるθ」を考えればいいわけです。
p(τ;θ)/p(τ;θo)の部分がわかりにくいですね。
先程の「西」と「6m」の例で具体化して考えてみましょう。
分子 p(τ;θ) → 「5m」や「6m」を切った時の評価値
分母 p(τ;θo) → 「西」を切った時の評価値
p(τ;θo)は学習後そのままのパラメータθoによる評価値なので、愚直に「西」切りを選択します。確かに牌効率的に間違ってませんが、この局面では評価値は低く算出されるでしょう。
それに対して、シミュレーションによって「6m」や「5m」を切った場合は評価値が高く算出されるはずです。この時の評価値はp(τ;θ)と表されます。
※オーラスでは（東発と比べて）特にp(τ;θ)の評価値が大きくなると考えられますね。数式からも半荘終盤で有効であることがわかります。
したがってp(τ;θo)<p(τ;θ)となるため、後者の方が報酬Rが大きくなります。これをK通りのシミュレーション分計算してargmaxを考えると、結果的に「6m」を切るような方策θがθaとして選ばれるというわけです。
ふぅ、長かった😅
pMCPAの問題点
このシミュレーションは理想的にはツモ番が来るたびに行うべきですが、実際のSuphxでは最初の一回しか行われていません。
おそらく計算時間を考えると非現実的なのでしょう。もし、天鳳の持ち時間がもっと長ければ最強の麻雀AIが実現するのかもしれません。
※論文発表時での話なので2021年稼働しているSuphx2ではここらへんの修正がはいっている可能性がありますね。最近不調気味ですが。
Suphxの牌譜を見る際の注意点
これは個人的な意見ですが、Suphxの何切るでは
「何を切ったか（What）」ではなく「何故切ったのか（Why）」
に注目した方がいいと思います。
Suphxは毎局毎局、配牌に応じて打牌選択の方針をアップデートしています。そのためSuphxの打牌が「いつどんな時でも同じように通用する」と考えるのは間違いです。
東1局のSuphxとオーラスのSuphxは全然別物です。あるシーンでダブ東を第一打で落としたからといって、もう一度似たようなシーンでダブ東を切るとは限りません。
同じ麻雀AIのNAGAは（Twitterなどを見ると）打牌選択がわかりやすく、人間もマネしやすいと評判です。NAGAの仕様は不明ですが、判断基準がSuphxよりも明確でコロコロ変化しないのかもしれませんね。
特に終盤での配牌何切るを考える場合は気をつけた方がいいでしょう。オーラスで字牌ドラを第一打で切ったとしても、「場面的にそうせざるを得なかった」に過ぎません。
逆に、東一局の点棒がフラットな状況ではpMCPAがあまり機能していないと考えられるため、配牌何切るを考える価値があるのかもしませんね。配牌の字牌何切るは東一局がオススメです。
まとめ
今回の記事も長くなってしまったのでポイントをまとめたいと思います。
・Suphxは配牌に応じて打牌選択の方針を最適化する
・pMCPAは特に終盤で有効である
・Suphxの牌譜研究ではWhatではなくWhyに注目する
最後に少しだけNAGAの話題に触れましたが、いつか時間のある時にNAGAの牌譜研究もしてみたいですね。
それではここまで。読んでいただきありがとうございました。