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.
I know it’s been a long time since you posted this but I just came across it after purchasing an EC-4001, which is the same calculator rebranded for Radio Shack.
The program plays by always trying to leave you with 4n+1 matches. You can always win by starting off with 4n+1 matches and taking 3 every turn. A human opponent might notice what you are doing and vary the number of matches he picks (you can still win but have to change the number of matches you take accordingly), but the program will take 1 match every time there are 4n+1 remaining.
The code is confusing because it uses “convenience functions”, which are invoked when an operator (+, -, x, /) or the equals sign follows an operator. The loop that subtracts 4 does “- – -”, and when the loop ends the code does “- – +”. The “- -” convenience function changes the sign of the current result. This is useful because the conditional jump operator is “go if negative” (gin), but the code needs to loop if the value is positive. “- – gin – # 4″ will jump if the initial value was positive, and the 3rd – changes the sign back to its original state before subtracting 4. “- – gin + # 5″ will not jump if the initial value was negative or zero, then the + changes the sign back and adds 5.
I found it easier to first look at the code with the section in the parentheses removed: STO – ( ) – STOP = STOP = = = =
It stores your initial # then subtracts what it calculates in the parentheses then “hits” the minus key (which displays the result) and stops. You enter the number of matchsticks you want to take and hit RUN, which resumes the program at the equals sign, then it stops again. Since the minus key had been hit before ypu entered your number, your number is subtracted from the total and the equals sign displays the new total. When you hit RUN, the code resumes at the first of 4 minus signs, which do nothing but advance the program to the end of the program at line 35, where it rolls over to the beginning (they could have used a GOTO 00, which is also 4 instructions). At this point, it’s like you just started a new game with the new total.
The code in the parentheses RCLs the number of matchsticks and adds 3. Then it subtracts 4 in a loop until the result is zero or negative. If negative, 4 is added; if zero then 1 is added. If the number of matches was not a multiple of 4 plus 1, this will be the number of matches to take to make the new total a multiple of 4 plus 1. If the number of matches was a multiple of 4 plus 1 then the code just takes 1; it needs to take 0 or 4 to get back to a multiple of 4 plus 1, but those choices are illegal.
I bought the calculator to preserve it through emulation. The chip inside is a National Semiconductor MM5799, a general purpose microcomputer with 1536 bytes of ROM and 48 bytes of RAM (not megabytes or even kilobytes!) It was also used in a couple of educational calculators and some Mattel handheld LED games (basketball, hockey and soccer) which are already emulated. I will use a blowtorch to remove the plastic package from the chip revealing the silicon die. I’ll take pictures of it, then use acid to remove the metal and take more pictures. I’ll transcribe the bits that make up the calculator’s “brains” and send those to the MAME team who will add it to the list of devices that are emulated.
Hi Sean – that’s amazing! I can’t pretend I follow all of it, but sounds like a weekend project for me to figure it all out. I’d love to find out more about the NatSemi chip at the heart of it. I assume the ROM was custom-flashed for each device?
best wishes and good luck with the emulation project.
Giles
Every different calculator or game has its own unique ROM that tells the chip what to do. Usually an ID code is printed on the chip package and is also marked on the die. All of the early microcontrollers use mask ROM – the ROM was permanently fixed when the chip was made. So no chance for updates if bugs were found!
In fact, Hap on the MAME team informed me that there are 2 versions of the Sinclair Cambridge Programmable MM5799; ID codes EHY and NBP. The one I bought is marked NBP; I assume since N comes after E that it has the later ROM, but we won’t know the differences unless the EHY also gets dumped.
Here are some giant pictures of the chip with the top metal layer and with it removed, some slightly smaller pictures of just the ROM array on the chip, a visual transcription of the bits from the ROM array, and those bits rearranged into how the CPU processes them. There’s also a text file describing how the chip is wired up:
http://www.seanriddle.com/sinclaircambridgeprogrammable/