ブロック分解方式向聴数計算アルゴリズムの精度の検証
はじめに
本記事ではブロック分解方式向聴数計算アルゴリズムの精度について検証した結果を報告します。本記事ではブロック分解方式向聴数計算アルゴリズムは以下のページ・書籍に記載の向聴数計算アルゴリズムの総称とします。
なお、「ブロック分解方式向聴数計算アルゴリズム」という用語は麻雀プログラム関係のリンク集から拝借しました。
さて、これらのアルゴリズムは特定の手牌で間違えることがすでにわかっています。以下は麻雀Cプログラム集からの引用です。
【問題点】 * 例えば「東東東東南南南南西西西北北北」のシャンテン数は１ですが * このソースでは０（テンパイ）になってしまいます。 * これは４枚目の字牌はターツになる事ができない「死に孤立字牌」なのが理由です。これを回避するには * 「どれか一つでも「４枚目の字牌」を持っていたらシャンテン数＋１」とすれば良いかもしれませんが未検証です。
また、同様の方式で向聴数計算アルゴリズムを実装しているMahjongRepositry/mahjongにも向聴数を間違えるケースについてのissueが報告されています。
以上を踏まえると「これらのアルゴリズムは間違っている」と主張するのは簡単です。しかしただそれを主張するのは生産的ではないのでどのような手牌で間違えるのか明らかにすることを検証の目的とします。どのような手牌で向聴数計算を間違えるのかをぜひ知っていただいて必要に応じてアルゴリズムの修正の参考にしていただければ幸いです。なお、理論的に正しいと証明済の向聴数計算アルゴリズムについては拙著の以下のページをご参照ください。
注意
ブロック分解方式向聴数計算アルゴリズムは実装依存の側面が強いです。以下で議論する内容は特別な工夫なく実装した場合のものと捉えてください。例えば以下の牌効率/牌理学習ツールでは特定の手牌に対する修正が入っています。そのような場合は本記事の指摘が当たるとは限りません。
結論
先に結論を述べておきます。ブロック分解型向聴数計算アルゴリズムは孤立牌不足の手牌で向聴数計算を間違えます。例えば正しくは一向聴の手牌を誤って聴牌と判断することがあります。孤立牌不足の手牌とは5ブロック取ることができない手牌のことを指します。なおここでのブロックには孤立牌も含めます。一般的にはブロックは面子または搭子または対子を指すと思いますので、誤解のないようあえて孤立牌不足という用語を定義することにします。
ここで「対戦型麻雀ゲームAIのアルゴリズムと実装」(以降、電脳麻雀本)に記載のアルゴリズムについて少し補足します。電脳麻雀本では他のアルゴリズムと異なり「13-面子数×3-搭子数×2-孤立牌数」という式で向聴数を計算しています。孤立牌数を数えているため問題なさそうに見えますが、孤立牌の生き/死にを区別していないため結局他のアルゴリズムと同様の計算結果をもたらします。[1]
以降、孤立牌不足や生き/死に孤立牌などの用語の定義と検証結果を解説します。
用語の定義
- 孤立牌不足: ブロック数が5未満の手牌⇔手牌にないすべての牌を有効牌に持つような手牌(例: 11112222333444zの有効牌は1234z以外のすべての牌)
- 孤立牌十分: 孤立牌不足の否定
孤立牌不足/孤立牌十分は部分置換数を用いて厳密に定義することが可能です。逆に部分置換数による定義を言い換えたものが上記の定義になります。部分置換数については[麻雀]シャンテン数計算アルゴリズムを参照してください。
- 生き孤立牌: 雀頭に変化できる孤立牌
- 死に孤立牌: 雀頭に変化できない孤立牌
孤立牌から面子への変化は考えなくてよいです(孤立牌を雀頭へ変化させるのに必要な牌の枚数は孤立牌を面子へ変化させる枚数より少ないか同じであるため)。
- ブロック分解: 手牌から面子、搭子、孤立牌の組を取り出すこと
面子数、搭子数、 孤立牌数の和は5とします。
検証と考察
プログラムで検証しました。実装は以下を参照してください。
孤立牌不足の手牌の割合
孤立牌不足の手牌の数を数えました。同じ種類の牌を区別するとした場合、孤立牌不足の手牌の割合は13枚と14枚でそれぞれ次のようになります。
- 13枚の場合: 1.538e-8(約6500万分の1)
- 14枚の場合: 6.204e-11(約160億分の1)
枚数が少ない13枚の場合の方が孤立牌不足になりやすいです。また、孤立牌不足の手牌の向聴数は14枚の場合1, 2に、13枚の場合1, 2, 3に限られることがわかりました。低向聴数の手牌のほうが高向聴数の手牌より孤立牌が少ないことは経験的に納得できると思います。
孤立牌不足の手牌の牌姿
アルゴリズム的には部分置換数を用いて同じ対称性を持つ手牌を集約するという工夫しているのですが、その辺の解説は省略します。
13枚の場合
- 4333型
- 4面子0搭子0孤立牌
- 1向聴(正しい値、以下同様)
- 例: 1111222333444z
- 4432型Ⅰ
- 3面子1搭子0孤立牌 (搭子=対子)
- 2向聴
- 例: 11m11112222333z
- 4432型Ⅱ
- 3面子1搭子0孤立牌 (搭子≠対子)
- 2向聴
- 例: 23m11112222333z
- 4441型
- 3面子0搭子1孤立牌
- 3向聴
- 例: 1111222233334z
14枚の場合
- 4433型
- 4面子0搭子0孤立牌
- 1向聴
- 例: 11112222333444z
- 4442型Ⅰ
- 3面子1搭子0孤立牌 (搭子=対子)
- 2向聴
- 例: 11m111122223333z
- 4442型Ⅱ
- 3面子1搭子0孤立牌 (搭子≠対子)
- 2向聴
- 例: 23m111122223333z
ここで分類型名の4は4枚使い、3は面子(刻子または順子)、2は搭子、1は生き孤立牌をそれぞれ表します。搭子を対子かどうかで区別しているのは部分置換数の表現が異なるからです。あまり重要ではないので区別しなくても問題ありません。上記ではわかりやすくするため字牌を多く使う手牌を中心に例を挙げていますが、字牌を数牌にしたり刻子と順子を入れ替えたりした手牌も同様に分類されます。そのため孤立牌不足の手牌の数は読者の想像以上に多いと言えるのかもしれません。
ところで上記で該当する牌姿が出尽くしているのはプログラムで検証したからわかることですが、直観的には「13個(または14個)のボールを4個の箱に入れる場合の数は何通りか？」という問題を考えると納得できるかと思います。
向聴数計算の精度
13枚と14枚のそれぞれの場合で以下の命題が真であることをプログラムで検証しました。
- (命題1) 孤立牌十分⇒正しい向聴数を計算する
- (命題2) 孤立牌不足⇒間違った向聴数を計算する(命題1の裏)
上記の結果から以下の命題も真であることが導かれます。
- (命題3) 正しい向聴数を計算する⇒孤立牌十分(命題1の逆)
- (命題4) 間違った向聴数を計算する⇒孤立牌不足(命題1の対偶)
また孤立牌不足ならば誤った向聴数+1が正しい向聴数になることも検証しました。
その他の検証
以下の記事に5枚目の牌を待つ聴牌を許可することの修正案として
聴牌と判定された場合に待ちの枚数が残り何枚あるかをカウントして0枚の場合は向聴数1を返すという処理を挟むことで補正は可能だが、コードはさらに複雑になるだろう。
との記述があります(電脳麻雀本にも同様の記述があります)。この案では上記の4333型と4433型の手牌に対する間違いは修正できますがその他の分類型に対する間違いは修正できないことに注意が必要です。
まとめ
- 孤立牌不足/孤立牌十分を定義しました。
- ブロック分解方式向聴数計算アルゴリズムの正当性を孤立牌不足/孤立牌十分のそれぞれの場合で検証しました。
おわりに
既存のアルゴリズムでも精度十分としてそのまま使い続けるのもありですしこの記事を参考に修正するのもありだと思います。なお私はブロック分解方式で完璧なアルゴリズムを文章で説明している例を知りません。ただ、天鳳牌理は生き孤立牌を真面目に数えているようなので有力です。
-
役に対するシャンテン数計算では孤立牌の生き/死にが考慮されていますが、なぜか一般形のシャンテン数計算ではそれが考慮されていません。 ↩︎
Discussion