I just inherited a load of books on programming the 6502 processor in assembly language (and a Kim-1 computer, more on that later!). Among them was an intriguing 1980 book by Rodnay Zaks called 6502 Games. Zaks wrote what, for many, is the default text book on programming the 6502, but this book is a bit more playful.
The games in this book are based around a hardware accessory for the Sym-1 computer. The Sym-1 was very much like a Kim-1, a 6502-based development board. (Intriguingly I read somewhere that it could use an oscilloscope as a VDU, I’d love to know more about that!) The Sym-1 Games Board consists of a bunch of LEDs and a number keypad, and even though I don’t have one of those, nor a Sym-1, the book itself is interesting.
I just noticed that the Games Board seems to be made by Sybex, who published the games book. Maybe this book was just a ruse to sell hardware. Anyway…
The most complex game is in the final chapter: ‘tic tac toe’, or noughts and crosses as we call it in the UK. Artificial intelligence long pre-dates this book, of course, but it’s interesting to see the term used here to describe a computer playing a game. It got me thinking about two approaches to solving this problem, which he discusses:
1) A heuristic approach, where the computer learns from its mistakes. This is, I think, how LLMs work, by training on huge amounts of data. It’s also how the matchbox-based noughts and crosses engine, MENACE, works. Often these systems come up with models that the creators of the tools don’t themselves fully understand. This approach takes time and a lot of memory, something lacking on a 1980 home computer. (By the way, there’s a great video of Matt Parker demonstrating MENACE to Professor Hannah Fry in the 2019 Ri Christmas Lectures).
2) A human-programmed algorithmic approach. This requires much more thinking by a human programmer, who needs a deep knowledge, in this case, of how to play the game and all its possible strategies and outcomes. The human applies the usual skills of computational thinking to solve the problem of how to get a machine to play a game that normally humans play.
So which approach is best? Zaks’ hand was forced down the second path due to lack of computer memory, but it strikes me that – if the problem is simple enough – it’s best to take the human-programmed route. The designer learns more. The algorithm is not opaque, you can challenge it if you think it’s biased. It’s open to inspection, improvement in a way LLMs, for example, seem not to be.
I don’t think I’ve ever coded a noughts and crosses game, so inspired by Rodnay Zaks’ very thorough discussion of approaches to creating algorithms for the game, I thought I’d have a go at writing one in Python.
Broadly speaking, he suggests assigning a numerical value to each potential square depending on the threat from the human opponent and the machine’s chances of winning. Clever.
I know that what I’m doing here below is not original, it’s purely an exercise for relaxation in creating some simple programs to play a game, inspired by reading a chapter in a very old computer book.
Simplest version
I started by writing a version for two human players, just so I could set up a user interface and handle the board, detecting wins and draws. The code is here.
It just uses a list to store the board, with 9 elements. A dash is used to show an empty square, capital O and X for each player’s marks. It scans each row, column and diagonal to counts Os and Xs, and if there are 3 it knows someone has won. It also counts free squares, so if no-one has won and every square is filled, it must be a draw. You make your move by typing in the number of the square:
012 345 678
Shooting fish in a barrel
As a stepping-stone to a clever machine that can beat me, I created a laughably simple version. In this one, the human plays against the machine which always just picks the first available square. As the human always goes first, it’s incredibly easy to beat.
I have created you and now you will destroy me
Then I tried to implement something much cleverer, and closer to Zaks’ algorithm. I don’t doubt there are much more elegant and compact ways of doing this, but I wanted to code something a child (and I) could understand.
Zaks’ algorithm is impressively sophisticated, especially for a small 6502 assembly language program. It incorporates randomness and the machine varies its skill level depending on how well it’s doing, which makes for a much more entertaining opponent. I decided to do something much simpler.
This clever version has a new list called ‘move_weight’ which it uses to score how good a square might be. It scans rows, columns and diagonals. Squares already played get a score of 0, playable squares 1. An additional point is added if the human already has placed a O on that line. If the human has two Os on the line, it gets an extra 5 points, but if the computer has two Xs on the line and can win, it gets 6.
You can also choose who goes first, human or machine. The human always plays O, the machine X.
It’s a pretty boring opponent, always playing the first square suggested by the algorithm if there’s more than one choice, but it’s also pretty good. When I’m being dozy, it can beat me!
It also prints out the ‘move_weight’ list, so you can see how it made its choice and it also prints out when it thinks it’s in danger of losing or spots a winning square. A typical bit of game play might look like this:
0 1 2 - - - 3 4 5 - - - 6 7 8 - - - Player O go: 0 0 1 2 O - - 3 4 5 - - - 6 7 8 - - - Computer thinking... [0, 1, 2, 1, 1, 1, 2, 1, 2] 0 1 2 O - X 3 4 5 - - - 6 7 8 - - - Player O go: 4 0 1 2 O - X 3 4 5 - O - 6 7 8 - - - Computer thinking... danger at 8 [0, 1, 0, 1, 0, 2, 2, 2, 6] 0 1 2 O - X 3 4 5 - O - 6 7 8 - - X Player O go: 6 0 1 2 O - X 3 4 5 - O - 6 7 8 O - X Computer thinking... danger at 3 winning move at 5 [0, 1, 0, 6, 0, 8, 0, 2, 0] 0 1 2 O - X 3 4 5 - O X 6 7 8 O - X Game over! Winner is X
micro:bit version
Using IDLE for the first time in ages made me miss the micro:bit Python Editor, so I made a version for the BBC micro:bit. It uses the serial console for entering moves and it even works in the simulator, as well as showing the board on the micro:bit’s LED display. Bright LEDs are the human’s Os, and dim LEDs are the computer’s Xs. I may see if I can create a version you can just play on the micro:bit itself with no computer attached, and maybe add a bit of randomness to make the computer a more interesting opponent. There’s also clearly scope to use functions to shorten some repetitive bits of code.
Self-contained micro:bit version
I also made a self-contained version that you can play just using a micro:bit V2, with no serial console or computer needed.
It works best with a headphones or speaker attached so you can clearly hear the speech instructions and who wins.
This version only works on a micro:bit V2 with built-in speaker which has more memory.
Press A to go first, B for micro:bit to go first.
Press B to step through possible play squares which blink.
Press A to choose a square to play.
Press reset button on back of the micro:bit to play a new game.
In conclusion
All in all, a nice, relaxing coding activity prompted by a 1980 book on programming the 6502!