In this next volume of the series I’ll be building on the C fundamentals developed during construction of the first two games and moving on from plain text command-line games to a game that uses a text-based user interface.
You can see an index of all the posts in this series: go to index.
As with earlier parts of this series, I’ll be converting a game originally written in BASIC from the classic book Basic Computer Games.
The Hexapawn program is a little more challenging than the two programs I looked at previously: Buzzword and Acey Ducey. To begin with, it’s a two player game – and the second player is played by the computer. That means I will be developing some form of artificial intelligence for the first time in this series. Furthermore, while with the previous two games I’ve been largely content to simply reproduce the functionality of the original version, for this part of the series I will be enhancing the original. I’ll explain the planned enhancements in the next post.
First though, a little history. Hexapawn is a game developed by the mathematician Martin Gardner in a article he wrote for the March 1962 edition of Scientific American. This was reprinted in his book, The Unexpected Hanging and Other Mathematical Diversions. If you can get hold of a copy of the article or book, it’s a worthwhile read, as it explains how you can build a “matchbox computer” (built using a set of match boxes and some coloured beads), which will not only play the game but improve upon its play over time.
The game is played on a 3 x 3 board, using Chess pieces – three white pawns and three black pawns – which are lined up on opposite sides of the board.
As in Chess, one player plays white and the other black. They take turns making moves and white always moves first. A pawn may advance one square forward (i.e. towards the opposite side of the board to its starting position), provided the square in front of it is empty. For the Chess players among you, note that in Hexapawn, pawns may not advance two squares on their first move.
If one of the opposing player’s pawns is diagonally opposite one of your pawns, you can optionally move diagonally to capture that pawn. So from the position above, the white pawn in the centre square could be captured by either of the black pawns on the left or right column (known as a file in Chess). Captured pieces are removed from the board and take no further part in the game.
There are three ways to win a game of Hexapawn. Let’s continue this game to see the first of them.
Here white makes a mistake by not capturing the black pawn at the centre of the board, which allows the black pawn to advance to the white’s side of the board, thus winning the game. So the first way to win is by advancing one of your pawns to the opposite side of the board.
Let’s look at a second game, showing the second way to win:
White wins this game because it is black’s turn to move next, but there are no legal moves black can make. So the second way to win is to force your opponent into a position where they have no legal moves.
And finally, here’s the third way to win:
In this game, black manages to capture all the white pieces, thereby winning the game. So the third and final way of winning is to capture all your opponent’s pieces.
So you can see this is a very simple game and the rules can be learnt quite quickly. What makes this game interesting is that the matchbox computer (or in this case, a simulation of it) knows how to make a legal move from each possible position of the board, but it begins with no strategy. When you first play against it, it will make a lot of poor moves. But it learns from its mistakes, so the more games you play against it, the better it gets. Eventually it gets so good that it’s quite hard to beat.
So how does this work? Well the computer, which always plays black, can recognise 19 possible configurations of the board when it is its turn to play, and between 1 and 4 legal moves it can make for each of those positions. These are all shown here:
If you study these for a moment you might spot that there appear to be some valid configurations missing. In fact there are 37 possible configurations of the board when it is black’s turn to play. All of the configurations shown above (with the exception of the second one, which is the only symmetrical configuration), have mirror images. These are not included in the matchbox computer, since it is an easy matter to mirror each configuration horizontally to take care of those additional cases.
So how does this the matchbox computer use this information to play and to improve its game? Well let’s consider the second game we looked at earlier – the one which white won – and see how it works.
So at the start of the game, it is white’s turn to move and white chooses to move the leftmost pawn forward. The computer now searches its board configurations to find one that matches.
There are three possible legal moves from this position. The computer has no conception at the moment about which of these moves, if any, is preferable, so it simply chooses one at random. In this case it chooses to advance its middle pawn.
White responds by advancing its rightmost pawn, thus blocking black and winning the game. Whenever black loses a game, it removes the losing move from its store of configurations, so the configuration now looks like this:
Now that losing move will no longer be played when that configuration arises in future games. And each time the computer plays and loses, the database of configurations is refined by removing one more losing move.
So now that you understand the principles of the game, in the next post I’ll look at how the BASIC version works.
Be First to Comment