Weaponised Boredom

Like all nerds, I don't get to choose my obsessions. For a day or two some years ago I was taken over by the question of how long a game of Snakes & Ladders actually last for. I wrote a quick little simulation, which has since grown into a handy little multithreaded benchmark. I've run it to compare the performance of every Raspberry Pi ever released, for example.

It's written in pure-python without any external dependencies. Even though individual game lengths vary tremendously, once you play more than a few thousand rounds it tends to even out. There's lots of dictionary look-ups, appending to lists, and of course random number generation. It's nice to be able to copy a single file into a new environment and get a quick feel for how fast its Python runs. It's also been a fun platform to learn different techniques.

Slowest and Fastest

My slowest computer right now is the original Raspberry Pi Zero. Under Python 3.11 it can run 2,629 games per second on its single core. My desktop is an AMD Ryzen 5750 with 16-cores. Using all of  those cores gets us 3,632,912 games per second under Python 3.11 and more than 18 million with PyPy3!

I'd rewrite in native code if it were (I'm dying to try writing a Python module in Rust). I write mostly Python those days, so

Download Script

The program is just a single-file command-line script that you can download here. There's lots of code to combine results and run under multiple cores, but the core program is simple:

SNAKES_AND_LADDERS = {
    # Ladders
    1: 38,
    4: 14,
    9: 31,
    21: 42,
    28: 84,
    36: 44,
    51: 67,
    71: 91,
    80: 100,
    # Snakes
    98: 78,
    95: 75,
    93: 73,
    87: 24,
    64: 60,
    62: 19,
    56: 53,
    49: 11,
    48: 26,
    16: 6,
}
def snakes_and_ladders() -> Game:
    moves = []
    place = 0
    while True:
        roll = int(6 * random.random()) + 1
        landed = place + roll
        if landed > 100:
            # Too high, ignore
            pass
        else:
            # Special move or as rolled
            place = SNAKES_AND_LADDERS.get(landed, landed)
        moves.append((roll, place))
        # Won? Require exact roll.
        if place == 100:
            return moves

Rules

If you roll greater than needed to land on 100 you stay where you are. The snakes and ladder positions are copied from the old board we used that most boring afternoon.

Sidebar: Python randint() is Slow

I'm not the first to notice that Python's random.randint() is slow. About half the  runtime of the current version is spent simulating rolls of the dice, but it used to be about three-quarters. Mostly this is because a Python has arbitrary-precision integers. While I only need numbers between one and six, `random.randint()` would happily generate numbers with many thousands of digits. As ever in software, that sort of flexibility does not come for free.

Let's compare a few methods of generating our dice rolls, just for fun. The most straight-forward implementation takes 189 nanoseconds per roll:

$ python3 -m timeit -s 'import random' 'random.randint(1, 6)'
2000000 loops, best of 5: 189 nsec per loop

That's faster than I can do it, but pretty slow. I'd love to break my standard-library only restriction and use NumPy to pre-roll 100,000 dice in advance. That would get me down to 2.3 nanoseconds per roll:

$ python3 -m timeit -s \
    'import numpy as np' \
    'np.random.default_rng().integers(low=1, high=6, size=100_000)'
1000 loops, best of 5: 225 usec per loop
>>> 225e-6/100_000
2.25e-09

I've compromised and used a little integer maths instead, getting us to 66 nanoseconds:

$ python3 -m timeit -s 'import random' 'int(6 * random.random()) + 1'
5000000 loops, best of 5: 66.2 nsec per loop

---

Updated 27 Apr 2024, first published 28 Jan 2024