                     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          |

                             |