OS X Games from the Ground Up: Hexapawn – BASIC programme

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

In the previous post I explained how the Hexapawn game works. In this post I’ll dissect the original BASIC programme we’ll be converting to C.

Here’s the full listing:

The first thing you’ll probably note about this is that, at first sight, it’s almost incomprehensible. This is one of the difficulties with any code that is poorly commented.  So let’s take it piece by piece.

These first three lines are straightforward and will be familiar to you. They simply display the title and attribution as shown below.

Hexapawn title

These next few lines are just comments with further information about the programme.

Here the programmer creates some arrays and other variables that will be used during the programme:

  • B is a two-dimensional array that holds the 19 possible board configurations we looked at in the previous post
  • M holds the moves that are available for each of those configurations
  • S holds the current state of the board
  • P$ is a three character string that holds the characters used to represent the white and black pawns and an empty space on the board
  • W holds the number of wins for the computer player
  • L holds the number of losses for the computer player.

The board (as stored in S and 19 times in B) is represented by an array of 9 values with elements 1 to 3 representing the top row of the board from left to right, 4 to 6 representing the middle row and 7 to 9 representing the bottom row.

Position 1 Position 2 Position 3
Position 4 Position 5 Position 6
Position 7 Position 8 Position 9

The content of the board at each position is represented by one of three numbers:

  • -1: black pawn
  • 0: empty square
  • 1: white pawn

Each move is stored as a two digit number, with the first digit indicating the from position and the second digit indicating the to position. So for the configuration shown below, a code of 25, for example, represents a black pawn advancing from position 2 to position 5. A code of 24 would indicate the black pawn at position 2 capturing the white pawn at position 4.

Position 1
Value -1
Position 2
Value -1
Position 3
Value -1
Position 4
Value 1
Position 5
Value 0
Position 6
Value 0
Position 7
Value 0
Position 8
Value 1
Position 9
Value 1

Hexapawn example config

These three lines are something we’ve not seen in the programmes we’ve looked at so far. In BASIC you can define your own functions, which is what these lines are doing. It’s important not to confuse BASIC’s user-defined functions with C functions. BASIC’s functions simply enable you to construct an expression in which the term in parentheses is substituted by a value that is passed into the function when it is used in another expression. For example, the code:

Would substitute the value 6 wherever X appears in the expression in line 20, so the expression in line 20 would effectively evaluate as:

-3*(6=1)-(6=3)-4*(6=6)-6*(6=4)-7*(6=9)-9*(6=7)+FNS(6)

Note that one function can make use of the value generated by another function. I’m sure this looks like gibberish to you right now. Basically the two functions FNR and FNS are used to convert a position on the board to its equivalent in a mirror image version of the board where the line of symmetry is vertical. So positions 1, 4, and 7 would become positions 3, 6, and 9 and vice versa, while positions 2, 5, and 8 would remain unchanged. Remember from the discussion in the previous post that we need this because we only store half the possible board configurations and we get the other half by creating mirror images of the ones we have stored.

When you look at the expression above remember that BASIC also uses a single = as both an assignment and an equality operator, and it works out which is which from context. So here, an expression in brackets like (6=1) is not trying to assign the value 1 to the value 6, it is checking to see if 6 is equal to 1. Clearly it isn’t, so this part of the expression will generate false. The next thing you need to know is that this dialect of BASIC represents false as 0, but it represents true as -1.

So let’s work through this expression bit by bit. 6 clearly doesn’t equal 1 so in the first past of the expression, -3*(6=1), 6=1 is going to evaluate as false or 0, and -3*0 is 0, so we end up with:

0-(6=3)-4*(6=6)-6*(6=4)-7*(6=9)-9*(6=7)+FNS(6)

Now let’s do 0-(6=3). 6 doesn’t equal 3 either, so that also evaluates to 0 and 0-0 is 0, so we get:

0-4*(6=6)-6*(6=4)-7*(6=9)-9*(6=7)+FNS(6)

In the next part of the expression, 0-4*(6=6), 6 does equal 6, so that gives us true or -1, and 4*-1 equals -4, and 0 – -4 gives us +4 because subtracting a negative number is like adding a positive number. Now we have:

4-6*(6=4)-7*(6=9)-9*(6=7)+FNS(6)

Now let’s calculate 4-6*(6=4). 6 doesn’t equal 4 so we get 6*0, which is 0 and 4-0 is 4:

 4-7*(6=9)-9*(6=7)+FNS(6)

For 4-7*(6=9), 6 doesn’t equal 9 so we get 7*0, which is 0 and 4-0 is 4:

 4-9*(6=7)+FNS(6)

Again 6 doesn’t equal 7 so we get 9*0, which is 0, and 4-0 is 4:

 4+FNS(6)

So at this point we have to evaluate FNS. If we pass the value 6 in, it evaluates as:

-6*(6=2 OR 6=5 OR 6=8)

Clearly 6 doesn’t equal any of those values, so the parenthesised expression will evaluate as false or 0, and -6*0 is 0, which is what will be returned by this function, so back in FNR we get:

4+0

which evaluates as 4. You should now be able to see that FNS returns the board position if that position is 2, 5, or 8 and it returns 0 if not. And FNR returns the mirror image equivalent of each position. So in our example, we passed it position 6 and it returned 4 which is the mirror image position.

Now let’s look at FNM. This is used to extract the second digit from a two digit move code. For example, if the move code was 15, indicating a capture from the top left square to the middle square then FNM would evaluate as:

15-INT(15/10)*10

So if we evaluate the part in parentheses first that gives us:

15-INT(1.5)*10

As you already know, the INT function in BASIC returns an integer by truncating any fractional part of its argument, so that gives us:

15-1*10

Next we multiply 1*10 to give us:

15-10

And finally we perform the subtraction, to give us 5, which is the second digit of the move code.

We’ll see how these functions get used a little later.

This line simply populates the string P$ with the three characters representing a black pawn (X), an empty board position (.) and a white pawn (0). This will be used later when the board is displayed.

These two sections of code read the configuration data into B and the move data into M respectively. We’ve already covered the format of the configuration and move data above.

If you happen to be following along with the original book, please note that the original listing had a couple of errors in the movement data table, which I have corrected in this version.

These two sections of code should be familiar to you. The first section repeatedly asks the player if they want instructions until they enter an answer beginning “Y” or “N”. LEFT$ is a BASIC function that returns a new string with the leftmost n characters of the string passed as an argument, so A$=LEFT$(A$, 1) has the effect of removing all but the first character of the string in A$.

The second section of code simply displays the instructions and then returns to the line following the input routine.

Hexapawn instructions

The variables X and Y store the computer’s move. X holds the index of the current configuration and Y holds the index of the current move within that configuration.

Lines 111 to 113 set the board to its initial configuration, with the black pawns lined up along the top row (or rank, as it’s known in Chess) and the white pawns lined up along the bottom.

Although BASIC doesn’t have functions in the sense that C does, you can define parts of the programme as subroutines that can be run multiple times from different parts of the code. The GOSUB command is used to run the subroutine starting at the given line. So GOSUB 1000 will begin executing code at line 1000 and continues until it encounters a return statement, like the one on line 1080. At this point it returns control to the line immediately following the GOSUB.

The subroutine at line 1000 displays the board. It sets up two nested loops. The first loop, between lines 1010 and 1060, iterates the rows on the board, while the second loop, between 1020 and 1040, iterates the columns.

This gives a coordinate in the form of (I, J). To convert this to an element number in the board array S, necessitates subtracting 1 from I and then multiplying this by 3, to give 0 for the first row, 3 for the second and 6 for the third. It is then simply a case of adding the value of J to this to get the correct index into the array S. This is achieved by this part of the expression: S((I-1)*3+J), which will yield either -1, 0, or 1 depending on the content of that square. The programmer now needs to display the relevant character from P$. To do this he uses the BASIC function MID$. This takes three arguments, the string, the starting position to extract a substring from and the number of characters to extract. So the programmer adds 2 to the value from the array to give the right character position in P$ and then uses this extract 1 character, which is then printed.

Hexapawn initial board

This next section of code gets the player’s move and validates it. Note that the INPUT statement on line 121 wants two values. In BASIC you can request multiple values separated by commas, but when the arguments are entered by the user they must also be separated by commas.

The first check on line 122 is to see if the player has entered integers between 1 and 9. If they enter a non-integer or an integer outside that range then the programme will display an “ILLEGAL CO-ORDINATES” message and the player will be asked for their move again, as shown below:

Hexapawn illegal coordinates

Next there is a series of six checks to make sure the player hasn’t tried to enter an illegal move:

  • Line 150 checks that the player isn’t trying to move to a square containing another white pawn
  • Line 160 checks that, if the player is not moving directly forward, the square they are moving to is occupied by a black pawn
  • Line 170 checks that the player is not trying to move sideways to the right or backwards
  • Line 180 checks that, if the player is moving a pawn directly forwards, the square it is moving to is currently unoccupied
  • Line 185 checks that the player is not moving further forward than they are allowed to
  • Line 186 checks for a special case illegal move that is not covered by the other rules (moving directly from the bottom left of the board to the top right).

If any of these conditions are found to be true, the programme displays an illegal move message and asks the player for a new move:

Hexapawn illegal move

If you think all that code sounds a little convoluted, you’d be right. This is a good example of how you can quickly tie yourself in knots when programming, especially if you sit down to code without thinking things through first. Here the programmer focused on all the things you can’t do when moving in Hexapawn (of which there are many), when a moment’s thought would have shown him that it’s actually far better to focus on what the player can do, like this:

hexapawn illegal move flowchart

If you spend a moment studying this flowchart you can see that this encompasses all the legal and illegal moves with just four decisions rather than six. By not thinking this through, not only did the original programmer tie himself up in knots, he also failed to test for every eventuality. Look at this game in progress:

Hexapawn illegal move demo 1

I am going to attempt to take the black pawn that is immediately to the left of my white pawn in the centre of the board. This should be an illegal move, right?

Hexapawn illegal move demo 2

Oops! Well all of us have, or will, make mistakes like this from time to time – that’s why it’s so important to test, test and test some more.

These three lines of code will be executed if a legal move is entered. Line 190 sets the square being moved from to empty, while line 200 sets the square being moved to as occupied by a white pawn. If the move is a capture, the black pawn that was previously there will, of course, be obliterated by this simple assignment statement.

Line 205 now reprints the board to show the result of the move.

Hexapawn player move

This section of code checks if white has won. Line 210 checks for a win by reaching the far side of the board by checking to see if any of those squares contain a white piece. If this is the case, the code branches to the player win routine at line 820, which we’ll examine a little later.

If not, we drop through to lines 220 to 223 which check to see if white has won by capturing all the back pieces. This works by simply examining all the squares on the board and jumping out of the loop as soon as a black pawn is found. If the end of the loop is reach then there are no black pawns remaining in the game, so control once again passes to the win routine.

Lines 230 to 340 check to see if black has any legal moves. This works by examining each square of the board. Line 240 checks to see if the square contains a black pawn. If it doesn’t the next square is examined. If it does line 250 checks to see if that pawn can move  directly forward (because the square in front of it is empty). If this is the case, there is at least one legal move available so control jumps out of the loop and picks up execution from line 350 which is the code to determine the computer player’s  move. Again, we’ll examine this a little later. Note that because the game ends as soon as a black pawn reaches the far side of the board, we don’t have to be concerned about an out of bounds error here, because we should never encounter a pawn in the final row within this loop. This does mean, of course, that the loop could have been made a little bit more efficient by only checking squares 1 to 6. Incidentally the same is true for the loop at line 220.

Line 260 uses FNR to check if the pawn is in the centre column. If it is, line 320 checks to see if there are available captures in the right or left columns. If it isn’t, meaning its on one of the outside columns, it can only capture pawns in the centre column. Line 270 checks to see if it is on the first row or second row. and then line 280 or 300 is executed to check if there is a possible capture to the centre square or centre bottom square respectively.

Again, if we reach the end of this loop, that means no legal moves were found and white has won, so line 340 goes to the win routine.

If none of the win conditions for white is satisfied then the computer next searches for the current board configuration. The outer loop, between 350 and 510 iterates through the 19 configurations stored in the array B. You’ll recall that we also need to check mirror images of each of the configurations, so the nested loops from 360 to 400 are used to build a temporary mirrored copy of the currently indexed configuration in the array T. Line 380 simply copies the relevant element of B into T, but the order of each row is reversed.

The loop between 410 and 430 now checks to see if the configuration of the actual board matches the currently indexed configuration in B. If this loop ends we have a match, so line 440 sets the variable R to 0, indicating that we are using a non-mirrored configuration so the computer’s move does not have to be mirrored.

If line 420 finds a mismatch, then control is passed to the loop between 460 and 480, which checks for a match with the mirrored configuration in T. If the end of this loop is reached, indicating we have a match, then R is set to 1 on line 490, so the computer knows its move is to be mirrored.

If line 470 finds a mismatch, it passes control to line 510 and the next configuration is checked. Theoretically the code in lines 511 to 530 should never be executed, because a match with at least one of the configurations should have been found by the time the loop ends. But as we saw earlier, there is a fault in the illegal move detection, so it is currently possible for these lines to be executed.

Line 511 might look like it’s missing a statement, but it’s actually a comment, the REM at the beginning of REMEMBER causes the line to be treated as a REM statement. Note that some BASIC interpreters would require you to put a space between REM and EMBER or this line would cause a syntax error.

This section of code is executed when the correct configuration is found. First X is set to the number of the configuration (i.e. the loop index at the point the loop ended). The loop between 550 and 570 now checks to see if there is at least one available move for this configuration. It’s possible that, if you play enough games, all the available moves for a configuration have been eliminated because they all resulted in a lost game. If at least one valid move is found by line 560, then execution is passed to the code that selects a move at line 600. If the loop finishes without a move being found then the computer resigns (it knows it can’t win from this point) and control passes to the player win code at line 820.

Hexapawn resign

If at least one available move has been found, the computer must now select a move from those available. Each configuration has up to four possible moves, so line 600 selects one of the move slots at random. If a move slot is unused (or if the move that used to be there has been deleted) then it will contain 0. Line 601 checks for this and returns to line 600 to pick another move slot if the chosen slot is empty.

Line 610 checks whether the move should be mirrored, because a mirror configuration was found. If the move should be reversed, control is passed to the alternative move routine on line 630. If not, control continues with the normal move routine on line 620. Line 620 displays the move the computer is about to make. Note that the BASIC function STR$ converts a numeric argument to a string. The expression INT(M(X/Y)/10) extracts the first digit from the move code. The second digit is extracted using the FNM function we examined earlier.

Lines 622 and 623 Now make the move by setting the square being moved from as empty and the square being moved to as holding a black pawn. Once again, if the move is a capture, the white pawn that previously occupied the square will be overwritten by the black pawn.

Lines 630 to 633 achieve the same thing for a mirrored configuration. The only difference is that FNR is used to mirror the move (e.g. the move 14 would be changed to 36).

Finally line 1000 calls the subroutine to display the board.

Hexapawn computer move

Now the programme checks for the three ways the computer could win:

  • By getting a pawn to the far side of the board (line 641)
  • By capturing all the white pawns (lines 650 to 680)
  • By blocking all legal moves for white (lines 690 to 810) – in this case a message is displayed on line 800 to prefix the computer’s “I WIN” message

Heaxapawn you can't move

These are functionally similar to the routines to check for a player win (between lines 210 and 340), which were discussed earlier.

Lines 820 to 840 are executed if the player wins a game. Line 830 deletes the last move the computer made that resulted in a lost game. This ensures that move will never be played from that configuration again. Line 840 increments the number of computer losses.

Hexapawn you win

If the computer has won, lines 870 and 880 are executed to display the “I WIN” message and increment the number of computer wins.

In both cases, lines 851 to 860 are then executed to display the number of games won by each player and then return to the code at line 100 that sets up a new game.

Hexapawn computer win

Note that the programmer has provided no way of exiting the game, other than hitting CTRL + C to terminate the programme. This is one of several improvements we will make in our version. The other things we’ll change are:

  • Fixing the error with the illegal move detection code
  • Displaying a better looking board using ASCII graphics
  • Implementing a menu system (which will include an exit function)
  • Providing save and load functionality for the configuration database
  • Creating and maintaining a database of played games, and providing a replay function for these

We’ll get started on this in the next post, in the meantime, here’s a flowchart showing the current functionality of the game:

hexapawn flow chart

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

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

Leave a reply