麻雀のシャンテン数を数えるアルゴリズム

プログラムで麻雀のシミュレーションを行うとき、手牌のシャンテン数を数えたいことがあります。 ここでは、機械的にシャンテン数を数えるアルゴリズムを考えてみます。 七対子や国士無双のシャンテン数は簡単に調べられるので、「4 メンツ + 1 雀頭」の基本形でアガる場合のシャンテン数を数える方法を説明します。

基本的な考え方

このような形が、4 メンツ + 1 雀頭の基本形です。 この 5 ブロック（合計 14 枚）のアガリ形を作るために、あと何枚の牌が必要かを考えればよいことになります。 ただし、アガリまでの枚数は、聴牌であればあと 1 枚、イーシャンテンであればあと 2 枚なので、シャンテン数を数える場合は、アガリまでの枚数から 1 を引いて数えることに注意してください（アガリまであと 3 枚であれば、2 シャンテンです）。

テンパイまでに必要な枚数ではなく、現在の手牌のうち何枚使えるかを基準にして考えることもできます。 その場合は、13 - アガリ形になったときに今ある手牌のうち何枚使えるか がシャンテン数になります。

最悪のシャンテン数

手牌に 1 つもターツがない、バラバラの状態は何シャンテンでしょうか？ 13 シャンテンでしょうか？ 違いますね。 仮に上記のようにバラバラの手牌であったとしても、少なくとも 5 枚の牌は 5 ブロックの中の 1 枚としてアガリ形の中で使えます。 つまり、最悪のシャンテン数は 8 シャンテン (13 - 5) です。 もちろん、実際には七対子があるので、本当の最大シャンテン数は 6 シャンテンになります。

あとは、8 シャンテンを基準にして、手牌にどのような形が含まれていればシャンテン数が減るのかを調べていけば OK です。

ターツまたはトイツができると 1 歩前進

上記のように、ターツ ( 1m2m ) やトイツ ( 7z7z ) ができると聴牌に向かって 1 歩前進します。 このように 2 枚で構成されるターツあるいはトイツのことを ペア と呼ぶことにします（ペアの例: 1m2m 、3s4s 、7p9p 、4z4z ）。 ペア 1 組ごとにシャンテン数は 1 つ減るので、（ペアだけを考慮した）シャンテン数は次のように計算できます。

ただし、ペアとしてカウントできるのは、最大 5 つまでです。 なぜなら、アガリ形のブロック数は最大 5 つだからです。 あと、5p5p + 5p5p のような形で、同一牌で 2 つのペアとカウントすることはできないことに注意してください。

メンツができると 2 歩前進

ターツが 1m2m3m のようなメンツに変化すると、さらに 1 歩前進するので、メンツ数を考慮したシャンテン数は次のように計算できます。

ここでは、メンツを 2 歩前進するものと数えているので、メンツになった部分はペアのカウントを減らしてください。 メンツとペアを、それぞれ 1 つのブロックとしてカウントするのであれば、次のような計算式でも大丈夫です。

「ブロック数 = メンツ数 + ペア数」と展開すると、前の式とまったく同じです。

メンツ数による制約

ターツやトイツ（これらをペアと呼んでいます）がたくさんあっても、最終的なアガリ形は 4 メンツ + 1 雀頭になるので、やみくもにペアの数をカウントしてシャンテン数を減少させるわけにはいきません。 例えば、4 メンツ完成しているときは、残りのブロックは雀頭（トイツ）ででなければいけないので、ターツは採用できません。 3 メンツ完成しているときは、ターツは 1 つまでしか採用できません。ターツは雀頭にはなり得ないからです。 完成メンツ数に応じて、カウントできる（採用可能な）ターツの最大数は次のように変化します。

つまり、カウントできるターツの最大数は「4 - 完成メンツ数」 です。

さらに、完成形は 5 ブロックなので、メンツとペアを合わせて 5 を超えてカウントすることはできません。 つまり、カウントできるトイツの最大数は「5 - 完成メンツ数 - ターツ数」 です。 ただし、このターツ数は、上記の補正を行ったあとのターツ数です。

例題として、次のような形を考えてみます（ここではツモる前の 13 枚で考えてみます）。

メンツが 1 つ、ターツが 4 つ、トイツが 1 つありますが、実際に採用できるターツ最大数とトイツ最大数は次のように計算します。

• ターツ最大数 = 4 - 完成メンツ数 = 4 - 1 = 3
  • よって、採用するターツ数は 3 となる（1 つのターツは無駄になる）
• トイツ最大数 = 5 - 完成メンツ数 - 採用ターツ数 = 5 - 1 - 3 = 1
  • よって、採用するトイツ数は 1 となる

最終的に、シャンテン数は、8 - (1 x 2) - 3 - 1 = 2 と計算できます。 あと 2 枚で聴牌するリャンシャンテンですね。

メンツ、ターツ、トイツを数える

シャンテン数の計算式を定義できたので、あとは、手牌の中のメンツとペア（ターツ or トイツ）の数が分かればシャンテン数を計算できます。 手牌の中からメンツあるいはペアを抽出するときの形は、たかだか次のようなパターンしか存在しないので、このパターンの組み合わせを総当たりで抽出してみて、一番シャンテン数が少なくなったものが求めたいシャンテン数になるはずです。

• ブロック抽出パターン
  1. メンツ（刻子）… 1p1p1p
  2. メンツ（順子）… 1p2p3p
  3. 対子 … 1p1p
  4. ターツ（連続形）… 1p2p
  5. ターツ（嵌張形）… 1p3p

シンプルに実装するなら、初歩的なバックトラックを使って全探索してしまえば OK です。 最適化手法としては、

• 完全な孤立牌を最初に削除してから処理する
• 同一色の手牌パターンから、ブロック構成を求めるテーブルを用意しておく

などがあるようですが、何百万回も実行するようなシミュレーションでなければ、単純なバックトラックだけでも速度的には問題なさそうです。

ソースコードは後ほど公開予定です。