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 program I’ll be converting to C.
Here’s the full listing:
1 PRINT TAB(32);"HEXAPAWN" 2 PRINT TAB(15);"CREATIVE COMPUTING MORRISTOWN, NEW JERSEY" 3 PRINT:PRINT:PRINT 4 REM HEXAPAWN: INTERPRETATION OF HEXAPAWN GAME AS PRESENTED IN 5 REM MARTIN GARDNER'S "THE UNEXPECTED HANGING AND OTHER MATHEMATIC- 6 REM AL DIVERSIONS", CHAPTER EIGHT: A MATCHBOX GAME-LEARNING MACHINE 7 REM ORIGINAL VERSION FOR H-P TIMESHARE SYSTEM BY R.A. KAAPKE 5/5/76 8 REM INSTRUCTIONS BY JEFF DALTON 9 REM CONVERSION TO MITS BASIC BY STEVE NORTH 10 DIM B(19,9),M(19,4),S(9),P$(3) 15 W=0: L=0 20 DEF FNR(X)=-3*(X=1)-(X=3)-4*(X=6)-6*(X=4)-7*(X=9)-9*(X=7)+FNS(X) 25 DEF FNS(X)=-X*(X=2 OR X=5 OR X=8) 30 DEF FNM(Y)=Y-INT(Y/10)*10 35 P$="X.O" 40 FOR I=1 TO 19: FOR J=1 TO 9: READ B(I,J): NEXT J: NEXT I 45 FOR I=1 TO 19: FOR J=1 TO 4: READ M(I,J): NEXT J: NEXT I 50 PRINT "INSTRUCTIONS (Y-N)"; 60 INPUT A$ 70 A$=LEFT$(A$,1) 80 IF A$="Y" THEN 2000 90 IF A$<>"N" THEN 50 100 X=0: Y=0 111 S(4)=0: S(5)=0: S(6)=0 112 S(1)=-1: S(2)=-1: S(3)=-1 113 S(7)=1: S(8)=1: S(9)=1 115 GOSUB 1000 120 PRINT "YOUR MOVE"; 121 INPUT M1,M2 122 IF M1=INT(M1)AND M2=INT(M2)AND M1>0 AND M1<10 AND M2>0 AND M2<10 THEN 130 123 PRINT "ILLEGAL CO-ORDINATES." 124 GOTO 120 130 IF S(M1)=1 THEN 150 140 PRINT "ILLEGAL MOVE.": GOTO 120 150 IF S(M2)=1 THEN 140 160 IF M2-M1<>-3 AND S(M2)<>-1 THEN 140 170 IF M2>M1 THEN 140 180 IF M2-M1=-3 AND (S(M2)<>0) THEN 140 185 IF M2-M1<-4 THEN 140 186 IF M1=7 AND M2=3 THEN 140 190 S(M1)=0 200 S(M2)=1 205 GOSUB 1000 210 IF S(1)=1 OR S(2)=1 OR S(3)=1 THEN 820 220 FOR I=1 TO 9 221 IF S(I)=-1 THEN 230 222 NEXT I 223 GOTO 820 230 FOR I=1 TO 9 240 IF S(I)<>-1 THEN 330 250 IF S(I+3)=0 THEN 350 260 IF FNR(I)=I THEN 320 270 IF I>3 THEN 300 280 IF S(5)=1 THEN 350 290 GOTO 330 300 IF S(8)=1 THEN 350 310 GOTO 330 320 IF S(I+2)=1 OR S(I+4)=1 THEN 350 330 NEXT I 340 GOTO 820 350 FOR I=1 TO 19 360 FOR J=1 TO 3 370 FOR K=3 TO 1 STEP -1 380 T((J-1)*3+K)=B(I,(J-1)*3+4-K) 390 NEXT K 400 NEXT J 410 FOR J=1 TO 9 420 IF S(J)<>B(I,J) THEN 460 430 NEXT J 440 R=0 450 GOTO 540 460 FOR J=1 TO 9 470 IF S(J)<>T(J) THEN 510 480 NEXT J 490 R=1 500 GOTO 540 510 NEXT I 511 REMEMBER THE TERMINATION OF THIS LOOP IS IMPOSSIBLE 512 PRINT "ILLEGAL BOARD PATTERN." 530 STOP 540 X=I 550 FOR I=1 TO 4 560 IF M(X,I)<>0 THEN 600 570 NEXT I 580 PRINT "I RESIGN." 590 GOTO 820 600 Y=INT(RND(1)*4+1) 601 IF M(X,Y)=0 THEN 600 610 IF R<>0 THEN 630 620 PRINT "I MOVE FROM ";STR$(INT(M(X,Y)/10));" TO ";STR$(FNM(M(X,Y))) 622 S(INT(M(X,Y)/10))=0 623 S(FNM(M(X,Y)))=-1 624 GOTO 640 630 PRINT "I MOVE FROM ";STR$(FNR(INT(M(X,Y)/10)));" TO "; 631 PRINT STR$(FNR(FNM(M(X,Y)))) 632 S(FNR(INT(M(X,Y)/10)))=0 633 S(FNR(FNM(M(X,Y))))=-1 640 GOSUB 1000 641 IF S(7)=-1 OR S(8)=-1 OR S(9)=-1 THEN 870 650 FOR I=1 TO 9 660 IF S(I)=1 THEN 690 670 NEXT I 680 GOTO 870 690 FOR I=1 TO 9 700 IF S(I)<>1 THEN 790 710 IF S(I-3)=0 THEN 120 720 IF FNR(I)=I THEN 780 730 IF I<7 THEN 760 740 IF S(5)=-1 THEN 120 750 GOTO 790 760 IF S(2)=-1 THEN 120 770 GOTO 790 780 IF S(I-2)=-1 OR S(I-4)=-1 THEN 120 790 NEXT I 800 PRINT "YOU CAN'T MOVE, SO "; 810 GOTO 870 820 PRINT "YOU WIN." 830 M(X,Y)=0 840 L=L+1 850 PRINT "I HAVE WON";W;"AND YOU";L;"OUT OF";L+W;"GAMES." 851 PRINT 860 GOTO 100 870 PRINT "I WIN." 880 W=W+1 890 GOTO 850 900 DATA -1,-1,-1,1,0,0,0,1,1,-1,-1,-1,0,1,0,1,0,1 905 DATA -1,0,-1,-1,1,0,0,0,1,0,-1,-1,1,-1,0,0,0,1 910 DATA -1,0,-1,1,1,0,0,1,0,-1,-1,0,1,0,1,0,0,1 915 DATA 0,-1,-1,0,-1,1,1,0,0,0,-1,-1,-1,1,1,1,0,0 920 DATA -1,0,-1,-1,0,1,0,1,0,0,-1,-1,0,1,0,0,0,1 925 DATA 0,-1,-1,0,1,0,1,0,0,-1,0,-1,1,0,0,0,0,1 930 DATA 0,0,-1,-1,-1,1,0,0,0,-1,0,0,1,1,1,0,0,0 935 DATA 0,-1,0,-1,1,1,0,0,0,-1,0,0,-1,-1,1,0,0,0 940 DATA 0,0,-1,-1,1,0,0,0,0,0,-1,0,1,-1,0,0,0,0 945 DATA -1,0,0,-1,1,0,0,0,0 950 DATA 24,25,36,0,14,15,35,36,15,35,36,47,36,58,59,0 955 DATA 15,35,36,0,24,25,26,0,26,57,58,0 960 DATA 26,35,0,0,47,48,0,0,35,36,0,0,35,36,0,0 965 DATA 36,0,0,0,47,58,0,0,15,0,0,0 970 DATA 26,47,0,0,47,58,0,0,35,36,47,0,24,58,0,0,15,47,0,0 1000 PRINT 1010 FOR I=1 TO 3 1020 FOR J=1 TO 3 1030 PRINT MID$(P$,S((I-1)*3+J)+2,1); 1040 NEXT J 1050 PRINT 1060 NEXT I 1070 PRINT 1080 RETURN 2000 PRINT: PRINT "THIS PROGRAM PLAYS THE GAME OF HEXAPAWN." 2010 PRINT "HEXAPAWN IS PLAYED WITH CHESS PAWNS ON A 3 BY 3 BOARD." 2020 PRINT "THE PAWNS ARE MOVED AS IN CHESS - ONE SPACE FORWARD TO" 2030 PRINT "AN EMPTY SPACE OR ONE SPACE FORWARD AND DIAGONALLY TO" 2040 PRINT "CAPTURE AN OPPOSING MAN. ON THE BOARD, YOUR PAWNS" 2050 PRINT "ARE 'O', THE COMPUTER'S PAWNS ARE 'X', AND EMPTY " 2060 PRINT "SQUARES ARE '.'. TO ENTER A MOVE, TYPE THE NUMBER OF" 2070 PRINT "THE SQUARE YOU ARE MOVING FROM, FOLLOWED BY THE NUMBER" 2080 PRINT "OF THE SQUARE YOU WILL MOVE TO. THE NUMBERS MUST BE" 2090 PRINT "SEPARATED BY A COMMA.": PRINT 2100 PRINT "THE COMPUTER STARTS A SERIES OF GAMES KNOWING ONLY WHEN" 2105 PRINT "THE GAME IS WON (A DRAW IS IMPOSSIBLE) AND HOW TO MOVE." 2110 PRINT "IT HAS NO STRATEGY AT FIRST AND JUST MOVES RANDOMLY." 2120 PRINT "HOWEVER, IT LEARNS FROM EACH GAME. THUS, WINNING BECOMES" 2130 PRINT "MORE AND MORE DIFFICULT. ALSO, TO HELP OFFSET YOUR" 2140 PRINT "INITIAL ADVANTAGE, YOU WILL NOT BE TOLD HOW TO WIN THE" 2150 PRINT "GAME BUT MUST LEARN THIS BY PLAYING." 2160 PRINT: PRINT "THE NUMBERING OF THE BOARD IS AS FOLLOWS:" 2170 PRINT TAB(10);"123": PRINT TAB(10);"456": PRINT TAB(10);"789" 2180 PRINT: PRINT "FOR EXAMPLE, TO MOVE YOUR RIGHTMOST PAWN FORWARD," 2190 PRINT "YOU WOULD TYPE 9,6 IN RESPONSE TO THE QUESTION" 2200 PRINT "'YOUR MOVE ?'. SINCE I'M A GOOD SPORT, YOU'LL ALWAYS" 2210 PRINT "GO FIRST.": PRINT 2220 GOTO 100 9999 END
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.
1 PRINT TAB(32);"HEXAPAWN" 2 PRINT TAB(15);"CREATIVE COMPUTING MORRISTOWN, NEW JERSEY" 3 PRINT:PRINT:PRINT
These first three lines are straightforward and will be familiar to you. They simply display the title and attribution as shown below.
4 REM HEXAPAWN: INTERPRETATION OF HEXAPAWN GAME AS PRESENTED IN 5 REM MARTIN GARDNER'S "THE UNEXPECTED HANGING AND OTHER MATHEMATIC- 6 REM AL DIVERSIONS", CHAPTER EIGHT: A MATCHBOX GAME-LEARNING MACHINE 7 REM ORIGINAL VERSION FOR H-P TIMESHARE SYSTEM BY R.A. KAAPKE 5/5/76 8 REM INSTRUCTIONS BY JEFF DALTON 9 REM CONVERSION TO MITS BASIC BY STEVE NORTH
These next few lines are just comments with further information about the program.
10 DIM B(19,9),M(19,4),S(9),P$(3) 15 W=0: L=0
Here the programmer creates some arrays and other variables that will be used during the program:
- B is a two-dimensional array that holds the 19 possible board configurations we looked at in the previous post
- M is a two-dimensional array that 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 with the values 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 -1 | Position 2 -1 | Position 3 -1 |
Position 4 1 | Position 5 0 | Position 6 0 |
Position 7 0 | Position 8 1 | Position 9 1 |
20 DEF FNR(X)=-3*(X=1)-(X=3)-4*(X=6)-6*(X=4)-7*(X=9)-9*(X=7)+FNS(X) 25 DEF FNS(X)=-X*(X=2 OR X=5 OR X=8) 30 DEF FNM(Y)=Y-INT(Y/10)*10
These three lines are something we’ve not seen in the programs 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:
A = FNR(6)
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), the 6=1 part in parentheses 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.
35 P$="X.O"
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.
40 FOR I=1 TO 19: FOR J=1 TO 9: READ B(I,J): NEXT J: NEXT I 45 FOR I=1 TO 19: FOR J=1 TO 4: READ M(I,J): NEXT J: NEXT I
900 DATA -1,-1,-1,1,0,0,0,1,1,-1,-1,-1,0,1,0,1,0,1 905 DATA -1,0,-1,-1,1,0,0,0,1,0,-1,-1,1,-1,0,0,0,1 910 DATA -1,0,-1,1,1,0,0,1,0,-1,-1,0,1,0,1,0,0,1 915 DATA 0,-1,-1,0,-1,1,1,0,0,0,-1,-1,-1,1,1,1,0,0 920 DATA -1,0,-1,-1,0,1,0,1,0,0,-1,-1,0,1,0,0,0,1 925 DATA 0,-1,-1,0,1,0,1,0,0,-1,0,-1,1,0,0,0,0,1 930 DATA 0,0,-1,-1,-1,1,0,0,0,-1,0,0,1,1,1,0,0,0 935 DATA 0,-1,0,-1,1,1,0,0,0,-1,0,0,-1,-1,1,0,0,0 940 DATA 0,0,-1,-1,1,0,0,0,0,0,-1,0,1,-1,0,0,0,0 945 DATA -1,0,0,-1,1,0,0,0,0 950 DATA 24,25,36,0,14,15,35,36,15,35,36,47,36,58,59,0 955 DATA 15,35,36,0,24,25,26,0,26,57,58,0 960 DATA 26,35,0,0,47,48,0,0,35,36,0,0,35,36,0,0 965 DATA 36,0,0,0,47,58,0,0,15,0,0,0 970 DATA 26,47,0,0,47,58,0,0,35,36,47,0,24,58,0,0,15,47,0,0
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.
50 PRINT "INSTRUCTIONS (Y-N)"; 60 INPUT A$ 70 A$=LEFT$(A$,1) 80 IF A$="Y" THEN 2000 90 IF A$<>"N" THEN 50
2000 PRINT: PRINT "THIS PROGRAM PLAYS THE GAME OF HEXAPAWN." 2010 PRINT "HEXAPAWN IS PLAYED WITH CHESS PAWNS ON A 3 BY 3 BOARD." 2020 PRINT "THE PAWNS ARE MOVED AS IN CHESS - ONE SPACE FORWARD TO" 2030 PRINT "AN EMPTY SPACE OR ONE SPACE FORWARD AND DIAGONALLY TO" 2040 PRINT "CAPTURE AN OPPOSING MAN. ON THE BOARD, YOUR PAWNS" 2050 PRINT "ARE 'O', THE COMPUTER'S PAWNS ARE 'X', AND EMPTY " 2060 PRINT "SQUARES ARE '.'. TO ENTER A MOVE, TYPE THE NUMBER OF" 2070 PRINT "THE SQUARE YOU ARE MOVING FROM, FOLLOWED BY THE NUMBER" 2080 PRINT "OF THE SQUARE YOU WILL MOVE TO. THE NUMBERS MUST BE" 2090 PRINT "SEPARATED BY A COMMA.": PRINT 2100 PRINT "THE COMPUTER STARTS A SERIES OF GAMES KNOWING ONLY WHEN" 2105 PRINT "THE GAME IS WON (A DRAW IS IMPOSSIBLE) AND HOW TO MOVE." 2110 PRINT "IT HAS NO STRATEGY AT FIRST AND JUST MOVES RANDOMLY." 2120 PRINT "HOWEVER, IT LEARNS FROM EACH GAME. THUS, WINNING BECOMES" 2130 PRINT "MORE AND MORE DIFFICULT. ALSO, TO HELP OFFSET YOUR" 2140 PRINT "INITIAL ADVANTAGE, YOU WILL NOT BE TOLD HOW TO WIN THE" 2150 PRINT "GAME BUT MUST LEARN THIS BY PLAYING." 2160 PRINT: PRINT "THE NUMBERING OF THE BOARD IS AS FOLLOWS:" 2170 PRINT TAB(10);"123": PRINT TAB(10);"456": PRINT TAB(10);"789" 2180 PRINT: PRINT "FOR EXAMPLE, TO MOVE YOUR RIGHTMOST PAWN FORWARD," 2190 PRINT "YOU WOULD TYPE 9,6 IN RESPONSE TO THE QUESTION" 2200 PRINT "'YOUR MOVE ?'. SINCE I'M A GOOD SPORT, YOU'LL ALWAYS" 2210 PRINT "GO FIRST.": PRINT 2220 GOTO 100 9999 END
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.
100 X=0: Y=0 111 S(4)=0: S(5)=0: S(6)=0 112 S(1)=-1: S(2)=-1: S(3)=-1 113 S(7)=1: S(8)=1: S(9)=1
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.
115 GOSUB 1000
1000 PRINT 1010 FOR I=1 TO 3 1020 FOR J=1 TO 3 1030 PRINT MID$(P$,S((I-1)*3+J)+2,1); 1040 NEXT J 1050 PRINT 1060 NEXT I 1070 PRINT 1080 RETURN
Although BASIC doesn’t have the ability for the programmer to create new functions in the sense that C does, you can define parts of the program 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 correct character position in P$ and then uses this to extract 1 character, which is then printed.
120 PRINT "YOUR MOVE"; 121 INPUT M1,M2 122 IF M1=INT(M1)AND M2=INT(M2)AND M1>0 AND M1<10 AND M2>0 AND M2<10 THEN 130 123 PRINT "ILLEGAL CO-ORDINATES." 124 GOTO 120 130 IF S(M1)=1 THEN 150 140 PRINT "ILLEGAL MOVE.": GOTO 120 150 IF S(M2)=1 THEN 140 160 IF M2-M1<>-3 AND S(M2)<>-1 THEN 140 170 IF M2>M1 THEN 140 180 IF M2-M1=-3 AND (S(M2)<>0) THEN 140 185 IF M2-M1<-4 THEN 140 186 IF M1=7 AND M2=3 THEN 140
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 program will display an “ILLEGAL CO-ORDINATES” message and the player will be asked for their move again, as shown below:
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 program displays an illegal move message and asks the player for a new 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:
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:
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?
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.
190 S(M1)=0 200 S(M2)=1 205 GOSUB 1000
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.
210 IF S(1)=1 OR S(2)=1 OR S(3)=1 THEN 820 220 FOR I=1 TO 9 221 IF S(I)=-1 THEN 230 222 NEXT I 223 GOTO 820 230 FOR I=1 TO 9 240 IF S(I)<>-1 THEN 330 250 IF S(I+3)=0 THEN 350 260 IF FNR(I)=I THEN 320 270 IF I>3 THEN 300 280 IF S(5)=1 THEN 350 290 GOTO 330 300 IF S(8)=1 THEN 350 310 GOTO 330 320 IF S(I+2)=1 OR S(I+4)=1 THEN 350 330 NEXT I 340 GOTO 820
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.
350 FOR I=1 TO 19 360 FOR J=1 TO 3 370 FOR K=3 TO 1 STEP -1 380 T((J-1)*3+K)=B(I,(J-1)*3+4-K) 390 NEXT K 400 NEXT J 410 FOR J=1 TO 9 420 IF S(J)<>B(I,J) THEN 460 430 NEXT J 440 R=0 450 GOTO 540 460 FOR J=1 TO 9 470 IF S(J)<>T(J) THEN 510 480 NEXT J 490 R=1 500 GOTO 540 510 NEXT I 511 REMEMBER THE TERMINATION OF THIS LOOP IS IMPOSSIBLE 512 PRINT "ILLEGAL BOARD PATTERN." 530 STOP
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.
540 X=I 550 FOR I=1 TO 4 560 IF M(X,I)<>0 THEN 600 570 NEXT I 580 PRINT "I RESIGN." 590 GOTO 820
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.
600 Y=INT(RND(1)*4+1) 601 IF M(X,Y)=0 THEN 600 610 IF R<>0 THEN 630 620 PRINT "I MOVE FROM ";STR$(INT(M(X,Y)/10));" TO ";STR$(FNM(M(X,Y))) 622 S(INT(M(X,Y)/10))=0 623 S(FNM(M(X,Y)))=-1 624 GOTO 640 630 PRINT "I MOVE FROM ";STR$(FNR(INT(M(X,Y)/10)));" TO "; 631 PRINT STR$(FNR(FNM(M(X,Y)))) 632 S(FNR(INT(M(X,Y)/10)))=0 633 S(FNR(FNM(M(X,Y))))=-1 640 GOSUB 1000
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.
641 IF S(7)=-1 OR S(8)=-1 OR S(9)=-1 THEN 870 650 FOR I=1 TO 9 660 IF S(I)=1 THEN 690 670 NEXT I 680 GOTO 870 690 FOR I=1 TO 9 700 IF S(I)<>1 THEN 790 710 IF S(I-3)=0 THEN 120 720 IF FNR(I)=I THEN 780 730 IF I<7 THEN 760 740 IF S(5)=-1 THEN 120 750 GOTO 790 760 IF S(2)=-1 THEN 120 770 GOTO 790 780 IF S(I-2)=-1 OR S(I-4)=-1 THEN 120 790 NEXT I 800 PRINT "YOU CAN'T MOVE, SO "; 810 GOTO 870
Now the program 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
These are functionally similar to the routines to check for a player win (between lines 210 and 340), which were discussed earlier.
820 PRINT "YOU WIN." 830 M(X,Y)=0 840 L=L+1 850 PRINT "I HAVE WON";W;"AND YOU";L;"OUT OF";L+W;"GAMES." 851 PRINT 860 GOTO 100 870 PRINT "I WIN." 880 W=W+1 890 GOTO 850
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.
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.
Note that the programmer has provided no way of exiting the game, other than hitting CTRL + C to terminate the program. This is one of several improvements I will make in my version. The other things I’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
I’ll get started on this in the next post. In the meantime, here’s a flowchart showing the current functionality of the game:
Be First to Comment