正確なブロック分解方式の向聴数計算アルゴリズムの提案
はじめに
先日、以下の記事を投稿しました。この記事ではブロック分解方式の向聴数計算アルゴリズムとして分類できるアルゴリズムが孤立牌不足の手牌で間違った向聴数を計算してしまうことを指摘しました。その後この問題を解決する方法を考案・テストしたのでここで解説します。
修正案
ここで提案する修正内容は以下の3つです。本記事では向聴数計算アルゴリズムとして最も広く参考にされていると筆者が考える麻雀C言語プログラム集(Webアーカイブ)に記載のアルゴリズムをベースにしています。
- 4枚使いを双碰待ち(シャンポン待ち・シャボ待ち)とみなさない
- 孤立牌不足になり得る手牌では孤立牌を数える
- 枝刈りを導入して高速化する
それぞれ解説していきます。
1つ目は向聴数を間違えるケースとしてよく知られている問題の解決策です。これを解決するにはどの牌を雀頭として抜き出したかをメモしておいて、搭子を抜き出すフェーズにおいてその牌を搭子として抜き出さないようにすればよいです。なお、この修正のためにあら氏の提案する「テーブルを使った高速化」はそのままでは使えなくなります(工夫すればテーブルを使えますがサイズは大きくなります)。
2つ目は孤立牌不足に関する解決策です。先日投稿した記事で13枚の手牌に対して4パターン、14枚の手牌に対して3パターンの孤立牌不足となる手牌を示しました。これらの手牌は以下の3つに分類できます。
- 雀頭へ変化できる孤立牌を1枚求める(4333型、4432型Ⅱ、4433型、4442型Ⅱ)
- 面子へ変化できる孤立牌を1枚求める(4432型Ⅰ、4442型Ⅰ)
- 雀頭へ変化できる孤立牌1枚と面子へ変化できる孤立牌1枚を求める(4441型)
あるブロック分解パターンにおいて面子と搭子の数が上記のパターンに一致すればその時に限って孤立牌の数を数えるようにします。その結果孤立牌が不足していると分かれば向聴数を+1します。逆に面子と搭子の数が上記のパターンに一致しなければ孤立牌を数える必要はなく従来の向聴数計算公式を使用することで余計な計算をしないようにします。
3つ目は精度ではなく速度を改善するための工夫です。あら氏が指摘しているようにすべてのブロック分解パターンを求めると計算速度が遅くなってしまいます。その解決策の一つがテーブルを使うことですが、テーブルを使わなくても高速化することは可能です。その方法がこれから説明する枝刈りです。例えばすでに雀頭1つと面子2つを抜き出していて次に搭子分解のフェーズに移ろうとしているとします。この時点で向聴数の下限値が確定し搭子2つを抜き出したケースとして1となります。その後搭子を2つ抜き出したのならば以降の搭子分解は不要となり面子分解のフェーズまで引き返すことが可能です。このように搭子分解を行う回数を減らすことができます。もちろん搭子分解を行う回数は手牌によって様々ですが平均として計算速度の向上が期待できます。この工夫によって筆者の環境では一手当たりの計算速度が1μsから2μsとなりました。計算条件が異なるとは思いますが、この値はあら氏や小林氏のものと遜色ないと思います。
実装
以上の修正案を以下のリポジトリに実装しました。このリポジトリでは13枚と14枚のすべての手牌について理論的に正しいと証明されている向聴数計算ライブラリの計算結果と比較することで正確さを証明します。なお理論的な証明はありません。また、あら氏のテストケースを使用した計算速度のテストも行います。余談ですが、あら氏のテストケースには孤立牌不足の手牌が含まれていないため精度のテストには使用しません。
おわりに
ブロック分解方式の向聴数計算アルゴリズムの修正案を解説しました。修正案として難しくないのではないでしょうか。参考にしていただければ幸いです。
Discussion