麻雀 和了判定（役の判定） アルゴリズム
最終更新日：2008/4/9
麻雀の和了判定を高速に行う方法について説明する。
和了の判定は通常バックトラック法を用いて行うが、バックトラック法は面子候補の組み合わせを総当たりで調べるため、処理に時間がかかるという問題がある。
1回実行するだけの場合は処理時間が問題になることはないが、思考ルーチンなどで繰り返し判定処理を行うような場合に、高速に処理できることが要求される。この記事では、そのような場合にインデックスを用いると高速に判定を行えること説明する。
まず、通常法方法を説明した後、インデックスを用いた方法を紹介する。
通常の方法（バックトラック法）
手牌を１つの雀頭と４つの面子に分けることができれば和了の形となる。（七対子と国士無双は例外）
雀頭と４つの面子を構成する牌が重ならない場合は、どのような順番で取り出しても判定することができる。しかし、雀頭と４つの面子を構成する牌が重なる場合は、ひとつの牌を雀頭とも面子ともとらえることができてしまう。たとえば、１２３３３３４５という牌の時、３を雀頭ととらえれば、残った１２３、３４５を面子として取り出すことができるが、３を面子（刻子）ととらえると、１２３４５が残り、雀頭を取り出すことができない。
したがって、雀頭と面子の候補をすべて試して和了の形になるかを調べる必要がある。このような組み合わせを全て調べる方法に対して、バックトラック法が用いられる。
バックトラック法を適用するにあたり、雀頭が必ずひとつであることを利用すると、雀頭→面子の順に取り出した方が、やり直しの回数が少なくて済む。面子の取り出し方は、刻子を先に取り出すか、順子を先に取り出すかは、どちらか一方に決めることはできない。麻雀の和了は、点数の高い方を採用するというルールであるため、たとえば、１１１２２２３３３を３つの刻子ととらえるか、３つの順子ととらえるかは、残りの雀頭と面子により役がどうかわるかによる。残りが１・９を含む雀頭と順子の場合は、平和、純チャン、一盃口となり、順子ととらえるより点数が高くなる。そうでない場合は、一盃口より、三暗刻ととらえた方がよく、刻子として取り出した方がよいことになる。つまり、取り出し方が複数ある場合は、和了の候補として残し、それらの点数を調べた上で決定する必要がある。ただし、刻子と順子の取り出し順が問題になるのは先ほどの三暗刻と一盃口の場合だけであり、刻子と順子を交互に取り出すようなパターンは不要である。
したがって、雀頭→刻子→順子、雀頭→順子→刻子の２通りの順序を試せばよいということになる。
通常、面子を構成する牌の重なりはそれほど多くないため、調べる組み合わせの数は多くない。しかし、清一のような手牌が一種類の牌で構成される和了の場合は、組み合わせの数が多くなり、処理時間の増加が懸念される。手牌により処理時間がどのように変わるか調べた結果は以下の通りである。
【10万回実行時の処理時間】（Java5、Pentium4 3.0GHzでの測定結果）
手牌：１２３５６７一二三五六七西西
バックトラック法 4297ms
手牌：
１１１２３４６７８東東東西西
バックトラック法 4391ms
手牌：１１１２２２２３３３３４４４
バックトラック法 4891ms
重なりが多いほど、処理時間が増えていることが確認できる。
インデックスを用いた方法
和了の形をあらかじめ調べておき、インデックスとして保持しておくことで、インデックスの検索だけで和了の判定を行う方法である。
単純に和了の形を牌の組み合わせとして保持すると、組み合わせの数は約1,700万通り※あるため、牌の種類34種を6bitで表すとした場合、14枚の組み合わせに6×14=84bit必要となり、1,700万通りを保持するには、少なくとも84bit×
1,700万=
1,428,000,000bit=約1.4Gbit=約175MBの記憶領域が必要となる。
※
http://www10.plala.or.jp/rascalhp/mjmath.htm
一般的なパソコン
のメモリが1GB程度であることを考えれば、和了の牌の組み合わせをそのまま保持することも可能である。しかし、記憶領域を押さえつつ保持できる方法があ
れば、そちらの方法の方が望ましいと言える。
連続した牌の数をインデックスにする方法
和了の形か判断するために、牌が萬子の１であるか、索子の１であるかは重要ではない。１２３のように数字が連続しているかどうかと牌の個数がわかれば十分である。したがって、連続している牌を個数の列に置き換えることで、調べる和了の組み合わせの数を減らすことができる。具体的な例を示すと次のように置き換える。
「１２３」→「１１１」
「５６７」→「１１１」
「１１１」→「３」
「３３３」→「３」
「２３４４５６」→「１１２１１」
異なる牌の組み合わせでも同じ数字の列に置き換わっていることがわかると思う。手牌がすべて連続することは通常ないため、手牌は、連続した数字の個数の複数の組で表現される。このように、牌の組み合わせをを連続した牌の個数の組に置き換えたものをインデックスとして利用することにする。インデックスを数値として扱えた方が便利なため、連続する牌の組同士を「０」でつなげてひとつの数字で表現する。そうすると手牌は次のような数字に置き換えられる。
「１２３５６７一二三五六七西西」→「１１１０１１１０１１１０１１１０２」
「１１１２３４６７８東東東西西」→「３１１１０１１１０３０２」
「１１１２２２２３３３３４４４」→「３４４３」
数値化した和了の形をインデックスとして保持し、和了かどうかの判定にインデックスを検索する場合、数値を比較する処理が必要になる。一般的なパソコンが32bitのコンピュータであるため、数値を比較するとき、数値が32bit以内であれば、扱いやすくなる。手牌を上記のルールに従って数値化した場合、最悪次のような長さの数値になる。
「１３５７９一三五七九東南西北」→「１０１０１０１０１０１０１０１０１０１０１０１０１０１」（27桁）
同じ牌の個数が4枚までなので、1桁を3bitで表すと3bit×27桁=81bit必要になる。このままでは、インデックスとして扱いにくい。そこで、「０」が2個以上続くことがないことを利用して、０をそのひとつ前の数字をセットにして、次のようなルールに従ってビット列に符号化を行う。
「１」→「０」
「２」→「１１０」
「３」→「１１１１０」
「４」→「１１１１１１０」
「１０」→「１０」
「２０」→「１１１０」
「３０」→「１１１１１０」
「４０」→「１１１１１１１０」
数字列を上記の符号化ルールに従ってビット列に変換する場合、次の数値が「０」かどうかに関わらず、以下のルールでビット列に符号化し、次の数字が「０」の場合は「１０」を付加し、「０」以外の場合は「０」を付加すればよい。
「１」→「」
「２」→「１１」
「３」→「１１１１」
「４」→「１１１１１１」
上記のルールで符号化すると、先ほどの手牌は次のように符号化される。
「１３５７９一三五七九東南西北」
→「１０１０１０１０１０１０１０１０１０１０１０１０１０１」（符号化前）
→「１０１０１０１０１０１０１０１０１０１０１０１０１００」（符号化後）
符号化後はビット列となっているため、bit数は、符号化前81bitに対して符号化後は27bitになる。32bit以内であるため、インデックスとして扱いやすい。よって、和了の形を全て調べて上記ルールで符号化してインデックスとして保持することにする。
全ての和了の形の調べ方
手牌を連続した牌の個数で表現した場合、和了の形は、面子が順子か刻子かにより、次のパターンに分類される。
「１１１」「１１１」「１１１」「１１１」「２」（全て順子）
「１１１」「１１１」「１１１」「３」「２」（ひとつが刻子）
「１１１」「１１１」「３」「３」「２」（ふたつが刻子）
「１１１」「３」「３」「３」「２」（みっつが刻子）
「３」「３」「３」「３」「２」（よっつが刻子）
「２」「２」「２」「２」「２」「２」「２」（七対子）※七対子は例外扱いしなくてよい
これらに加えて、副露（ポン、チー、槓）がある場合の手牌も考慮して、
「１１１」「１１１」「１１１」「２」（全て順子、ひとつの副露）
というパターンも加える。
それぞれのパターンで、牌が重なる場合があるため、それらを考慮して全て列挙すればよい。たとえば全てが順子の場合、次のようなパターンがある。
「１１２１１」「１１１」「１１１」「２」
「２２２」「１１１」「１１１」「２」
また、牌を個数にする場合、牌の順番も考慮する必要がある。次の２つは異なる数字に変換される。
「１１３４５７８９一二三五六七」→「２」「１１１」「１１１」「１１１」「１１１」
「３４５７８９一二三五六七東東」→「１１１」「１１１」「１１１」「１１１」
「２」
牌の重なりと牌の順番の組み合わせを全て調べることでインデックスが完成する。
面子の構成を知る
和了かどうかを判定するにはインデックスを検索すればよいが、役を判定するには、どの牌が雀頭でどの牌が刻子か順子かがわかる必要がある。そのため、符号化する前の数字列の何番目が雀頭で何番目が刻子で何番目が順子であるかをインデックスとセットで保持することにする。面子の構成を保持するために、面子の構成を次のようなビット列で構成することにする。
下位
3bit
刻子の数
3bit 順子の数
4bit
雀頭の位置
4bit 面子の位置
4bit
面子の位置
4bit 面子の位置
4bit
面子の位置
上位
面子の位置は刻子→順子の順に埋めていくことにする。
役を事前に判定する
インデックスを作成するときに、連続する牌の個数の並びから一部の役が判定できる。たとえば、次のようなものが事前に判定できる。
「２２２」→一盃口
「２２２」「２２２」→二盃口
「２」「２」「２」「２」「２」「２」「２」→七対子
「４１１１１１１１１３」→九連宝燈
「１１１１１１１１１」→一気通貫
面子の構成とともに事前にわかる役についてもビット列にフラグとして保持することにする。
下位
3bit 刻子の数
3bit 順子の数
4bit 雀頭の位置
4bit 面子の位置
4bit 面子の位置
4bit 面子の位置
4bit 面子の位置
1bit 七対子フラグ
1bit 九蓮宝燈フラグ
1bit 一気通貫フラグ
1bit 二盃口フラグ
1bit 一盃口フラグ
上位
和了の組み合わせを求める
上記の通り、和了の組み合わせを全て列挙して符号化を行い、面子の構成の作成と役の事前判定を行う。配列が扱いやすいためRuby言語を使用してJava言語用のHashMap(またはTreeMap)を作成するコードを生成した。調べ上げた結果、和了の形のパターン数は、9362通りであった。
数値化した和了の形をJava言語のHashMapに追加した場合、ハッシュテーブルサイズがいくつになるか調べた。その結果、ハッシュテーブルサイズが16384となった。ハッシュテーブルを保持するために、少なくとも、32bit×16384=4byte×16384=65,536byte=約65KBが必要となる。これは、パソコンのメモリサイズからすると、十分に小さい。また、TreeMapとして保持する場合は、ハッシュテーブルサイズは不要となる。
インデックスを用いた方法の処理速度測定
インデックスを用いた方法で和了判定を行った場合の処理速度を測定した結果を以下に示す。比較のために通常の方法（バックトラック法）の処理時間も同時に記載した。
【10万回実行時の処理時間】（Java5、Pentium4 3.0GHzでの測定結果）
手牌：１２３５６７一二三五六七西西
バックトラック法 4297ms
インデックス法(HashMap) 94ms
インデックス法(TreeMap) 125ms
手牌：１１１２３４６７８東東東西西
バックトラック法 4391ms
インデックス法(HashMap) 94ms
インデックス法(TreeMap) 125ms
手牌：１１１２２２２３３３３４４４
バックトラック法 4891ms
インデックス法(HashMap) 94ms
インデックス法(TreeMap) 94ms
バックトラック法に比べて、45～50倍程度高速に判定できていることがわかる。また、手牌によらず、速度が安定している。
まとめ
麻雀の和了を判定するために、インデックスを用いることで高速に判定できることを示した。インデックスを利用する場合の利点を以下に示す。
・判定が高速に行える
・一部の役が事前に判定できる
・七対子を例外扱いしなくてよい
ソースコード
測定には以下のソースコードを使用した。
点数計算アプレット
以下で公開しているアプレットではインデックスを用いた方法で和了の判定を行っている。
../mjscore/
[トップページへ]