Programming your computer for board games There is one common thread which can hold together computer programs for such games as draughts, chess, reversi and even Nine Men's Morris. Tim Hartnell reveals the secret, and shows how it can be used to write an intelligent board game - from scratch. [This article, and the program developed in it, were first written for the ZX-81. Apparently, though, Mr. Hartnell thought, halfway through, that it would also work fine on that new (it was 1982), flashy Spectrum machine, as all references to the machine itself are to "your ZX Computer" rather than to "your ZX-81". He was right, too - the program works with only cosmetic changes on the Speccy. There were still two clues to its 81 origin left in the article: first, at one point it mentions an error report, which is in the ZX-81 style; and second, the program uses raster graphics for the board. I've replaced the latter with a blue background; everything else ported to the Spectrum without change. At the end of the article there was mention of a second part to the series in which this program was to be deve- loped further. I haven't been able to locate that next part, so I've left that bit out. The TZX that goes with this article holds, first, the completed program, and after that all the separate parts ("program 1" through "program 7" as described in the text.] Look first at diagram one. ___________________________________________________________ 1 2 3 4 5 6 7 8 ::: ::: ::: ::: 8 81 82:83 84:85 86:87 88: ::: ::: ::: ::: 7 71:72 73:74 75:76 77:78 ::: ::: ::: ::: 6 61 62:63 64:65 66:67 68: ::: ::: ::: ::: 5 51:52 53:54 55:56 57:58 ::: ::: ::: ::: 4 41 42:43 44:45 46:47 48: ::: ::: ::: ::: 3 31:32 33:34 35:36 37:38 ::: ::: ::: ::: 2 21 22:23 24:25 26:27 28: ::: ::: ::: ::: 1 11:12 13:14 15:16 17:18 Fig. 1 A chessboard game which a computer can use! All the squares are numbered up in ranks and files, so that the machine can be told exactly where to go! ___________________________________________________________ It shows a draughts or chess board, numbered to make it easy for a computer to handle. You can indicate any square on the board by referring to the number along the left hand side (such as 3), then the number along the top (such as 4). In this case, the lines numbered 3 (along the left hand side) and in the line numbered 4 (along the top) meet at the square numbered 34. If you wish to move a piece, you can do so by entering the number of the square you're moving from (such as 55), then the number you are moving to (such as 66), and the computer can understand exactly what you are doing. There is no need to change the numbers entered by the human player into another set of numbers in order that the computer can interpret them. That's the first 'secret'. The second is that the board numbered in this way has another great advantage over a board which is simply numbered from one to 64 in order. When you move in any direction, no matter where you are on the board, the difference between the squares is the same. I'll explain that somewhat cryptic statement. If you move one square up and to the right - like the move of a piece in draughts - you will move from, say, 24 to 35; or from 53 to 64; or from 71 to 82. But notice that no matter where you are on the board, the difference between your starting and ending squares is always 11. If you move dia- gonally up to the left, you'll move from, say, 26 to 35 (plus 9), or 66 to 75 (plus 9) or 22 to 31 (plus 9). This predictably makes it relatively simple to create a board which the computer can handle. Imagine the computer has a draughts piece on the square numbered 24. It could be programmed to check each square on the board, and every time it found one of its own pieces, could check if there was a human piece on the square num- bered that (i.e. 24 in out example) plus 11 (i.e. on 35); and it could check to see whether the square 11 beyond that (i.e. 46), was blank. If it found all these conditions were true, the computer could jump over square 35 into square 46, and capture the piece on 35. This, in essence, is how many computer board games - from draughts, through Reversi to chess - work, based on a simple 8 x 8 grid numbered this way. If you were writing chess on this board, you could spe- cify the moves of, for example, a knight, by knowing that it can always move to squares which are the following 'dis- tance' from its own squares: 21, 12, -8, -19, -21, -12, 19 or 8. Try it now, by placing a coin on square number 55, and move it as if it was a knight, working out the mathe- matical relationship between the starting square, and the square you're moving to. You should find the differences are the same as the numbers just listed. The Pieces Let's move on now to produce a board game, making use of the information we've discussed so far in this article. We are going to write CORNER CHECKERS, which will be a game much the same as draughts, except that it is played by starting in the corners of the board rather than the ends, there are no multiple jumps, and no kings. Any piece may move in any diagonal direction. Captures are as in draughts, by jumping over an opponent's piece into an empty square, always moving on the diagonal. First we need an array to hold the pieces. We'll start the program with a title, and a GOSUB to send action to line 9000. It is a good idea to assign the variables at the end of the program, as it makes the program run a little more quickly once the subroutine has been run (as it saves going right through the 'variables assignment' section every time the computer is going through the program, line by line, to find a GOTO or GOSUB address), and if you suddenly dis- cover, when you're writing a program, that more variables are needed, there will be no shortage of places to put them, which there could well be if the variables were assigned at the start of the program. The first 'mini-program' we'll enter, then, is program one. Next, we have to decide which squares on our board will be occupied by pieces, and what codes we will assign to those pieces. We'll be playing on the black squares in this game, starting the human pieces on 11, 13, 15, 22, 24, 31, 33, 42 and 51. The computer's pieces will be on squares 88, 86, 77, 68, 84, 75, 66, 57, 48. All other squares will be blank, and there will be - of course - other squares (such as those with numbers below 11 and above 88) which are off the board. We need to assign the values to the elements of the A array, which we do by running through a loop, from one to 100. Look at lines 9010, 9020, 9030 and 9040 in program two. These are acting as 'data statements', holding the numbers of the squares which will be assigned. H$ holds the start- ing human squares, C$ the starting computer squares, B$ the empty or 'black' squares (they are white on our numbering diagram, but are black here to give a good appearance when the game is underway), and E$ for squares which will be empty at the start of the game, but which will be used for playing on once the game gets underway. The first routine after the 'data' statements, lines 9050, 9060 and 9070, gives a value of 9 to all squares. This value will later serve as an indication of 'off the board'. The lines from 9080 to 9100 give the values which will be assigned to the other squares. The variables are given names to make it easy to keep track of them during the game - H for human's piece, C for the computer's, E for an empty square and B for a black one. Having run program two we need to check that it is work- ing correctly, by printing out the board and seeing it is correct. Note that the RETURN line is numbered 9500 to give as much room as needed for working. Enter your program up to the end of program two, and make sure it runs through without a hitch. The code 9/8990 shows it is working per- fectly. We will put the subroutine to print the board starting from line 8000. Add 30 GOSUB 8000, and then add program three, and run the whole program again. If all goes well, a complete board, set up for CORNER CHECKERS, should appear. Once it has (and it is very pleasing to see the board on the screen as it looks far stronger than the printout would suggest), add 8130 RETURN, and you're ready to add the next part of the game. Human Mover The human moves are the simplest to program. In essence, all we need in an input to take the square the human is moving from, an input for the square the human is moving to, and a means of turning the 'square from' blank (E) and the 'square to' into a human square (H). It is also useful to check that the human is not cheating, and there will have to be some mechanism for 'erasing' pieces which the computer has jumped over, but - for now - let's just arrange a simple, non-capture move. We'll start the PLAYER MOVE subroutine at line 7000. Add 40 GOSUB 7000, 50 GOSUB 8000, then enter program four. Run this, and enter your move as suggested as 3344 - that is, two numbers. If all is well, you'll see the "H" move from square 33 to square 44. The program will keep cycling in its present form. Try moving a few other pieces, even computer pieces. You'll see there is one check, line 7030, to make sure the move consists of four numbers. This program includes a line to remove a piece which has been captured. Look at our master numbered board. If the player moves from 42 to 64, and there is a computer piece on 53, the piece on 53 must be removed. Fifty-three is half of 42 plus 64, which gives us an easy way of finding out which piece to 'delete'. Try out some 'captures', making sure the captured piece vanishes, and the human score is incremented. Once you're happy with this, we start the biggest task of all, adding 'computer intelligence'. We'll start the computer's thinking subroutine at line 6000, so add 60 GOSUB 6000. Computer Mover Let's think about how the computer can be 'taught to play'. It must first scan the board, square by square, looking for any and all possible captures, so obviously it needs a loop of some kind. Look at lines 6010 to 6040 in program five. They go through the board, square by square, looking for a piece and once one is found, goes to like 6050 to find out what to do with that piece. The relationship between the squares on the board is plus eleven and minus eleven, plus nine and minus nine. The computer knows that if a human piece is on, say, a square eleven more than it is, and the square beyond that (its square number plus two times eleven) is empty, it can capture by jumping into the empty square. Add the lines between 6000 and 6200 (program five) and set up a capture or two for the computer, by moving some of your pieces into danger. It is fascinating (and quite pleasing) to see the computer finding possible cap- tures, and making them. Random moves are the next thing we should implement. We add the lines from 6200 onwards (program six) to achieve this. There are a number of things we need to do for 'intelligent' (i.e. non-sacrifice) moves: find a piece (line 6230) and then check around this piece (from line 6260) to make sure that we are not moving the piece into a potential capture situation. If, after 200 squares have been chosen in this way, no move can be found, the computer goes to 6500 and chooses 200 more squares, this time not checking to see if it is movign into danger. If no moves can be found, it goes to line 6500 and concedes defeat. Following through the possible moves will show you how this (somewhat complex) routine works. Finally, add the remaining lines for the main loop (pro- gram seven), which keeps the whole song and dance underway. The game continues until one of the players manages to cap- ture seven of the opponent's pieces. There is quite a bit you can do to improve this game, including speeding it up by ensuring that when it picks squares at random it does not select the same one more than once in any particular move. Also, the printing of the board (especially the numbers down the left hand side of the board) slows the game down. You may well be able to improve this. The final page of this article shows some stages in a typical game against this program. ___________________________________________________________ Computer > 0 0 < Human | Computer > 2 3 < Human | 12345678 | 12345678 8 : :C:C:C | 8 : : : : 7 : : :C: | 7 :H:C: : 6 :H:C:C:C | 6 :H: :C:C 5 : : :C: | 5 H:H:C: : 4 :H: : :C | 4 :H: :C:C 3 H:H: : : | 3 :H: : : 2 :H:H: : | 2 : : :H: 1 H:H:H: : | 1 : : : : 12345678 | 12345678 | Computer > 0 0 < Human | Computer > 5 4 < Human | 12345678 | 12345678 8 : :C:C:C | 8 : : : : 7 : : :C: | 7 C:H: : : 6 :H:C:C: | 6 : : :C:C 5 : : :C: | 5 H: : : : 4 :H:H:C:C | 4 : : :C:C 3 H: : : : | 3 : : : : 2 :H:H:H: | 2 : :H:H: 1 H:H: : : | 1 : : : : 12345678 | 12345678 | Computer > 1 0 < Human | Computer > 6 4 < Human | 12345678 | 12345678 8 : :C:C: | 8 : :C: : 7 : : :C: | 7 : : : : 6 :H:C:C: | 6 : : : :C 5 H: : :C: | 5 H: :C: : 4 :H:C:C:C | 4 : : :C:C 3 : : : : | 3 :H: : : 2 :H:H:H: | 2 : : :H: 1 H:H: : : | 1 : : : : 12345678 | 12345678 | Computer > 1 0 < Human | Computer > 7 5 < Human | 12345678 | 12345678 8 : :C:C:C | 8 : :C: : 7 : : : : | 7 : : : : 6 :H:C:C:C | 6 : : : :C 5 H: : : : | 5 : :C: : 4 :H:C:C:C | 4 : :H: :C 3 H: : : : | 3 :H: : : 2 :H:H:H: | 2 : : : : 1 :H: : : | 1 : : :C: 12345678 | 12345678 | Computer > 1 0 < Human | So you think you're smart, | he? Try and beat the program 12345678 | before you boast too much! 8 : :C: :C | Follow the game through 7 : :C: : | (down each column in turn) 6 :H:C:C:C | and see if you would have 5 H: : : : | done any better than our 4 :H:C:C:C | hapless editor who, although 3 H:H: : : | he got his nose briefly in 2 :H: :H: | front, ended up wiped out 1 :H: : : | by the ZX! 12345678 | | The computer move routine Computer > 2 1 < Human | is surprisingly effective | in games like this where the 12345678 | moves are strictly limited 8 : :C: :C | in type and a logical ap- 7 : :C: : | proach is best most of the 6 :H:C: :C | time. Your best chance of 5 H: : : : | victory is to wait for a 4 :H:C:C:C | 'mistake', i.e. a bad 3 H: : : : | random move and then capi- 2 :H: :H: | talise on it. If the ZX 1 :H: : : | throws in a genius move 12345678 | instead... forget it! | Computer > 2 3 < Human | | 12345678 | 8 : :C: : | 7 :H: : : | 6 :H: :C:C | 5 H: : :C: | 4 :H: :C:C | 3 H: : : : | 2 :H: :H: | 1 : : : : | 12345678 | |