ぴたすちお、一人麻雀練習機などの自作フリーソフトの配布、数独などのパズル、麻雀、その他もろもろ
あらのHP 数独まにあ エクセルまにあ 麻雀研究所 賢く儲ける株式投資 お釣り ダイエット なたでぽぽ FX

シャンテン数計算アルゴリズム
 

スポンサードリンク

はじめに

麻雀において、シャンテン数(向聴数)を数えるというのは非常に基本的な作業です 。手牌を見て数秒でシャンテン数が分かるようでないと、とてもまとに麻雀を打つことは出来ません。麻雀が上手くなるためには、牌効率や期待値、相手との駆け引きといった事はもちろん重要なのですが、それ以前にシャンテン数を把握することが当然必要なのです。

ここでは、一人麻雀練習機に実装されているシャンテン数を求めるコンピュータアルゴリズムについて解説したいと思います。これからコンピュータ麻雀のプログラムを書こうとしている人はもちろん、それ以外の人にとってもシャンテン数の数え方を理解する上で助けになると思います。

 

場合分け

マージャンの役には、平和やタンヤオなどいろいろなものがありますが、シャンテン数を求める上で関係してくるのは、七対子(チートイツ)と国士無双です。それ以外の手(一般手)においては、4面子1雀頭を揃えることが和了の条件ですが、チートイツと国士無双においてはココが違ってくるからです。

したがって、シャンテン数を求めるためには、この3通りを区別して考える必要があります。つまり、一般手、チートイツ、国士無双に対するシャンテン数を別々に計算して、それらの最小値をもってシャンテン数とするわけです。人間の場合にはほとんど無意識でやっている事ですが、コンピュータはそれほど融通がきかないので、真面目に3通りとも求めないといけません。

チートイツ、国士無双については単純な話なので、まずこれを説明し、最後に一般手についてのシャンテン数の求め方を考えていきます。

なお、シャンテン数を求める対象の手牌が13枚の場合と14枚の場合が考えられますが、アルゴリズム的には本質的な違いがないため特に区別していません。

スポンサードリンク

 

チートイツのシャンテン数

チートイツではその名前の通り、7つの対子を集めることが和了の条件になります。したがってシャンテン数を求めるためには、対子の数を数える事が基本になります。例として下の手牌を考えましょう。

 

対子の数は5つで、シャンテン数は1シャンテンです。つまりチートイツの場合には、対子の数を数えて、それを6から引けばシャンテン数になります。例えば対子が6つあれば聴牌(0シャンテン)、7つあれば和了(−1シャンテン)です。

   チートイツのシャンテン数 = 6 − 対子の数

ただし気を付ける必要があるのは次のようなケース。

 

が暗子になっていますが、これも対子として数えてやる必要があります。さらに気を付けるべきなのは次のような場合。

 

これは対子が6つなので、上の公式によると聴牌になってしまいますが、実際には1シャンテンです。このように牌の種類が足らない場合には、7から牌の種類を引いたものをシャンテン数に足してやる必要があります。

 

例えばこの手牌だと、対子の数が4つで牌の種類が4種類なので、

シャンテン数=6−4+(7−4)=5

となります。

なお、チートイツに対するシャンテン数の最大値は6になります。全くバラバラであっても6枚重なれば聴牌するという事ですね。

 

国士無双のシャンテン数

次は国士のシャンテン数ですが、これは非常に簡単です。

ヤオチュウ牌(一九字牌)の種類を数えて、それを13から引いてやればそれがシャンテン数です。ただし対子がある場合にはひとつを上限にシャンテン数をひとつ減らすことが出来ます。つまり、

 

の場合には、ヤオチュウ牌が12種類で対子がひとつなので、13−12−1で0シャンテン、つまり聴牌です。

 

この場合にはのどちらかは使えないので、13−11−1で1シャンテンということになります。

国士に関してはこれで終了です。

 

一般手のシャンテン数

さて、最後に一般手のシャンテン数ですが、これはちょっとやっかいです。

求め方としては、面子と面子候補の数を数えて、次の式で計算します。

   シャンテン数 = 8 − 面子の数×2 − 面子候補の数

ここで面子とは、完成した面子のことを指していて、つまり順子と暗子です。槓子については一人麻雀練習機では考えていません。面子候補とは、あと一枚で面子になるもののことで、つまり対子と搭子です。

基本的にはこれだけなのですが、注意すべき点がふたつほどあります。

ひとつは、面子と面子候補の数が合わせて4つ以下である必要があるということです。

 

例えばこの手牌ですが、面子が2つ、面子候補が4つなので、上の式で計算すると、

8−2×2−4=0

となってしまいますが、実際には面子候補のうち2つは使うことが出来ません 。いわゆる面子過多という状態です。このような場合には面子と面子候補の数の合計を4にするために、面子候補を2つと数える必要があります。これで計算すると、

8−2×2−2=2

となり、2シャンテンであることが分かります。

もうひとつの注意点は雀頭についてです。上で使った牌以外で雀頭が取れる場合にはシャンテン数から1を引きます。例えば、

 

という手牌の場合、

8−2×2−2=2

という式は同じなのですが、が頭として使えるため、1シャンテンになります。

ここまでが基本的なシャンテン数の求め方ですが、これをコンピュータに実装しようとする場合、もう少し考えることがあります。それは面子と面子候補の数え上げ方です。

 

面子と面子候補の数え上げ方

次の例を見てみましょう。

 

この場合には、というふたつの面子として数えるのが正解なわけで、人間の目で見れば一目瞭然です。しかしながら、これをコンピュータにやらせようとすると少し工夫が必要になってくるのです。どういうことかというと、コンピュータがこれを見たときにという順子を先に数えてしまう可能性があるのです。すると残りはなので、面子が取れないという状況になってしまいます。

では暗子を先に取ればいいかというと、次のような例もあります。

 

この場合には

の2面子を取って欲しいのですが、先にを取ってしまうとが余るという事になってしまいます。

このふたつは面子の例ですが、面子候補が絡むと話はもう少しややこしくなります。例えば、

 

という場合には、という面子がひとつ、という数え方のほかに、という分け方もあります。

したがって、コンピュータで自動的にシャンテン数を求めるためには、これらの可能性をすべて調べていく必要があるわけです。はじめに面子が取れる可能性を全て調べ、そのそれぞれの場合について面子候補を探して行きます。一人麻雀練習機では、再帰関数を使ってこれを実現しています。

 

高速化

シャンテン数を求める処理というのは、基本的なものであるだけに呼びだされる回数が必然的に多くなります。したがって、全体の実行速度に対して結構な影響を与えてしま う事になりかねません。よって、いかに効率的にシャンテン数を計算できるかが重要になってくるのですが、以下ではそのためのいくつかの工夫について説明します。

まず、数牌の種類ごとに面子のカウントを行うこと。

順子については、同じ種類の数牌の中でしか取ることが出来ないため、上記の処理は数牌の種類ごとに分割することができます。これによって、再帰の段数が浅くなるため、実行速度を速くすることができるのです。

次に孤立牌の除去。

例えば、といったような場合、 前述のアルゴリズムで面子を数えようとすると結構な計算量が必要になってきます。このときそれぞれの再帰関数呼び出しにおいてに対する処理が行われてしまいますが、これは無駄です。つまりは面子にも面子候補にも絡んでくる可能性がないので、再帰をかける前の段階で消しておく方が計算時間が節約できるということです。

 

ハッシュテーブルを使った高速化

上記のアルゴリズムによってかなり高速に計算することはできるのですが、それでもやはり再帰処理が入っているため限界があります。特にチンイツなどの手になると、再帰の回数が指数関数的に増加するため、かなりの計算量が必要になってしまいます。これを解決するためのひとつの方法がハッシュテーブルを用いる方法です。

数牌の組み合わせ方というのは有限なので、それぞれの組み合わせについて面子・面子候補の数をあらかじめ調べておき、それをメモリ上に持っておけばいいのです。そうすればいちいち複雑な再帰計算をする手間が省けるということです。ハッシュのキーについては、各牌の枚数を0から4で表して、それを5進数として解釈してやれば、5の9乗=1,953,125ということで普通に整数型が使えます。もちろん、10の9乗も32ビットの範囲内なので、そのまま各牌の枚数を整数に直してもいいですし、8進数を使えばシフト演算が使えるので多少は速くなります。

問題はその組み合わせの数ですが、数牌の数が1枚の場合、2枚の場合…と数えていくと、次のようになっています。

枚数 組合せ数 孤立牌なし
1 9 0
2 45 24
3 165 63
4 495 258
5 1278 774
6 2922 2012
7 6030 4546
8 11385 9218
9 19855 16954
10 32211 28640
11 48879 44795
12 69675 65331

右端の列は、孤立牌を除いた場合の組合せ数です。これを見ると、当然の事ながら枚数が増えるにしたがって組合せ数が指数関数的に増えていくことがわかります。この全通りを組み込むことは、メモリの観点から現実的ではありませんので、なんらかの工夫が必要になります。

ひとつは枚数が少ない場合だけについてハッシュテーブルに登録しておくという方法です。しかし、枚数が少ない場合には通常の方法での計算量も少ないため、それほど効果があるとも思えません。せめて7枚か8枚のあたりまで使わないと、ハッシュキーの計算やテーブルの探索にかかるオーバーヘッドがカバーできないと思います。

もうひとつは、出現率が高いものに関して優先的に登録する方法です。これについては一人麻雀練習機にはまだ実装していませんが、それなりの効果が期待できると思われます。

 

計算時間

一人麻雀練習機では、上に示したようなアルゴリズムでシャンテン数を求めているわけですが、その計算時間を測定してみました。

測定方法

一人麻雀練習機のノーマルモード、チンイツモード、ホンイツモード、国士モードのそれぞれを用いて配牌を10,000 通り生成し、そのシャンテン数を求めるためにかかった時間を測定しました。CPUはPentium4の3GHzです。

モード 時間
ノーマル 0.046秒
ホンイツ 0.188秒
チンイツ 4.328秒
国士 0.031秒

ほぼ予想通りの結果で、やはりホンイツ、チンイツの場合にはかなりの時間がかかってしまっています。

ノーマルモードの、いわゆる普通の手では、1万回のシャンテン数計算で約0.05秒ということで、1秒間に20万回くらいの速度になっています。C++言語を用いていることや、前述のハッシュテーブルを実装していないことを考えれば、もう少し高速化は可能ですが、実用的には問題のないレベルであるということが出来ます。

 

追記

上で述べたハッシュテーブルを用いる方法を一人麻雀練習機に実装しました(ver. 1.22)。8枚までの16,000通り余りと12枚までの165,000通り余りを登録したハッシュテーブルを用意して、それぞれ計算速度を測定したところ、結果は以下の通りでした。

モード 時間 8枚まで 12枚まで
ノーマル 0.046秒 0.047秒 0.046秒
ホンイツ 0.188秒 0.063秒 0.063秒
チンイツ 4.328秒 0.843秒 0.141秒
国士 0.031秒 0.047秒 0.046秒

ノーマルモードと国士モードについては、オーバーヘッドが大きくきいており、ほとんど計算時間は変わらないか、逆に少し遅くなっています。しかし、ホンイツモードでは約3倍、チンイツモードでは5倍 から30倍くらいの高速化がされています。

この測定は配牌に対して行っているのですが、実際のプログラム中では順目が進んだ手牌に対しても当然計算する必要があります。順目が進むごとに字牌や孤立牌が整理され、各色の枚数は多くなる傾向があると思うので、 この表の結果よりはノーマルモードでも効果が期待できるはずです。実際に一人麻雀練習機のシミュレーションモードで実験してみたところ、平均的には2倍から3倍程度の高速化が実現できたようです。

 


このページに対するご意見ご感想は (ara999 あっと gmail.com ) までお願いします

あらのHP 数独まにあ エクセルまにあ 麻雀研究所 賢く儲ける株式投資 お釣り ダイエット なたでぽぽ FX