Last week my son, Bertie, and I had a go at making a Hexapawn machine. We were inspired by listening to Geoff Engelstein talk about the Hexapawn in his GameTek segment on The Dice Tower podcast. The Hexapawn demonstrates machine learning in a very simple way. All you need is 24 matchboxes, 3 white pawns, 3 black pawns, some coloured cubes or counters and a colour printer. Hexapawn is played on a 3 x 3 grid. Three white pawns stand across one edge and three black pawns along the opposite edge. The pawns move the same way that pawns in a chess game move. They can only move forwards, unless they are attacking, in which case they move diagonally forwards and remove the piece in that position from the board. The winner is the first player to get one piece to the opposite side of the board or to wipe out all the opponent’s pieces. The human player always plays white and always goes first.
The black player is the machine. The machine is comprised of the 24 matchboxes, all labelled in a different way. The labels indicate the possible positions of the pieces at the start of the turn. As the game is guaranteed to end within 6 turns, only boxes for turns 2, 4 and 6 are required. Each label indicates different possible moves that the machine can make with different coloured arrows. A counter of the same colour is added to the matchbox. So if there is a matchbox with four different arrows on, four different counters will be placed inside.
So, the player makes the opening move and then looks for the matchbox that corresponds to the current board. The player shakes the matchbox and pulls out one of the counters. The machine then takes the move indicated by the arrow of the same colour. The player moves the machine’s black pawn accordingly. When the player has taken a second turn, she again looks for the matchbox that corresponds to the current board layout, pulls out a counter and makes the machine’s chosen move. This continues until the player or the machine wins the game.
But here’s the interesting bit… Each time the machine loses a game, you remove the counter that corresponds to the last move that the machine took. If there is only one counter left in this box, remove the counter that decided its previous move. This means that the machine will never again take the same losing moves. When the machine wins, no changes are made to the boxes, but each time the machine loses another counter is removed. Very quickly the machine becomes unbeatable.
You can do the whole project in the space of about 40 minutes, including making the Hexapawn machine and playing enough times for the machine to always win. It’s an elegant demonstration of machine learning with a very simple game. Download the board and all the Hexapawn labels here.