Impractical Random Number Generators

Computers are notoriously bad at generating random numbers. To the point where programmers are relying on using tricks such as using your mouse movement to add entropy to the system, or using dedicated hardware that makes use of nuclear decay to extract randomness out of the unpredictable radiations.

Random Number Generation is also compute intensive, which has been a performance issue in the past, if you look at the source code for the original Doom game, you will see their RNG is a simple, pre-scrambled list of integers, and any time you need a random number, the system just takes the next one in the list, and hopes you won't notice.

Today I want to join the fight and research more Random Number Generators.

Tamagotchi

Tamagotchi

This is a Tamagotchi. And I swear this will become relevant later, just bear with me for now. Tamagotchi is an electronic pet companion that was released in 1996 by Bandai. You can feed it, play with it, clean its poop, it sleeps at night, just like a real pet! A few years ago Randall Munroe, creator of the brilliant web comic xkcd, proposed the idea of running a simulated network of Tamagotchi where they live and play, and eat and sleep.

xkcd Tamagotchi hive

That's what we're doing today.

Single Tamagotchi

Creature

We are going to make a legally distinct simulation called "Cute Cat Creature Pals", or CCCP for short. The creature lives in a device, and has three stats: Food, Rest, Happiness, ranging from 0 to 100. These stats are initialized pseudo-randomly based on the ID of the creature. At every tick of the clock, every step in the simulation, the stats will decay by a certain amount.

public class Creature
{
    private int m_id;

    private int m_foodStat;
    private int m_sleepStat;
    private int m_happinessStat;

    private int InitializeStat(int seed, int statId, int min, int max)
    {
        int v = seed * 123 + statId * 456;

        v = Math.Abs(v);
        v %= max;

        return Mathf.Clamp(v, min, max);
    }

    public void Tick()
    {
        m_foodStat      = StatDecay(m_foodStat,      Settings.FoodDecay,      Settings.MinFoodStat,      Settings.MaxFoodStat);
        m_sleepStat     = StatDecay(m_sleepStat,     Settings.SleepDecay,     Settings.MinSleepStat,     Settings.MaxSleepStat);
        m_happinessStat = StatDecay(m_happinessStat, Settings.HappinessDecay, Settings.MinHappinessStat, Settings.MaxHappinessStat);

        ExecuteCurrentState();
    }
}

To get these stats back up, the Creature has a State Machine to decide what to do based on how they feel.
If Food falls below a certain threshold, they will switch to state Eat , during which their Food stat increases by a set amount at every step of the simulation, until they are full. Similarly, if they are too tired, they will switch to state Sleep to get some Rest. By default, they are in Idle state, or Play state, and their happiness increases.

public enum EState
{
    Idle = 0,
    Eat = 1,
    Sleep = 2,
}

That's one creature done, and it could run forever with this simple State Machine. But for the purpose of today's video, which, again, bear with me it's going to makes sense eventually, we're going to need something a lot more complex. So we will add more creatures.

Multimagotchi

10 Simulated Creatures

Here's a simulation with 10 creatures, and we're going to add the ability to visit each other. Let's see, so when a creature is at home and doesn't have much to do (they're rested, they're not hungry), the State Machine will now decide to start traveling to another creature's house. The ID of the creature we want to visit is also initialized using the creature's ID as seed.

Traveling takes 4 simulation steps, and upon arriving to the house of the target creature, they will switch their state to Visiting. While visiting, their happiness stat increases significantly faster. After 10 simulation ticks the visitor will travel back home.

public enum EState
{
    Idle = 0,
    Eat = 1,
    Sleep = 2,

    TravelingTo = 3,
    Visiting = 4,
    TravelingFrom = 5,
}

Now obviously the simulation continues, and if the host is hungry and needs to eat, both creatures will eat together. If the host gets sleepy, they will not go to sleep, unless they reach a critical threshold in which case they will kick the visitor out in order to get some sleep.

Upon returning home, the visitor will increase their m_nextVisitingTarget in order to visit a different creature next time.

SetNextVisitingTarget(m_nextVisitingTarget + 1);
// Pick the next creature we will visit

Of course, some times popping in unannounced at your friend's house doesn't work out. If a traveler reaches another house and the host is unavailable, either sleeping, or already hosting someone else, or they're themselves away on travel, the traveler returns home.

Randomagotchi

Gris of simulated creatures

We now have a simulation of 10 creatures, but that number is configurable in the constructor so we could have 1000 creatures if we wanted. And here's the part where we finally circle back to random number generation. This is all a rather complex bundle of stats, states, IDs, and at any point in time, you wouldn't be able to predict the next state of the simulation without knowing the entire state and running the code yourself. Which means we could take the simulation, convert it to bytes, brutally cast it to an integer, and that's a perfectly valid random number.

private int InternalSample()
{
    m_simulation.Tick(); // Advance the simulation

    var bytes = ObjectToByteArray(m_simulation); // Convert the whole simulation to bytes
    var hash =  ComputeHash(bytes);
    /* Note: we hash the bytes array in order to scramble them and make sure
    that two close states are going to give numbers that are very different*/

    int result = System.BitConverter.ToInt32(hash, 0);

    return Math.Abs(result);
}

We just need to write a quick class that initializes an internal simulation of creatures, and provides an interface to generate a double, and int, a number in a range, you name it.

// Example uses of the Creature.Random class
var simulation = new Random(creatureCount: 10, seed: 0);
int i       = simulation.Next();
double d    = simulation.NextDouble();
float f     = simulation.value;
f           = simulation.Range(3, 15);

And with every call to the RNG, the simulation advances one step. It's a bit more compute intensive than using System.Random but to be honest it's not that much work for modern CPUs.

Now as a bonus, since this simulation is initialized from a number of creatures and a seed, the state after an arbitrary number of steps in the simulation is actually deterministic. It's hard to guess, but it's deterministic. Which means you could use this to produce authenticator tokens (This is obviously not cryptographically safe), and those hardware key fobs could totally run a simulation of a few hundred tamagotchi to generate tokens, a small tamagovillage in your pocket. Heck maybe they already do for all we know.

RSA SecurID key fob

Twitter Bot

Of course, this is random but it's not random random. A fair way to decide on a random number would be a democratic process. Asking strangers on the internet is always a good call in all situations, so we will head to the "town square" of the internet, Twitter. What could go wrong?

Let's make a simple Twitter bot. When calling it with a range of numbers, it will post a tweet, asking strangers to respond to the thread with a random number in that range. Now you will need to trust them to actually respond with a number and not memes. But people on the internet are trustworthy.

Tweets of the Twitter bot

Tune-in for my next twitter bot that just executes random tweets as code with root privileges.

And obviously, while you're waiting for a number to be provided, the main thread in your game or program will be stalling, awaiting a result. And that might take a while, depending on your follower count and on the tantrums of a billionaire.

Stalling pending a random number

Actually fair RNG

Of course, this is random but can always be manipulated by an adversary. What is globally accepted as a fair random generation method is rolling dice.

So we're going to build a dice launcher thrower device thing. What I'm imagining is a box, in which there's a die. The die is placed on a plate, which itself is mounted on springs. And then some motors will apply pressure on the plate, and when they release the plate, it will shoot up, be stopped by solid stops, and the momentum will propel the die upward against the top of the box.

Finally after much trouble with the springs and the motors and everything, I completed building the box, there's a raspberry pi, a few buttons and stuff, then a lot of cabling to the motors, and this is it, I did make walls for it but it was too tedious to access the die in the middle and reposition the plate so I didn't install them.

The DiceShuffler

In the end it sort of works, but as you can see in the video the motors, despite being all setup the same way, don't apply pressure in the exact same manner, and as a result the die isn't properly shuffled, it's barely toppled. I would have expected it to be propelled higher.

Also the whole system is pretty unstable, the plate keeps sliding around, I should have added some sort of guard rails to guide it vertically. Maybe I should stick to software engineering. Speaking of which, the die being shuffled enough we can film it with a raspberry-pi compatible camera.

Raspberry Pi camera

It's pretty low resolution but it works fine in our case, the program must then apply some treatment on the image to binarize it and count the black clusters on the die.

Of course similarly to the twitter bot earlier, your game will be interrupted every time there is a need for a random number. A good thing though is that if the 1 to 6 range isn't right, the game could prompt the user to change the dice inside the box, to insert either a die with more faces, or just multiple dice.

Stalling pending a dice change

Conclusion

There you go! That's 3 Random Number Generators that are totally 100% viable options for your game project or your bitcoin exchange platform. The Tamagotchi source code is available on the Patreon, and until next time, have a good one!

Check these out

Interesting stuff featured in the video and/or more stuff about boids:

Music Credits