On the Shanten Number Calculation Algorithm

[Apricot-S]

1. Document that the shanten number is defined with respect to X melds and 1 pair, where the value of X is determined by the current number of tiles in the hand.
2. The known issue that shanten numbers may be inaccurate for hands containing 3n tiles.
   -> resolved in bug: stabilize shanten input validation #242
3. Whether the shanten number calculation algorithm should be modified or extended in version v2.1.
   -> not to change

[Apricot-S]

Regarding Topic 2:

The current algorithm does not appear to return a consistent shanten number for a hand of 3n tiles.

Example:

# ruff: noqa: D103, T201

from mahjong.shanten import Shanten
from mahjong.tile import TilesConverter


def print_shanten(mpsz: str) -> None:
    tiles = TilesConverter.one_line_string_to_34_array(mpsz)
    print(f"shanten for {mpsz}: {Shanten.calculate_shanten(tiles)}")


print_shanten("")
print()

print_shanten("1m")
print_shanten("12m")
print_shanten("123m")
print_shanten("124m")
print_shanten("135m")
print()

print_shanten("1m")
print_shanten("11m")
print_shanten("111m")

Output:

shanten for : 0

shanten for 1m: 0
shanten for 12m: 0
shanten for 123m: 0
shanten for 124m: 1
shanten for 135m: 1

shanten for 1m: 0
shanten for 11m: -1
shanten for 111m: 0

[Nihisil]

I wonder if we just should reject tile counts that are divisible by 3 with a clear ValueError. All valid game-state tile counts (1 or 2 mod 3, up to 14) will continue to work exactly as before.

What do you think?

[Apricot-S]

I agree with your suggestion. Other shanten number calculation libraries, such as Cryolite/nyanten, Apricot-S/xiangting, and zurukumo/kago-utils, also reject hands where mod 3 == 0.

Some expected score calculation algorithms require calculating the shanten number of a hand, including any surplus tiles drawn, but this library does not need to handle this.

This is a breaking change from behavior up to and including v1.4.0, so the CHANGELOG and docstring must be updated.

[Apricot-S]

It was resolved in #242 .

[Apricot-S]

Regarding Topic 3

Personally, I'm reluctant to change or add to the algorithm.

There are roughly three methods for calculating Shanten numbers:

1. Backtracking

   • this library
   • kobalab/majiang-core

2. Pruning DFS

   • https://github.com/gimite/MjaiClients/blob/master/src/org/ymatsux/mjai/client/ShantensuUtil.java

3. Calculating the values for single color and then finding the smallest combination of those values

   • 01-BFS: habara-k/flush-shanten
   • pre-calculated tables: tomohxx/shanten-number, Apricot-S/xiangting

Each method has its own issues.

1. Backtracking
   Without correction, if four identical tiles are held and become isolated, the calculated shanten number will be one less than the correct value (This library has already corrected this.)

2. Pruning DFS
   Since the hand is compared with all winning hands at runtime, the calculation time is extremely slow.

3. Calculating the values for single color and then finding the smallest combination of those values
   There are two methods for calculating the value for one suit: 01-BFS and pre-calculated tables.
   Both methods require MBs of memory.

[Apricot-S]

For reference, I present benchmarks for each algorithm (all implemented in Rust).

Repository: https://github.com/Apricot-S/shanten-algorithm-collection

Note: The value shown as ns/iter represents the total time for 10,000 calculations, and dividing that value by 10,000 gives the time per single calculation.

1. Backtracking (No correction)

test benches::bench_shanten_full_flush_10000       ... bench: 1,463,496,270.00 ns/iter (+/- 45,048,797.00)
test benches::bench_shanten_half_flush_10000       ... bench: 112,692,940.00 ns/iter (+/- 4,668,478.00)
test benches::bench_shanten_normal_10000           ... bench:  41,778,860.00 ns/iter (+/- 3,150,787.00)
test benches::bench_shanten_thirteen_orphans_10000 ... bench:  15,417,830.00 ns/iter (+/- 787,616.00)

2. Pruning DFS

test benches::bench_shanten_full_flush_10000       ... bench: 129,226,490.00 ns/iter (+/- 6,276,463.00)
test benches::bench_shanten_half_flush_10000       ... bench: 672,604,550.00 ns/iter (+/- 10,311,966.00)
test benches::bench_shanten_normal_10000           ... bench: 1,670,836,090.00 ns/iter (+/- 20,481,109.00)
test benches::bench_shanten_thirteen_orphans_10000 ... bench: 981,470,600.00 ns/iter (+/- 20,996,472.00)

3. Calculating the values for single color and then finding the smallest combination of those values (Apricot-S/xiangting)

test benches::bench_shanten_full_flush_10000       ... bench:     668,670.00 ns/iter (+/- 120,003.50)
test benches::bench_shanten_half_flush_10000       ... bench:     671,905.00 ns/iter (+/- 241,495.62)
test benches::bench_shanten_normal_10000           ... bench:     667,535.00 ns/iter (+/- 82,399.50)
test benches::bench_shanten_thirteen_orphans_10000 ... bench:     654,400.00 ns/iter (+/- 95,602.00)

[Nihisil]

Thank you for detailed explanation. Given all provided context I agree with you to keep backtracking algorithm implementation in this library. We can add section to wiki and/or readme with links to xiangting-py for these who wants to try different algorythm, what do you think about that?

[Apricot-S]

Thank you for the suggestion. I also think including a link to xiangting‑py is a good idea, since it gives users a clear option to explore alternative shanten algorithms.

As for where to place this information, adding it to the README makes sense to me. Whether we should also put it in the Wiki might depend on how much detail we want to provide. I’d like to check how other projects structure similar content (for example, polars, burn, rolldown, oxc) before deciding.

Another point is whether we want to list only Python implementations/bindings or also include C++ and Rust libraries.
Let me know what you think about this direction.

[Nihisil]

We are publishing readme to pypy as is, so probably it is not a right place for the libs directory.

I'm thinking about separate wiki page where we can list other mahjong libraries we know for better visibility (they can be in any language).

[Apricot-S]

I've created a separate discussion for this topic. Let’s continue there.
#245