麻雀 和了判定(役の判定) アルゴリズム

最終更新日:2008/4/9

麻雀の和了判定を高速に行う方法について説明する。

和了の判定は通常バックトラック法を用いて行うが、バックトラック法は面子候補の組み合わせを総当たりで調べるため、処理に時間がかかるという問題がある。 1回実行するだけの場合は処理時間が問題になることはないが、思考ルーチンなどで繰り返し判定処理を行うような場合に、高速に処理できることが要求される。この記事では、そのような場合にインデックスを用いると高速に判定を行えること説明する。

まず、通常法方法を説明した後、インデックスを用いた方法を紹介する。

通常の方法(バックトラック法)

手牌を1つの雀頭と4つの面子に分けることができれば和了の形となる。(七対子と国士無双は例外)

雀頭と4つの面子を構成する牌が重ならない場合は、どのような順番で取り出しても判定することができる。しかし、雀頭と4つの面子を構成する牌が重なる場合は、ひとつの牌を雀頭とも面子ともとらえることができてしまう。たとえば、12333345という牌の時、3を雀頭ととらえれば、残った123、345を面子として取り出すことができるが、3を面子(刻子)ととらえると、12345が残り、雀頭を取り出すことができない。

したがって、雀頭と面子の候補をすべて試して和了の形になるかを調べる必要がある。このような組み合わせを全て調べる方法に対して、バックトラック法が用いられる。

バックトラック法を適用するにあたり、雀頭が必ずひとつであることを利用すると、雀頭→面子の順に取り出した方が、やり直しの回数が少なくて済む。面子の取り出し方は、刻子を先に取り出すか、順子を先に取り出すかは、どちらか一方に決めることはできない。麻雀の和了は、点数の高い方を採用するというルールであるため、たとえば、111222333を3つの刻子ととらえるか、3つの順子ととらえるかは、残りの雀頭と面子により役がどうかわるかによる。残りが1・9を含む雀頭と順子の場合は、平和、純チャン、一盃口となり、順子ととらえるより点数が高くなる。そうでない場合は、一盃口より、三暗刻ととらえた方がよく、刻子として取り出した方がよいことになる。つまり、取り出し方が複数ある場合は、和了の候補として残し、それらの点数を調べた上で決定する必要がある。ただし、刻子と順子の取り出し順が問題になるのは先ほどの三暗刻と一盃口の場合だけであり、刻子と順子を交互に取り出すようなパターンは不要である。 したがって、雀頭→刻子→順子、雀頭→順子→刻子の2通りの順序を試せばよいということになる。

通常、面子を構成する牌の重なりはそれほど多くないため、調べる組み合わせの数は多くない。しかし、清一のような手牌が一種類の牌で構成される和了の場合は、組み合わせの数が多くなり、処理時間の増加が懸念される。手牌により処理時間がどのように変わるか調べた結果は以下の通りである。

【10万回実行時の処理時間】(Java5、Pentium4 3.0GHzでの測定結果)

手牌:123567一二三五六七西西
バックトラック法    4297ms

手牌: 111234678東東東西西
バックトラック法    4391ms

手牌:11122223333444
バックトラック法    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程度であることを考えれば、和了の牌の組み合わせをそのまま保持することも可能である。しかし、記憶領域を押さえつつ保持できる方法があ れば、そちらの方法の方が望ましいと言える。

連続した牌の数をインデックスにする方法

和了の形か判断するために、牌が萬子の1であるか、索子の1であるかは重要ではない。123のように数字が連続しているかどうかと牌の個数がわかれば十分である。したがって、連続している牌を個数の列に置き換えることで、調べる和了の組み合わせの数を減らすことができる。具体的な例を示すと次のように置き換える。

「123」→「111」
「567」→「111」
「111」→「3」
「333」→「3」
「234456」→「11211」

異なる牌の組み合わせでも同じ数字の列に置き換わっていることがわかると思う。手牌がすべて連続することは通常ないため、手牌は、連続した数字の個数の複数の組で表現される。このように、牌の組み合わせをを連続した牌の個数の組に置き換えたものをインデックスとして利用することにする。インデックスを数値として扱えた方が便利なため、連続する牌の組同士を「0」でつなげてひとつの数字で表現する。そうすると手牌は次のような数字に置き換えられる。

「123567一二三五六七西西」→「11101110111011102」

「111234678東東東西西」→「311101110302」

「11122223333444」→「3443」

数値化した和了の形をインデックスとして保持し、和了かどうかの判定にインデックスを検索する場合、数値を比較する処理が必要になる。一般的なパソコンが32bitのコンピュータであるため、数値を比較するとき、数値が32bit以内であれば、扱いやすくなる。手牌を上記のルールに従って数値化した場合、最悪次のような長さの数値になる。

「13579一三五七九東南西北」→「101010101010101010101010101」(27桁)

同じ牌の個数が4枚までなので、1桁を3bitで表すと3bit×27桁=81bit必要になる。このままでは、インデックスとして扱いにくい。そこで、「0」が2個以上続くことがないことを利用して、0をそのひとつ前の数字をセットにして、次のようなルールに従ってビット列に符号化を行う。

「1」→「0」
「2」→「110」
「3」→「11110」
「4」→「1111110」
「10」→「10」
「20」→「1110」
「30」→「111110」
「40」→「11111110」

数字列を上記の符号化ルールに従ってビット列に変換する場合、次の数値が「0」かどうかに関わらず、以下のルールでビット列に符号化し、次の数字が「0」の場合は「10」を付加し、「0」以外の場合は「0」を付加すればよい。

「1」→「」
「2」→「11」
「3」→「1111」
「4」→「111111」

上記のルールで符号化すると、先ほどの手牌は次のように符号化される。

「13579一三五七九東南西北」
→「101010101010101010101010101」(符号化前)
→「101010101010101010101010100」(符号化後)

符号化後はビット列となっているため、bit数は、符号化前81bitに対して符号化後は27bitになる。32bit以内であるため、インデックスとして扱いやすい。よって、和了の形を全て調べて上記ルールで符号化してインデックスとして保持することにする。

全ての和了の形の調べ方

手牌を連続した牌の個数で表現した場合、和了の形は、面子が順子か刻子かにより、次のパターンに分類される。

「111」「111」「111」「111」「2」(全て順子)
「111」「111」「111」「3」「2」(ひとつが刻子)
「111」「111」「3」「3」「2」(ふたつが刻子)
「111」「3」「3」「3」「2」(みっつが刻子)
「3」「3」「3」「3」「2」(よっつが刻子)
「2」「2」「2」「2」「2」「2」「2」(七対子)※七対子は例外扱いしなくてよい

これらに加えて、副露(ポン、チー、槓)がある場合の手牌も考慮して、

「111」「111」「111」「2」(全て順子、ひとつの副露)

というパターンも加える。

それぞれのパターンで、牌が重なる場合があるため、それらを考慮して全て列挙すればよい。たとえば全てが順子の場合、次のようなパターンがある。

「11211」「111」「111」「2」
「222」「111」「111」「2」

また、牌を個数にする場合、牌の順番も考慮する必要がある。次の2つは異なる数字に変換される。

「11345789一二三五六七」→「2」「111」「111」「111」「111」
「345789一二三五六七東東」→「111」「111」「111」「111」 「2」

牌の重なりと牌の順番の組み合わせを全て調べることでインデックスが完成する。

面子の構成を知る

和了かどうかを判定するにはインデックスを検索すればよいが、役を判定するには、どの牌が雀頭でどの牌が刻子か順子かがわかる必要がある。そのため、符号化する前の数字列の何番目が雀頭で何番目が刻子で何番目が順子であるかをインデックスとセットで保持することにする。面子の構成を保持するために、面子の構成を次のようなビット列で構成することにする。

下位
3bit    刻子の数
3bit    順子の数
4bit    雀頭の位置
4bit    面子の位置
4bit    面子の位置
4bit    面子の位置
4bit    面子の位置
上位

面子の位置は刻子→順子の順に埋めていくことにする。

役を事前に判定する

インデックスを作成するときに、連続する牌の個数の並びから一部の役が判定できる。たとえば、次のようなものが事前に判定できる。

「222」→一盃口
「222」「222」→二盃口
「2」「2」「2」「2」「2」「2」「2」→七対子
「4111111113」→九連宝燈
「111111111」→一気通貫

面子の構成とともに事前にわかる役についてもビット列にフラグとして保持することにする。

下位
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での測定結果)

手牌:123567一二三五六七西西
バックトラック法    4297ms
インデックス法(HashMap)      94ms
インデックス法(TreeMap)      125ms

手牌:111234678東東東西西
バックトラック法    4391ms
インデックス法(HashMap)      94ms
インデックス法(TreeMap)      125ms

手牌:11122223333444
バックトラック法    4891ms
インデックス法(HashMap)      94ms
インデックス法(TreeMap)      94ms

バックトラック法に比べて、45~50倍程度高速に判定できていることがわかる。また、手牌によらず、速度が安定している。

まとめ

麻雀の和了を判定するために、インデックスを用いることで高速に判定できることを示した。インデックスを利用する場合の利点を以下に示す。

・判定が高速に行える
・一部の役が事前に判定できる
・七対子を例外扱いしなくてよい

ソースコード

測定には以下のソースコードを使用した。

点数計算アプレット

以下で公開しているアプレットではインデックスを用いた方法で和了の判定を行っている。
http://hp.vector.co.jp/authors/VA046927/mjscore/


[トップページへ]