一人麻雀和了確率計算アルゴリズム まとめ
はじめに
今回はこれまでに議論してきた一人麻雀和了確率についていくつかの問題点・疑問点を解消します。
諸問題
存在確率と和了確率の再定義
前々回の記事のトップダウンとボトムアップの関係についての記述が不十分なので補足します。
向聴の手牌を想定し、からまでの個の状態(手牌)があるとします。状態間の遷移確率を表す以下の確率行列を定義します。
巡目に枚の牌があるとして巡目に和了する確率はの成分なので
と書けます。なお行列とベクトルの添字は0始まりとします。または単位ベクトルです。これを計算する方法は2通りあり、①に左からを繰り返し作用させる方法と②に右からを繰り返し作用させる方法があります。①がトップダウンで②がボトムアップです。それぞれの方法は以下のように書けます。
基底変換(パラメータ変換)
手牌変化が一通りではなく分岐する場合、確率行列としてではなく以下のを考えます。
これをと同じように扱いたいので以下の対角行列を導入して基底を変換します。
ここで例えばを考えると行目はと同じになります。よって
が成り立ちます。とのかわりにによって基底を変換したとを使えば、手牌変化が一通りの場合と分岐する場合の確率の計算をほとんど同じようにできます。
手牌変化のグラフの正確な記述
前回の記事で手牌変化のグラフを導入しました。
一人麻雀和了確率は2次元確率DPで計算できます。それならばグラフは無向グラフではなくDAGとして記述すべきなような気がします。
上の図では簡単のため2つの巡目しか記載していません。また矢印の色と線種については後述します。先述のように和了確率を求めるには各状態での和了確率を知らなければならないので、DPを使って計算する際は矢印の向きを逆向きにたどって各状態を訪問することになります。
緩和順
各状態での和了確率を表す漸化式は以下のようになります(前回の記事を参照)。
添字が手牌方向と巡目方向と2つあるので、どちらをループの外側にするのかが問題になります。手牌変化のグラフを見ると巡目方向がトポロジカル順序になることがわかるので巡目をループの外側にすればよいことがわかります。ここで手牌変化のグラフから赤色の矢印がないとすると手牌方向もトポロジカル順序になります。赤色実線矢印は向聴戻し、赤色破線矢印は手替わりを表していると思ってください。この場合再帰的に手牌を探索しながら各巡目での和了確率を計算できるので、計算速度・メモリ効率ともに向上します。
辺の重み
辺の重みを巡目によらず固定としてよいのかは、和了確率を最大にする打牌をする場合2回以上同じ手牌を訪問しないので固定としてよいです。
おわりに
一人麻雀和了確率についての問題点・疑問点をほぼ解消できたのではないかと思います。
一人麻雀和了確率計算アルゴリズム グラフ探索
今回は前回の記事の続きです。
tomohxx.hatenablog.com
これまで手牌変化の木は与えられたものとして和了確率を求めてきました。基本的にシャンテン数が下がれば和了確率は上がると考えられるので、実装上は一方的にシャンテン数を下げる手牌変化の木を扱ってきました。しかし手替わりやシャンテン戻しを考慮すると、この手牌変化の木以外により高い和了確率を与える木が存在する可能性があります。つまり和了確率を最大にする手牌変化の木は自明ではありません。そこで手牌変化の木を構築することも含めた和了確率を計算するアルゴリズムを紹介します。
今回は手牌変化の木ではなく手牌変化のグラフを考えます。以下のような重み付き無向グラフが与えられるとします。は13枚の手牌、は14枚の手牌を表し、異なる枚数の手牌を表す頂点同士は隣接するが同じ枚数を表す頂点同士は隣接しません。また辺は13枚の手牌から14枚の手牌に変化するための牌の枚数を表します。なお、手牌の枚数をより一般に枚、枚としても構いません。
ここで和了確率を次のように定義します。
以下の連立確率漸化式を解いて和了確率を求めます。はの隣接する頂点の集合を得る演算です。
初期条件は和了している手牌の集合をとして
です。
式の意味を簡単に説明します。まず(1)式の第2式は簡単で、手牌の枚数が14枚のときの和了確率をそこからある牌を捨てたときの和了確率の最大値とすることを意味します。次に(1)式の第1式ですが具体例を用いて説明します。現在頂点にいるとして頂点に隣接しているとします。前回の記事の要領でを計算すると次のようになります。
これを変形すると
となるので、隣接する頂点数を一般化して(1)式の第1式になります。ここでもしであればからへの変化を考えない方が和了確率が高くなると言えますが(1)式の第2式よりが保証されるので(1)式の第1式はそのままでよいことがわかります。つまり(1)式は不要牌をツモったときのツモ切りを内包していると言えます。
ところで巡目によって辺の重みが変化することは考えなくてよいのでしょうか?これは特定の計算条件の下では考える必要はありません。実は先の手牌変化のグラフの図には自己ループが省略されています。これは自明な不要牌をツモ切りすることを意味していてその重みはで巡目によって変化します。自明な不要牌とは例えばタンヤオテンパイに対する字牌やホンイツに対する本命ではない色の数牌のような絶対にいらない牌です。自己ループを含めて辺の重みの合計がであればよく、辺の重みの巡目依存性を自己ループに押し付けていることになります。逆に自明な不要牌が存在せず自己ループが存在しない場合(あらゆるツモを考慮して和了確率を計算する場合)(1)式は破綻することになります。*1*2
以上の議論を踏まえると和了確率を計算するには対象の手牌から変化可能な手牌の集合が必要でそれは手牌の全体集合ではないことがわかります。その集合の部分集合を得るのは簡単ですが、漏れなく効率的にこの集合の全要素を得る方法は現在検討中です。まあ、これについては和了確率とあまり関係ないような気がするので正直なところやる気が起きません。そこで、変化可能な手牌の集合を簡単に得られる場合として一色手の手牌の和了確率を計算してみました。
github.com
一色手の場合14枚の手牌のパターンは118800通り、13枚の手牌のパターンは93600通りなので時間的にも空間的にも計算可能な範囲です。
前述の通り、和了確率についてはもうやる気が起きないので新規に何かをするとしてもかなり先になると思います。あとこれまでに各所で公開したトップダウンの方法は今となっては人に勧められるものではなくなったので前回と今回の記事で扱ったボトムアップの方法に置き換えないといけないですね。面倒くさい……。
一人麻雀和了確率計算アルゴリズム トップダウン vs ボトムアップ
トップダウンとボトムアップの定義を逆にしました。(2022/09/23追記)
実装例を追記しました。(2022/09/23追記)
このブログでは度々一人麻雀の和了確率を計算するアルゴリズムを取り上げてきました。ところでこのブログ以外でも一人麻雀の和了確率や期待値の計算方法を解説しているサイトがあります。
- http://critter.sakura.ne.jp/ (critter 氏)
- https://mahjong.ara.black/ (あら氏)
- https://pystyle.info/mahjong-expected-value-in-mahjong/ (nekobean 氏)
これらのサイト、そしてこのブログは一人麻雀の和了確率や期待値を計算しているはずですが、すべて同じ値を計算できているのでしょうか?言い換えればこれらのサイトで用いられているアルゴリズムはすべて等価なのでしょうか?今回はこれらのアルゴリズムの関係を明らかにしたいと思います。なお先に結論を述べておくとすべて等価です。
先に言及したアルゴリズムに共通するのは手牌変化の木を探索するということです。手牌変化の木とは以下の図のように手牌の変化を木で表現したものです。なお、議論を簡単にするため以降では引いた牌に対してどの牌を捨てるかが事前に決まっているものとします。
それぞれのアルゴリズムで求める値は次のように決定的に異なります。手牌変化の木の根を上としたときにそれらの値を上から下へ求めるか下から上へ求めるかによって、これらのアルゴリズムはトップダウンとボトムアップに分かれます。このブログでこれまで取り上げてきたアルゴリズムはトップダウンに、それ以外はボトムアップになります。
- トップダウン
- 巡目にノードの状態である確率を求める。
簡単な問題を使って2つの違いを見ていきます。
トップダウンの解法
ボトムアップの解法
(3)式と(4)式を見ると違いは2点あり、①時間発展の方向が互いに逆である②行列が互いに共役転置の関係にあることがわかります。計算過程は省略しますがこれらを解くと
の関係が得られます。よってトップダウンとボトムアップのどちらでも同じ和了確率を得られます。
では手牌の変化の行先が複数の場合について考えてみます。例えばの変化の他にの変化がある場合、ボトムアップでは以下の連立確率漸化式を解きます。なおトップダウンについては https://tomohxx.github.io/mahjong-algorithm-book/ を参照してください。
(6)式のように行先の分だけ項が増えます。ここまでに解説したボトムアップのアルゴリズムがおそらくcritter氏のアルゴリズムに相当すると思います。
ここで(2)式に戻ってこれを形式的に解いてみます。
念のため途中式を記載しました。さて(7)式は「巡目の和了確率は、巡目まで有効牌を引かず巡目に有効牌を引く確率に巡目の和了確率をかけたものを]に渡って足したものである」と解釈できます。この(7)式を使うアルゴリズムがあら氏とnekobean氏のアルゴリズムに相当すると思います。
以上の議論から冒頭で言及した3つのサイトとこのブログで用いられたアルゴリズムはすべて等価であることが簡単には(厳密ではない)説明できました。
最後にどのアルゴリズムを使うべきか考えてみます。素朴に実装すれば計算量はどれも同じですが、ボトムアップでは途中のノードの和了確率をキャッシュする(メモ化再帰)ことで訪問するノード数を減らせるので計算速度を追求するならボトムアップを使うべきです。また(2)式と(7)式は等価ですが、(7)式はループカウンタの分変数が増えるので(2)式の方が実装が簡単だと思います。つまりcritter氏のアルゴリズムが一番おすすめです。
ここまで完全に机上の議論しかしてきませんでしたが、ボトムアップを実装したものがこちらです。
手替わりなし・シャンテン戻しなしの条件付きですが、5シャンテンまでなら1秒以下、6シャンテンでは10秒から20秒程度で和了確率を計算することができます。6シャンテンの計算はキャッシュを使うからこそできるのであって、キャッシュの使えないトップダウンでは時間がかかりすぎて事実上計算不可能です。というわけでボトムアップの優位性は明白です。また一般の5シャンテンや6シャンテンの高シャンテン数の手牌の和了確率を計算できるプログラムは他にないと思われます。なお高シャンテン数であっても対称性が高い特殊な手牌では以前から計算可能でした。
vs Mortal
最近Equimさんの開発したMortalという麻雀AIが話題になっています。
天鳳や雀魂の牌譜をレビューする機能と、天鳳の個室に呼び出して同卓する機能があります。話題になっているのは主に前者ですが、ここでは後者を使って自作の麻雀AIと対戦させてみます。目的は評価ではなく人気に便乗お試しです(おそらく評価目的で多試合打たせることはサーバーのリソースを専有することになるのでダメかと)。Mortalは開発者の検証によりAkochanよりも強いことがわかっています。Akochanの強さは天鳳の段位において七~九段相当とされているので、Mortalが天鳳鳳凰卓レベルであることは間違いないと思われます。
自作の麻雀AI用に以下の2つのアカウントを用意しました。
- Mar1422
- Mar1422'
1つ目は以前に天鳳自動打ちで使用したものです。
もちろん名前が違うだけでそれぞれはまったく同じです。これら2体のAIとMortal 2体を個室で対戦させました。以下が牌譜です。
- 1試合目
- 2試合目
簡単に気になった場面をピックアップしてみます。
1試合目Mar1422'視点です。上家・下家がMortal、対面がMar1422です。親番ということで立直しなくてもまくれるので立直しないほうがいいと思います。
2試合目Mar1422'視点です。上家・対面がMortal、下家がMar1422です。立直後あと5枚のところまで引っ張られると相対的に愚形待ちの割合が高まるので、ダブルワンチャンスかつションパイではない1pを選択したと思われます。私なら安易に9sを切りそうです(これが正解かはわかりません……)。ちなみにその後Mortalから跳満を出あがりました。満貫以上で得点上昇効率が悪いのでダマで正解ですかね。
全体的な感想になりますがすごく攻撃的な試合だったと思います。私自身これらのAIのように押すタイプではなく、真似できないような行動もありました。あとAIはミスしないので一局の中での展開が速いですね。正直同卓したくはないです……。
さて、最後になりますが麻雀AI開発を引き続き頑張っていこうと思います。
配牌時有効牌の枚数
配牌時(手牌の枚数が13枚のとき)有効牌の枚数を計算するアルゴリズムを以下のページにまとめました。ここでは結果について簡単に記載します。
向聴数 | 場合の数 | 割合 | 有効牌の枚数の平均値 |
---|---|---|---|
0 | 39270395383132 | 8.1175e-05 | 4.5843 |
1 | 3006175115638776 | 0.006214 | 12.2671 |
2 | 45249205945148216 | 0.0935337 | 23.3215 |
3 | 175141291509958900 | 0.362031 | 40.4909 |
4 | 192909046305573888 | 0.398758 | 60.6136 |
5 | 63384201353756672 | 0.13102 | 77.8174 |
6 | 4045365540028416 | 0.00836209 | 100.154 |
向聴数を区別しないで有効牌の枚数の平均値を計算すると52.1202になります。
ちなみに計算時間は私の環境で5分弱でした。正直、このデータが何の役に立つか不明です。とりあえず計算できるということを強調しておきます。
牌の危険度予測ツール
牌の危険度予測ツールを開発しました。
ここで述べる危険度は以下の式で定義されます。この式はすべての聴牌形の出現確率が等しいという最も単純な仮定の下で危険度を求めます。
どのように聴牌形を数え上げるかについては以下のページを参照してください。大雑把には天和の確率を求めたり配牌時向聴数を求めたりすることと同じようなこと(動的計画法)をやっています。
この式では切り順や手出し・ツモ切りは考慮されません。上級者にはもの足りないかもしれませんが初・中級者には十分有用だと思われます。
簡単に使い方を説明します。例えば以下の場面で立直をかけている対面に対して牌の危険度を求めてみます。なお、このツールは対象者が聴牌しているという前提で牌の危険度を求めます。よって対象者が立直をかけているか、三副露以上している、連続でツモ切りしているというように聴牌していることを確信できる必要があります。
まず以下のファイルを作成します。
4 1m 1 1 2m 1 1 3m 4 0 4m 3 0 5m 3 0 6m 3 1 7m 3 0 8m 2 0 9m 2 1 1p 0 1 2p 2 0 3p 2 0 4p 3 0 5p 3 0 6p 4 0 7p 1 0 8p 1 1 9p 2 0 1s 3 0 2s 3 1 3s 3 0 4s 3 0 5s 3 0 6s 1 0 7s 1 1 8s 3 0 9s 2 0 1z 4 0 2z 1 0 3z 2 0 4z 3 1 5z 1 1 6z 1 1 7z 2 1
1行目に手牌の面子数を、2行目以降に各牌の残り枚数と振聴かどうかのフラグを入力します。このファイルをwall_river.txt
という名前で保存します。次に以下のコマンドでDockerのイメージを作成、コンテナを作成・実行して危険度の計算とグラフの出力を行います。計算時間は環境によりますが私の環境では2~3ミリ秒です。
$ docker build . -t predictor $ docker run -v $PWD/output:/output -v $PWD/wall_river.txt:/wall_river.txt --rm predictor
次のグラフが出力されます。
このグラフから36s、47m、3pから7pが危険だとわかります。中らずと雖も遠からずという感じでしょうか。
最後に補足事項があります。このツールで計算された牌の危険度が本当に正しいのか、つまり(1)式を正しく計算できているのか客観的に証明することができていません。アルゴリズムによって聴牌形を数え上げている人が他にいないことと、私自身これ以外の方法で聴牌形を数えたことがないためです。もちろんアルゴリズムは正しいと確信していますが実装に誤りがある可能性を否定できません。また証明しようにもどのようなテストケースを作成すればよいかという問題もあります。
統計やシミュレーションではなく、厳密に聴牌形を数え上げることで危険度を予測するというツールは他にはないはずです。統計やシミュレーションでは誤差が避けられませんがこのツールには誤差がないことが魅力ではないかと思います。厳密に危険度を議論したいという状況がどれくらいあるのかわかりませんが、そのようなときにはぜひ活用していただきたいと思います。
配牌時向聴数
気分転換にブログを更新します。最近は強化学習について勉強していて、今後の麻雀AI開発に生かしたいと考えています。こちらについてまだブログに書くだけの結果がないので、今回は麻雀アルゴリズムについて書きます。少し前に、配牌時向聴数を計算するアルゴリズムを以下のページにまとめました。
(簡易版) https://tomohxx.github.io/mahjong-algorithm-book/shanten/
(完全版) https://gist.github.com/tomohxx/036d814e5099ce972ba9683826b9d41e
配牌時向聴数については、このブログでこれまで言及してこなかったのでここで言及(宣伝)しておきます。「麻雀の数学(http://www10.plala.or.jp/rascalhp/mjmath.htm#12)」というサイトがありますが、そのサイトの計算を追試したようなものです。そのアルゴリズムは競技プログラミングに通じるものを感じます。麻雀をテーマに自分の知らなかったアルゴリズムを勉強することができてよかったです。
最近は麻雀AIに注力していますが、ときどき麻雀アルゴリズムについて理解を深めていければと思います。