#shuffle #game #mt19937 #riichi #mahjong

no-std tenhou-shuffle

Tenhou Deck/Wall-Shuffling Algorithm

3 releases

0.1.2 Oct 3, 2022
0.1.1 Oct 3, 2022
0.1.0 Oct 3, 2022

#1827 in Algorithms

MIT license

17KB
210 lines

Tenhou Deck/Wall-Shuffling Algorithm

Crates.io docs.rs

Tenhou is an online Japanese Riichi Mahjong game. As of 2022-10-02, Tenhou has published their algorithm for shuffling the deck / wall of tiles, alongside with validation data for a particular game seed, including intermediate results.

This crate re-implements the published algorithm for reconstructing the full shuffled wall of any game from its RNG seed.

This crate is no_std.

MT19937 RNG

This crate bundles an implementation of MT19937, copy-pasted from https://crates.io/crates/mt19937. This is mostly for no_std compatibility.

  • Seed: [u32; 624].
  • Raw output type: u32.

The Algorithm

Assuming u32 is little-endian (LSByte first) in byte buffers.

Each game begins by seeding an MT19937 RNG for the game. This seed can be retrieved as a base-64 encoding of the seed array.

Each round in the game requires a shuffle. We first derive the randomness as follows:

Then, we shuffle the wall with rnd:

  • Start with wall = sorted array of all tiles; length = 136 (4 players) or 108 (3 players).
  • Perform a low-to-high Fisher-Yates Shuffle, using rnd[i] as the random number table, scaled to i..n as i + rnd[i] % (n - i). This is implemented as shuffle_with_rnd.
  • The shuffled wall array should be dealt from the highest index to the lowest.

Dependencies

~675KB
~14K SLoC