3 releases
0.1.2 | Oct 3, 2022 |
---|---|
0.1.1 | Oct 3, 2022 |
0.1.0 | Oct 3, 2022 |
#1827 in Algorithms
17KB
210 lines
Tenhou Deck/Wall-Shuffling Algorithm
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:
-
Generate 9 chunks of 1024 bits (
[u32; 288]
) from the game-wide RNG. This array is namedsrc
in the original algorithm description. This is implemented assrc_from_mt
. -
For every 1024-bit chunk (
[u32; 32]
, little-endian), calculate its SHA512 hash. All 9 chunks of 512 bits are concatenated into[u32; 144]
. This array is namedrnd
in the original algorithm description. This is implemented asrnd_from_src
.
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 toi..n
asi + rnd[i] % (n - i)
. This is implemented asshuffle_with_rnd
. - The shuffled wall array should be dealt from the highest index to the lowest.
Dependencies
~675KB
~14K SLoC