Why is a Hibernating Squirrel like a Computer Game from 1984?
And other questions you’ve always wondered but been too afraid to ask
Imagine you were trying to describe how to dance the ‘Hokey Cokey’ to someone. You could sing them the song, but that takes about three minutes (and gets stuck in your head). Could you do it faster?
Suppose you showed them how to do just one verse (say, the verse about the left arm). That would take about 40 seconds. Then you could tell them that they do the same thing with their right arm, their left leg, their right leg, and their whole self. We could be done with explaining the Hokey Cokey in under a minute.
Squirrels: A History
In the Autumn, squirrels bury nuts; then they go to sleep in their nests (called drays). Although they sleep a lot during the Winter, this isn’t technically hibernation, because they do wake up to eat. When they wake up, they go to where they buried the nuts, dig them up, and eat them. What a clever squirrel. Most of us can’t remember where we left our keys yesterday.
What if squirrels couldn’t remember things? How would you design a squirrel if memory was expensive? What’s more, perhaps we could imagine that squirrel memory was write once — a squirrel gets to remember a specific number of things and then it can’t remember any more… How would you make sure that he could, almost unfailingly, go back to where he left his nuts?
Perhaps you might be tempted to make sure the squirrel could smell nuts so he didn’t have to remember where he put them? It’s a nice thought, but not a great idea in practice. The whole point of burying the nuts so they can’t be seen is to stop other animals making off with them. If they’re buried close to the surface and can be smelled from some distance away, they’re going to get eaten by the Winter Nut Snaffler and the poor squirrel is going to be left with nothing. We’ve got to go deeper than that, both underground and in theory.
So the problem is to hide the nuts somewhere where we can find them again later, without having to remember where they went.
Let’s go on a short digression. Suppose you and I have a deck of cards each, and we each shuffle our deck and take the top card. We wouldn’t normally expect to get the same card out. But if we start with the decks in the same order, and then shuffle them in exactly the same way, the new order will be the same for your deck and mine, so we’ll draw the same card. Crucially, as long as we know what we’re doing, the steps can be pretty simple but still result in an apparently arbitrary choice of card. Let’s say we both start with a deck in “new deck order”, which is something like all the hearts from Ace to King, followed by the clubs, followed by the diamonds, followed by the spades. Then we both take the top 17 cards off, put them through the rest of the deck at positions 5, 8, 11, and so on (starting at card 5 and leaving two cards between each of them, so they become every third card). Then we do the same thing with the top 27 cards starting at card 10 and putting a card in every fourth card: 10, 14, 18… When we get to the end of the deck with cards left over we’ll just keep counting from the beginning of the deck again. If we already know roughly how “interleaving” the cards works, we only need the numbers (17,5,3) and (27,10,4) to describe these operations. A few more sets of numbers and a casual glance won’t see much order in either of the decks of cards — but they’re still in the same order as each other, so when you and I draw the top card of our shuffled decks, they match. Magic!
Now let’s get back to the squirrel. What he needs is a method which, given a rough location (the area near his dray, say), chooses a hiding place. The method needs to give the same results in the Autumn as in the Winter, and then he can use it both for hiding the nuts, and for finding them. Wherever his method told him to bury the nuts, it will tell him to dig them up from the same place three months later.
It turns out this is exactly what squirrels do. They take the general layout of the scenery: tree positions, hill shapes and so on — which are similar in all seasons, and use that to select a hiding place. If you change the landscape around a sleeping squirrel, he won’t go back the the same place he buried his nuts (as a squirrel might if he remembered “they’re ten metres away to the Northwest”), and he won’t give up completely (as he might if he’d remembered what everything looked like and then you confused him), but instead he’ll go and confidently dig in a different place, because you’ve changed the inputs to his hiding place method, so he gets a different result. Similarly, if we tried to perform our dual-shuffle trick but someone set us up with two decks which started in different orders, we’d confidently draw two different cards, which would be embarrassing.
Come to think of it, this trick of ‘repeating the method’ is a pretty good way of working out where you left your keys last night, and a lot of people do it. “Now, if I came in through this door, in the dark, with my shopping in that hand, and my keys in this hand, I’d have put them down… in that bin. Oh dear… Quick, after that rubbish van!”
Now, about that Computer Game…
Glad you asked. Elite was a very successful computer game, released in 1984, in which you played the captain of a spaceship, trading goods around a galaxy and trying to raise your rating to ‘Elite’ (hence the snappy name).
Elite has a large universe of eight galaxies with 256 planets each. But the game was written for the BBC Micro, a computer with only 16KB of memory (remember this was 1984): that’s only about eight characters of data for each planet — even ignoring the amount of memory for the program instructions. That’s barely enough space to store the planet names! But these planets not only had a name, they had a location, a priced-up trading market with different goods, a system of government, and other descriptive details — which were always the same every time you opened the game. How could they do that?
The solution the designers came up with was to have the game generate the planets by a fixed procedure. Just as the squirrel comes to the same answer when it generates its hiding location the same way in the Autumn and the Winter, Elite gave the illusion of a large amount of stored data by storing one starting ‘seed’ value and then making all the other data the program needed depend on that seed, run through some sequence of steps. Since the seed was stored, and the steps were always the same, the game map was constant, just as if it was saved as part of the program. But because you couldn’t see the seed number, and the steps were a little tricky, you didn’t know what was on the other side of the map until you went there, even though it was all predetermined.
(In fact, the designers had originally intended to have 281474976710656 galaxies, which is 2⁴⁸ : 2 raised to the power of 48 — that is, 2 multiplied by itself 48 times. But the publishers thought that sounded rather silly. Which is a shame, because “Explore a universe big enough that visiting a different planet every second would let you play for about the same length of time as complex cellular life has existed before you started to repeat yourself” sounds like an amazing marketing campaign.)
But What’s It All About?
The squirrel ‘remembers’ where it put its nuts by working out where it would put them if it was hiding them now. Elite ‘remembers’ the layout of an improbable number of planets by working them out from a simple starting value when it needs them. So that’s why a squirrel is like a 1984 computer game. And we decided we could cut through the tedium of actually singing the whole ‘Hokey Cokey’ by telling people how to re-create it from a small template and a number of instructions. Has anyone noticed this before? Or maybe studied in detail? You bet they have.
In mathematics, there is a concept called the Kolmogorov Complexity of a message. This is the length of the shortest computer program which will generate that message.
Kolmogorov Complexity: The length of the shortest
computer program which will generate a message
To stop us cheating by including the message as data along with the very small program ‘print this data’, the length of a computer program should include any special data that it needs to work — essentially, it’s the disk space that the program would take up if you had it on your computer. The programmers of Elite put a lot of work in to get the size of their computer program down as small as they could while still generating the large number of planets that made for an interesting game. The squirrel uses a small amount of ‘mental hardware’ to hide and find his nuts. But of course the techniques they use can lead to some results that don’t look ‘simple’.
So the concept of ‘simple’ isn’t so simple. I’ll expand on this… another time.
This article is — hopefully — part one of a series I’m writing. If everything comes together, it should take shape over the next few months. If not — well, I hope you’ve had fun reading this!