zenmumbler

Random

May 20, 2013

At the local casino the roulette tables have a big sign next to them showing the last 20 winning numbers, colour-coded black and red. It entices people to join, because with all that knowledge of past wins, your odds must be so much better! "8 black numbers in a row…, why not try your hand on red?"

In reality of course, the effect of those numbers on your chance to win will be negligible, but I am not xkcd and will not try to prove that here. A fact is though that if that sign gave people any significant advantage, it would not be there. The casino is not your friend.

Tricks like these play on people's notion of random numbers. True random is not what most people consider random at all. If I were to say I'd pick a random number between 1 and 1000000 inclusive, most people will give me a funny look when I pick 1 and not something like 838417.
My “flawed” method of picking the number is the point: people expect “random numbers” to conform to how a human mind would come up with an arbitrary number, which must be “interesting” and have multiple digits, preferably all unique.

1 -> not random
123321 -> kinda random
486137 -> random
3871264059 -> really random
1234567890 -> not random

In my first real job I worked at a company on to-order screen savers for Windows. Many of these were made up of a series of animated sequences, played continuously in random order. It wasn't long until the comments came in that the scene selection wasn't really random. A scene had played twice in a row, clearly something was wrong.

After some sniggering about this honest, but just plain wrong statement, we added the following function1:

int customerRandom(int min, int max) {
    static int lastVal = 0;
    int val = lastVal;

    while (val == lastVal)
        val = rangeRandom(min, max);
    return val;
}

It was a minimal solution to the problem — a scene could still occur twice in a three-scene time span — but customers all agreed that this was random enough.

A better solution would be a series of permutations of the possible items. This just so happens to be the algorithm newer Tetris games use as mandated by The Tetris Corporation a.k.a. Henk Rogers.

The original Tetris games used simple pseudo-RNG2s that did not do much, or at all, to make things easier for the player. In Ecstasy of Order they call a long period of time without a long bar a “drought”, which is often fatal for less experienced players3. The simple RNG is the cause, it's inevitable.

So Henk's team sat down one day and came up with a better way to dispense Tetris blocks, which they creatively titled the “Random Generator”. It conceptually works like this:

A. There are 7 distinct pieces in Tetris, number them 1 through 7 and put one of each in a metaphorical bag.

1 2 3 4 5 6 7

B. One by one, pick a random number out the of the bag and add it to a list that we'll call the permuted list.

Bag:
1 2 3 4 5 6 7 -> 1 2 3 4 6 7 -> 1 3 4 6 7 -> 1 4 6 7 -> 1 6 7 -> 1 7 -> 7 ->

Permuted list:
-> 5 -> 5 2 -> 5 2 3 -> 5 2 3 4 -> 5 2 3 4 6 -> 5 2 3 4 6 1 -> 5 2 3 4 6 1 7

In the diagram, the arrows -> indicate a number being picked, taken out of the bag and being appended to the permuted list4.

C. Whenever the game needs a new piece, pop the first number off the permuted list and return that.

5 2 3 4 6 1 7 -> 2 3 4 6 1 7 -> 3 4 6 1 7 -> 4 6 1 7 -> 6 1 7 -> 1 7 -> 7 ->

D. If the permuted list is empty, go back to A and the sequence starts anew with another permutation of the 7 pieces.

This algorithm is simple but it guarantees equal availability of all the pieces and a maximum drought of 12 pieces. This change in how Tetris worked was of course criticised as making the game easier for n00bs.

In early builds of my Tetris clone Quadrae I used a pure RNG for piece selection and I sometimes felt it was just unfair. “4 squares in a row? You've got to be kidding me!” What was wrong with this thing?

I quickly added the Henk-approved piece selection method and the game immediately felt more balanced and dare I say, reasonable. Though the pure random piece selection certainly elicited more extreme reactions from me, this was just plain better. Is it easier? Yes, but Tetris has enough stress-inducing qualities already, getting a few guarantees makes it less extreme, not any less of a game.

Numerical sequences in games need to be not overly obvious but also not too random. Obvious repetition or "duplicates" will distract the player and can make things boring. When the player's life directly depends on the next random number though, you should add grouping or result bias to your RNG so that players will not rage-quit and trash your app.

Leave numerical honesty to Hard Mode.

  1. The real version was in Pascal because we used Delphi, but bollocks to Pascal.
  2. RNG is Random Number Generator. It's pseudo because pure software RNGs are incapable of generating true random number sequences.
  3. The Tetris championships still use the NES version of Tetris, which has a simple RNG and therefore, droughts.
  4. When looking at the permuted list, did/do you feel a sense that I could have come up with a more random permutation? I rest my case.

Reply @zenmumbler to discuss this article.