OS X Games from the Ground Up: Hexapawn

In this next part of the series we’ll be sticking to the C language for one more game and building on the C fundamentals developed during construction of the first two games.

You can see an index of all the posts in this series: go to index.

If you are joining the series at this point, you should have some prior experience with C. In particular you should understand:

  • C variables and data types (including pointers)
  • Decision structures with if… then… else… and switch
  • Loops using while, do …. while and for
  • C functions (including passing arguments to a function and returning values from a function)
  • The main function
  • How to construct simple command line programmes

If you’re not comfortable with those topics then I recommend you have a look at the index and pick an earlier episode to begin with.

As with earlier parts of this series, we’ll be converting a game originally written in BASIC from the classic book Basic Computer Games.

The Hexapawn programme is a little more challenging than the two programmes we 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 we will be developing some form of artificial intelligence for the first time in this series. Furthermore, while with the previous two games we’ve been content to simply reproduce the functionality of the original version, for this part of the series we 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.

Hexapawn initial position

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.

Hexapawn forward 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.

Hexapawn capture

There are three ways to win a game of Hexapawn. Let’s continue this game to see the first of them.

Hexapawn win by reaching opp side

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:

Hexapawn no moves 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:

Hexapawn win by capture

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, our 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:

Hexapawn configurations

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.

Hexapawn AI explanation 1

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.

Hexapawn matching configuration

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 choses one at random. In this case it choses to advance its middle pawn.

Hexapawn AI explanation 2

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:

Hexapawn revised configuration

Now that losing move will never 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 we’ll look at how the BASIC version works.

This entry was posted in BASIC, Games, Programming Tutorials and tagged , , , , , . Bookmark the permalink.

2 Responses to "OS X Games from the Ground Up: Hexapawn"

Leave a reply