Puyo Puyo Tsu/Random Number Generator

When the game gives the player random pairs, there obviously is some logic to it. In most computer systems, randomization is not actually random and can be predicted: one has to know the algorithm and how it is used, to then infer some properties that make it predictable.

Puyo Puyo Tsu is no exception, and has what is called a random number generator (RNG). This page describes how it works.

Overall RNG mechanics

• a variable is declared to stand for the current random value (rng_val);
• when the system boots, this variable is set to a predefined value;
• a function then modifies this value every time it is called, based on various parameters, but should attempt to make it difficult to predict the next value;
• when needed, read the variable and "iterate" the random value so that the next code chunk that wants a random value does not get the same as yours.

Puyo Puyo Tsu has those functions and variables:

• the game stores the current random value at 0xFFA134;
• it is initialized at boot time by function sub_2216 (subroutine which code begins at 0x002216), which initializes the game options to their default values. With instruction 0x222C the routine writes the default "random" value of 0x35879DE2;
• function sub_C04 is the "iterator", equivalent to rand() in most programming languages, which picks the next random value based on its calculations and the old value stored in that variable.

Function offsets are specific to the Genesis version.

On the arcade version, the initialization function lies at 0x23FA and the rand iterator function is at 0x4AA. The initial value of the rng_val variable is the same.

RNG implementation

Here's the initialization function:

And here's the rand() iterator function:

This RNG function calculates the next value as follows:

• assign old value to d0 from the variable in RAM, adding it to the current d0 content
• add the value of the stack pointer register to d0
• rotate the contents of d0 by 5 bits to the left: higher bits get placed at the lowest place
• add the old value to d0
• increment d0 by one
• store the new value to the variable in memory

The function also returns the generated value, as it is not erased from d0: that's the return value, a new 32-bit random number.

Sample C code

The following C code accurately mimics Puyo Puyo Tsu's randomization behaviour:

#include <stdio.h>
#include <stdlib.h>

#define TRIALS 1<<16

unsigned int _rotl(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
        return value;
    return (value << shift) | (value >> (sizeof(value)*8 - shift));
}
 
unsigned int _rotr(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
        return value;
    return (value >> shift) | (value << (sizeof(value)*8 - shift));
}

int main(int argc, const char** argv)
{
   unsigned int seed = 0x35879DE2;
   unsigned int i;
   unsigned int tmp;

   printf("sizeof(unsigned int): %ld bits\n", sizeof(unsigned int)*8);
   if(sizeof(unsigned int) != 4)
      puts("WARNING: integer type is not 32-bit long");

   for (i = 0; i < TRIALS; i++) {
      /* tmp holds d0 value that depends from where the function is called, 
      so is a yet unknown variable.
      The following initialization is accurate for the first 7 values of the RNG, 
      if you let the animation play through, on the genesis.
      
      For the color-set shuffling, it holds 0x00000004.
      For the pool randomization process, it holds the previous RNG value masked 
      with 0xFFFF00FF, and is initialized to 0x4AD00000.
      */
      if(i%2 == 0)
         tmp = 0xF1;
      else 
         tmp = 0xF0;
      tmp += seed;
      printf("0x%08X ", tmp);
      tmp += (unsigned int) 0x00FF7FE8; /* 0x00FF7FF4 most likely to be the sp at generation */
      printf("0x%08X ", tmp);
      tmp  = _rotl(tmp,5);
      printf("0x%08X ", tmp);
      tmp += seed;
      printf("0x%08X ", tmp);
      tmp++;
      printf("0x%08X \n", tmp);
      seed = tmp;
      
      printf("0x%08x: %3d (0x%02x) [mod 4: %d]\n", seed, seed & 0xFF, seed & 0xFF,(seed & 0xFF)%4);
   }
   
   return EXIT_SUCCESS;
}

The code will generate 65536 values and print the results. tmp stands for the d0 register. _rotl() is the rotation function. Beware, this code sample only works on systems where unsigned int is a 32-bit wide type.