概要

清一色のシャンテン数は01BFSで計算できる。
機械的な計算なので、正当性が簡単に証明できる。

シャンテン数とは

テンパイするまでに必要な牌の最小枚数のこと。
例えば 🀉🀊🀍🀎🀑🀒🀙🀚🀛🀜🀜🀀🀁 のとき、🀈🀌 を引いて🀀🀁を捨てればテンパイとなる。これより少ない枚数の入れ替えでテンパイすることはできないので、この手牌のシャンテン数は2となる。
この例のようにシャンテン数がわかりやすいケースがほとんどだが、清一色のような場合はシャンテン数を求めにくい。
特にプログラムでシャンテン数を計算する場合、正しいコードを書くことは難しい。また、正当性を保証するのも難しい。

考える問題

清一色だけを考える。以下では萬子🀇🀈🀉🀊🀋🀌🀍🀎🀏だけを扱う。
- 複数色ある場合や字牌を含む場合でも、清一色のシャンテン数さえ計算できていれば、軽いdpで解くことができるため。
- 正確には、x面子y雀頭を完成形とみなしたときの清一色のシャンテン数を全ての $0 \le x \le 4, \ 0 \le y \le 1$ について求めておく必要があるが、これらはほぼ同様に計算できる。
4面子1雀頭の一般手だけを考える。
- 七対子や国士無双のシャンテン数は、簡単な計算で求めることができるため。
副露は考えない。
- x回副露している場合は、4-x面子1雀頭を完成形とみなしてシャンテン数を求めれば良く、ほぼ同様の計算となるため。

Notation

手牌をで表す。
- $h_i :=$ 萬子 $i$ が何枚あるか。
次の条件を満たす手牌全体の集合をとおく。
- $0 \le h_i \le 4, \quad 1 \le i \le 9$
- $\sum_{i=1}^9 h_i \le 14$
手牌に対して、4面子1雀頭を作るのに必要な牌の最小枚数をとおく。
- 厳密には、4面子1雀頭を余りなく作れる手牌（以下完成形と呼ぶ）の集合を $W \subseteq H$ とおいて、 $r(h)$ を次で定義する。

$\displaystyle r(h) := \min_{w \in W} \sum_{i=1}^{9} \max(w_i - h_i, 0) \tag{1}$

手牌 $h$ のシャンテン数は $r(h) - 1$ となるので、 $r(h)$ を計算すれば良い。

$r(h)$ の計算

アイデア

重み付き有向グラフを以下で定める。

手牌全体の集合 $H$ を頂点集合とする。
次のルールで辺を張る。
- 手牌 $h \in H$ から、1枚牌を追加して得られる手牌に距離0の辺を張る。
  - 厳密には、各 $i=1,\dots,9$ に対して $h^{+i} := (h_1, \dots, h_i+1, \dots, h_9)$ とおき、 $h^{+i} \in H$ ならば $h$ から $h^{+i}$ に距離0 の辺を張る。
- 手牌 $h \in H$ から、1枚牌を削除して得られる手牌に距離1の辺を張る。
  - 厳密には、各 $i=1,\dots,9$ に対して $h^{-i} := (h_1, \dots, h_{i}-1, \dots, h_9)$ とおき、 $h^{-i} \in H$ ならば $h$ から $h^{-i}$ に距離1 の辺を張る。

このとき、完成形 $w \in W$ から $h \in H$ の最短距離を $d(w, h)$ とおくと、次の関係が成立する。

$r(h) = \min_{w \in W} d(w, h) \tag{2}$

証明

式 $(1)$ より、 $\sum_{i=1}^{9} \max(w_i - h_i, 0) = d(w, h)$ を示せば良い。

これは辺の張り方から簡単に従う。（ $w$ の牌を追加・削除して $h$ に一致させていく様子をイメージするとわかる。）

完成形 $w$ の列挙

面子は 7 + 9 通り
雀頭は 9 通り

であるから、 $(7 + 9)^{4} \times 9 = 589824$ 通りを考えて、その各牌の枚数 $h$ を計算する。

$1 \le i \le 9$ に対して $0 \le h_i \le 4$ を満たすものを完成形として列挙する。

$\min_{w \in W} d(w, h)$ の計算

辺の距離が0と1しかないので、01BFSを用いて計算することができる。

頂点数と辺の数を計算すると

頂点数 $|H|$ = 405350
辺の数 $|E|$ = ~~3648150~~ 4791600

となる。 $O(|H| + |E|)$ で $\min_{w \in W} d(w, h)$ を計算することができる。

実装とテスト

https://github.com/habara-k/flush-shanten

3.2GHz CPUと8GB RAMを用いたところ、

python実装では42±1[sec]
rust実装では2.15±0.08[sec]

程度となった。

python実装

import numpy as np
from collections import deque
from copy import deepcopy
import time


# 面子のリスト
sets = [
    np.array([1, 1, 1, 0, 0, 0, 0, 0, 0]),
    np.array([0, 1, 1, 1, 0, 0, 0, 0, 0]),
    np.array([0, 0, 1, 1, 1, 0, 0, 0, 0]),
    np.array([0, 0, 0, 1, 1, 1, 0, 0, 0]),
    np.array([0, 0, 0, 0, 1, 1, 1, 0, 0]),
    np.array([0, 0, 0, 0, 0, 1, 1, 1, 0]),
    np.array([0, 0, 0, 0, 0, 0, 1, 1, 1]),
    np.array([3, 0, 0, 0, 0, 0, 0, 0, 0]),
    np.array([0, 3, 0, 0, 0, 0, 0, 0, 0]),
    np.array([0, 0, 3, 0, 0, 0, 0, 0, 0]),
    np.array([0, 0, 0, 3, 0, 0, 0, 0, 0]),
    np.array([0, 0, 0, 0, 3, 0, 0, 0, 0]),
    np.array([0, 0, 0, 0, 0, 3, 0, 0, 0]),
    np.array([0, 0, 0, 0, 0, 0, 3, 0, 0]),
    np.array([0, 0, 0, 0, 0, 0, 0, 3, 0]),
    np.array([0, 0, 0, 0, 0, 0, 0, 0, 3]),
]

# 雀頭のリスト
heads = [
    np.array([2, 0, 0, 0, 0, 0, 0, 0, 0]),
    np.array([0, 2, 0, 0, 0, 0, 0, 0, 0]),
    np.array([0, 0, 2, 0, 0, 0, 0, 0, 0]),
    np.array([0, 0, 0, 2, 0, 0, 0, 0, 0]),
    np.array([0, 0, 0, 0, 2, 0, 0, 0, 0]),
    np.array([0, 0, 0, 0, 0, 2, 0, 0, 0]),
    np.array([0, 0, 0, 0, 0, 0, 2, 0, 0]),
    np.array([0, 0, 0, 0, 0, 0, 0, 2, 0]),
    np.array([0, 0, 0, 0, 0, 0, 0, 0, 2]),
]


# hand -> int (5進数とみなす)
def encode(hand):
    ret = 0
    for e in hand:
        ret = (ret * 5) + e
    return ret


# int -> hand
def decode(hash):
    ret = np.zeros(9, dtype=int)
    for i in range(9):
        ret[8-i] = hash % 5
        hash //= 5
    return ret


# 4面子1雀頭の形を列挙
def complete_hands():
    ret = {}
    for s1 in sets:
        for s2 in sets:
            for s3 in sets:
                for s4 in sets:
                    for head in heads:
                        hand = s1 + s2 + s3 + s4 + head
                        if (hand <= 4).all():
                            ret[encode(hand)] = hand
    return ret


# 01BFSを用いてシャンテン数を計算
def bfs(W):
    dist = {}
    deq = deque()
    for hash, hand in W.items():
        dist[hash] = 0
        deq.append((hash, hand))

    while len(deq) > 0:
        hash, hand = deq.popleft()
        for k in range(9):
            if hand[k] < 4 and sum(hand) < 14:
                hand_add = deepcopy(hand)
                hand_add[k] += 1
                hash_add = encode(hand_add)
                if hash_add not in dist:
                    dist[hash_add] = dist[hash]
                    deq.appendleft((hash_add, hand_add))
            if hand[k] > 0:
                hand_sub = deepcopy(hand)
                hand_sub[k] -= 1
                hash_sub = encode(hand_sub)
                if hash_sub not in dist:
                    dist[hash_sub] = dist[hash] + 1
                    deq.append((hash_sub, hand_sub))

    return dist


def main():
    W = complete_hands()
    shanten = bfs(W)
    assert(len(shanten) == 405350)

    # 計算結果を保存
    with open("shanten.txt", mode='w') as f:
        for hash, shanten in shanten.items():
            hand = decode(hash)
            f.write("{} {} {} {} {} {} {} {} {} {}\n".format(
                hand[0], hand[1], hand[2], hand[3], hand[4],
                hand[5], hand[6], hand[7], hand[8], shanten))


if __name__ == '__main__':
    start = time.time()
    main()
    elapsed_time = time.time() - start
    print("elapsed_time: {} [sec]".format(elapsed_time))

rust実装

use std::collections::{VecDeque, BTreeSet, BTreeMap};
use std::fs;
use std::io::Write;
use std::time::Instant;

// 4面子1雀頭の形を列挙
fn complete_hands() -> BTreeSet<Vec<i32>> {
    // 面子のリスト
    let sets = vec![
        vec![1, 1, 1, 0, 0, 0, 0, 0, 0],
        vec![0, 1, 1, 1, 0, 0, 0, 0, 0],
        vec![0, 0, 1, 1, 1, 0, 0, 0, 0],
        vec![0, 0, 0, 1, 1, 1, 0, 0, 0],
        vec![0, 0, 0, 0, 1, 1, 1, 0, 0],
        vec![0, 0, 0, 0, 0, 1, 1, 1, 0],
        vec![0, 0, 0, 0, 0, 0, 1, 1, 1],
        vec![3, 0, 0, 0, 0, 0, 0, 0, 0],
        vec![0, 3, 0, 0, 0, 0, 0, 0, 0],
        vec![0, 0, 3, 0, 0, 0, 0, 0, 0],
        vec![0, 0, 0, 3, 0, 0, 0, 0, 0],
        vec![0, 0, 0, 0, 3, 0, 0, 0, 0],
        vec![0, 0, 0, 0, 0, 3, 0, 0, 0],
        vec![0, 0, 0, 0, 0, 0, 3, 0, 0],
        vec![0, 0, 0, 0, 0, 0, 0, 3, 0],
        vec![0, 0, 0, 0, 0, 0, 0, 0, 3],
    ];

    // 雀頭のリスト
    let heads = vec![
        vec![2, 0, 0, 0, 0, 0, 0, 0, 0],
        vec![0, 2, 0, 0, 0, 0, 0, 0, 0],
        vec![0, 0, 2, 0, 0, 0, 0, 0, 0],
        vec![0, 0, 0, 2, 0, 0, 0, 0, 0],
        vec![0, 0, 0, 0, 2, 0, 0, 0, 0],
        vec![0, 0, 0, 0, 0, 2, 0, 0, 0],
        vec![0, 0, 0, 0, 0, 0, 2, 0, 0],
        vec![0, 0, 0, 0, 0, 0, 0, 2, 0],
        vec![0, 0, 0, 0, 0, 0, 0, 0, 2],
    ];

    let mut ret: BTreeSet<Vec<i32>> = BTreeSet::new();
    
    for s1 in sets.iter() {
        for s2 in sets.iter() {
            for s3 in sets.iter() {
                for s4 in sets.iter() {
                    for head in heads.iter() {
                        let hand: Vec<i32> = (0..9).map(|i| {
                            s1[i] + s2[i] + s3[i] + s4[i] + head[i]
                        }).collect();
                        if hand.iter().all(|&h| h <= 4) {
                            ret.insert(hand);
                        }
                    }
                }
            }
        }
    }

    ret
}

// 01BFSを用いてシャンテン数を計算
fn bfs(ws: BTreeSet<Vec<i32>>) -> BTreeMap<Vec<i32>, i32> {
    let mut dist: BTreeMap<Vec<i32>, i32> = BTreeMap::new();
    let mut deq: VecDeque<Vec<i32>> = VecDeque::new();

    for hand in ws {
        dist.insert(hand.clone(), 0);
        deq.push_back(hand);
    }

    while !deq.is_empty() {
        let hand = deq.pop_front().unwrap();
        let sum: i32 = hand.iter().sum();
        for k in 0..9 {
            if hand[k] < 4 && sum < 14 {
                let mut hand_add = hand.clone();
                hand_add[k] += 1;
                if !dist.contains_key(&hand_add) {
                    dist.insert(hand_add.clone(), dist[&hand]);
                    deq.push_front(hand_add);
                }
            }
            if hand[k] > 0 {
                let mut hand_sub = hand.clone();
                hand_sub[k] -= 1;
                if !dist.contains_key(&hand_sub) {
                    dist.insert(hand_sub.clone(), dist[&hand] + 1);
                    deq.push_back(hand_sub);
                }
            }
        }
    }

    dist
}

fn main() {
    let start = Instant::now();
    let ws = complete_hands();
    let shanten = bfs(ws);
    assert_eq!(shanten.len(), 405350);

    // 計算結果を保存
    let mut f = fs::File::create("shanten-rs.txt").unwrap();
    for (hand, sh) in shanten {
        f.write_all(format!("{} {} {} {} {} {} {} {} {} {}\n",
            hand[0], hand[1], hand[2], hand[3], hand[4],
            hand[5], hand[6], hand[7], hand[8], sh
        ).as_bytes()).unwrap();
    }
    let elapsed_time = start.elapsed().as_nanos() as f64 
        / 1_000_000_000 as f64;
    println!("elapsed_time: {} [sec]", elapsed_time);
}

また、こちらのリポジトリの実装と結果が一致することを確かめた。

https://github.com/tomohxx/shanten-number-calculator

参考

[麻雀]シャンテン数計算アルゴリズム - Qiita

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

yukinote

清一色のシャンテン数を01BFSで計算する

概要

シャンテン数とは

考える問題

Notation

$r(h)$ の計算

アイデア

完成形 $w$ の列挙

$\min_{w \in W} d(w, h)$ の計算

実装とテスト

参考

概要

シャンテン数とは

考える問題

Notation

の計算

アイデア

完成形 の列挙

の計算

実装とテスト

参考

$r(h)$ の計算

完成形 $w$ の列挙

$\min_{w \in W} d(w, h)$ の計算