Nim and the Sinclair Cambridge Programmable calculator

The game of Nim comes in many forms, but the idea is same: players take turns to remove objects from a pile and the player left taking the last object loses. Or wins. You can play it so you win if you take the last piece, but I think it’s usually last piece loses, which apparently makes it a misère game. (Apparently they play Nim in Last Year at Marienbad, so I probably ought to get round to watching that one day.)

I taught Nim in my first ever year 3 class, and I was reminded of it when students from Queen Mary University of London were showing the Dr Nim game at Science Museum Lates (thank you Alan O’Donohoe!). This is a plastic game with marbles about the size and colour of an etch-a-sketch that is designed to win at Nim. It’s basically an ingenious, plastic computer:

I was convinced that Nim was one of the first computer games I ever played, probably on my brother’s Kim-1. But I can’t find anything about a Kim Nim so I now think the first version I really played was on the Sinclair Cambridge Scientific Programmable Calculator which came out in 1977. This was quite an amazing machine. The same elder brother had an eyewateringly-expensive HP programmable calculator that stored programs on magnetic strips. But the Sinclair was a machine cheap enough for me, a schoolboy, to own.

I think it’s fair to say I never used any from volumes 2, 3 or 4 such as ‘Inverse Hyperbolic Functions’ (volume 2), ‘Doppler effect (non-relativistic)’ (volume 3) or ‘Operating point of transistor in base-potential divider and emitter resistor bias’ (volume 4). Playing Nim and spelling rude words was probably, age 12, more my thing.

In the table below is the program for the ‘matchstick game’ from volume 1 (‘General/Finance/Statistics’) of the four volume boxed set of programs that came with the Sinclair Cambridge Programmable. It’s a simple version of Nim where you have 1 pile, you type in how many matchsticks you want to start with and you and the calculator take it in turns to take 1, 2 or 3 sticks from the pile. Whoever is left with the last stick is the loser.

I cannot decypher how this code works, and would love some help, because eventually got it to stay on long enough to enter and run the program for the matchstick game. And work it does! I cannot beat it, and it must be using a strategy to divide the pile into groups of 4 to ensure the human player is always left with 4 sticks in their penultimate move (see Dr Nim video above for more on this strategy for winning 1-pile Nim). It seems like an ingenious algorithm that uses less than 36 instructions to play this, and with such a ridiculously limited instruction set.

Here’s what I’ve worked out about what it does, although apart from possibly repeatedly subtracting 4 I cannot figure out precisely how it works. ‘sto’ means store a number in memory. ‘rcl’ means recall a number from memory. You can ignore the hash/pound sign # as that just means the next digit is a number not an instruction and you can also ignore ▼ which tells the calculator that the next instruction needs a shift, it’s a ‘lower case’ instruction found underneath that key’s label. The pleasing command ‘gin’ is nothing to do with drink, but means ‘go if negative’, which I think is the only conditional branching instruction the Cambridge Programmable has. I assume the following two digits are the address the program branches to if the number being considered is indeed negative.

If you can draw me a flowchart or write pseudocode for precisely how this program works (and who was the author!?) I shall be hugely grateful…

instruction step sto 00 - 01 ( 02 rcl 03 + 04 # 05 3 06 - 07 # 08 4 09 - 10 - 11 ▼ 12 gin 13 0 14 7 15 + 16 ▼ 17 gin 18 2 19 4 20 # 21 5 22 - 23 # 24 4 25 = 26 ) 27 - 28 stop 29 = 30 stop 31 = 32 = 33 = 35 = 36

To play the game, you enter the program and enter the number of sticks you you want to play with then press RUN. The machine plays. Then you enter 1, 2 or 3 depending on how many sticks you are taking and press RUN again. Then press RUN to get the machine to play, and repeat until you have 1 stick left, you loser…

I seem to have lost the actual manual for the calculator, although it’s not massively helpful it does explain a few things like brackets.
You can find out more about winning Nim strategies here and here.