Jump Over Left Menu
Chapter 3: Board Games
This chapter deals with four common board games, namely chess, draughts (checkers), Kalah, and GO. To equip the computer to deal with board games it is necessary to define a representation of the board and positions on it, and to furnish the computer with a program which will generate legal moves and also execute them. This is a pure programming problem and is the main consideration of this chapter. The problem of providing the machine with methods of choosing a suitable move from such generated lists is considered in Chapter 4.
To test and demonstrate the techniques described a program was written in Algol to solve any two-move mate problem (10). The program and the tables required to drive it (with the omission of castling and en passant captures) are given in Appendices 1 and 2 of this sub-chapter.
The first decision is to choose a numerical notation for the 64 squares of the chess board. Fig. 3.1(a) is the simple board notation chosen for this discussion. White always plays from south to north, and initially occupies squares 1 to 16. The purpose of square 65 is to detect pawns capturing outside the board (see section 2.3).
The next decision is to choose a notation for the chess men. Each man is described by a different integer. Thus king (K) = 6, queen (Q) = 5, rook (R) = 4, bishop (B) = 3, knight (N) = 2, and pawn (P) = 1.
To simplify the problem of detecting captures the two sides are placed on separate boards. Fig. 3.1(b) is an example of board position, and Fig. 3.1(c) and 3.1(d) give the breakdown of the white and black men into their separate camps. As will be seen when listing moves, it is only necessary to know the colour (and therefore direction) of a pawn; the colour of a piece is immaterial.
The most important feature of the program is that it requires six tables (arrays) to drive it. To keep the program small it is best if these tables are read in rather than computed, and for this reason they are given in full in Appendix 2. Moreover it is simpler to understand and check how they work.
The six tables fall naturally into three groups; these are the knight and king, the bishop and rook, and the white pawn and the black pawn. (The moves of the queen are obtained by treating her first as a rook and then as a bishop.)
The knight and king tables
Appendix 2(a) is the table for the knight. It consists of 64 rows (each row corresponding to a square on the board as given in Fig. 3.1(a)), the numbers in the left hand column being only for reference and not part of the table. The first eight elements of each row give the eight possible knight moves from the particular square. The ninth element of the row is a back pointer to circumvent the zeros which pad out the table.
Consider row 1. This is used if a knight is in square 1. The last element of the row is the back pointer (7), and the preceding two elements are the number of the squares (18 and 11). The zeros in the table are never accessed.
Fig. 3.1 Representation of white and black men on the board. White plays from south to north.
The table of moves for a king (Appendix 2(b)) is constructed in exactly the same way, so the procedure knight or king in the program only requires the number of the square occupied by a knight or king, coupled with the appropriate table, to read off the squares the piece can move to. These possible moves are stored sequentially in a list called moves.
Note that two checks are made before accepting a move (these checks apply to all the men when listing their moves). Firstly, no man is allowed to move to a square which contains a friendly man. And secondly, if the man can move to a square containing the opponent's king (check the array opponents for a 6), then the listing of further moves is pointless and will be terminated (by exiting via the label cut off). This latter device is really used to check the legality of the opponent's previous move. For castling the king see the original paper.
The rook and bishop tables
Appendix 2(c) is the table used to generate the rook's moves. The first row of numbers is the increment to move the rook from its initial square in each of its four possible directions, i.e. east (+1), west (-1), north (+8), and south (-8).
Again consider row 1, which is used if a rook is in square 1. The first number is the terminal square on the board (see Fig. 3.1(a)) if it moves in an easterly direction (8), the second if it moves west (1), the third if it moves north (57), and the fourth if it moves south (1). To move west and south from square 1 is impossible, but Algol, unlike Fortran, can cope with these attempts because a loop can be executed zero times and, therefore, no move is generated.
The greatest number of moves a rook can have is 14, all of which would be produced only if the rank and file of the rook were empty, or if just the terminal squares contained enemy pieces. However, as in the knight or king procedure, each square generated must be tested for the presence of a friendly man. If he is present, then the move to that square is ignored and the next increment, i.e. direction, is selected:
if my man in[i] ≠ 0 then goto new direction;
If the square does not contain a friendly man, then the move is added to the list moves, and a new test is now made for the square being occupied by a hostile man:
if opponents [i] ≠ 0
If he too is absent the next square in the current direction is generated. Otherwise, the procedure will exit if that man is the opponent's king (like the knight or king move), or else it will select another direction. When it has exhausted all four directions, it terminates.
The bishop table (Appendix 2(d)) operates in exactly the same way. The four directions this time are north-east (+9), south-east (-9), north-west (+7), and south-east (-7).
The white and black pawn tables
Unlike the pieces, the colour of pawns is important. In the program, white pawns move up the board and black pawns move down, hence two tables are needed. The pawn is the most difficult man of all to generate moves for because it has five distinct moves. Consider the white pawn:
- from its starting position it can move either one or two empty squares up the board;
- from then on it advances 1 empty square at a time;
- captures opponents in the immediate north-east or northwest square;
- becomes a queen, rook, bishop, or knight on reaching the eighth rank; (
- captures en passant.
The black pawn differs only in that it must always move down the board.
The tables deal only with moves of types (1), (2), and (3). Queening (4) is dealt with by the program (see Making a move). For en passant captures see the original paper.
Appendix 2(e) gives the table used to generate the white pawn's possible moves. Pawns can only exist in the squares 9 to 56, and the rows are numbered accordingly. The first column shows the pawn moving forward one square and if this square is empty the move is recorded. Then, and only then, the program will try to advance the pawn two squares (the number of this square is in the second column). If that square is also empty then the move is also recorded. Note that once a pawn has moved, the double move derived from the table is always suppressed because the square is apparently occupied (by itself!). The third and fourth columns give the squares which may be entered provided an opponent is in them (i.e. captures). Square 65 of the opponent is always empty (a no-man's land), catering for edge effects. The black pawn's table (see Appendix 2(f)) operates in exactly the same way. Once again, the procedure white or black pawn move only requires to know the square a pawn occupies and the table appropriate to the pawn's colour. The usual test for taking the opponent's king is made.
Listing the moves
The procedure list moves uses the three procedures described in the previous section, and works for either black or white men.
Consider Fig. 3.1(b), in which the position is a two-move mate for white. Figs 3.1(c) and 3.1(d) are the required representation of the position stored in the arrays whitemen and blackmen.
List moves has five parameters:
piece - an integer array (dimension 0:16) describing
- how many white or black men are on the board (in piece ) and
- where each of them is (see Figs 3.1(e) and 3.1(f)). This array saves time scanning the board for men, but loses time when moves are actually made.
- mymanin - a representation of the board containing the pieces of the side whose moves we wish to list (see Fig. 3.1(c)); this has already been used when checking if a move is to the square of a friendly man.
- opponents - similar to (2), but containing only the opponent's pieces. This is used to detect captures, and therefore must be separated from mymanin (see Fig. 3.1(d)). It also detects if the opponent's king was en prise as already mentioned.
- startat - the generated moves (stored in a large array called moves) begin at moves[startat].
- cutoff - a label used when the opponent's king can be taken, i.e. his last move was illegal.
On entry, the information generated will be stored sequentially in the array moves, starting from element startat. For the example given in Fig. 3.1 (b-f), a loop is set up to scan the 11 men
for pointer:= piece step - 1 until 1 do
and square successively becomes the number of the square each white man occupies. If the square is empty, the man has been captured. However, if there is a man there, then he is first identified (by storing 3 items of information in the array moves) before generating his moves. The information is
- pointer - his position in the array piece
- mymanin[square] - his value (pawn = 1, knight = 2, etc.)
- square - his present position on the board
and is used later when the moves are actually made.
The next instruction in the procedure is crucial. moveof is declared as a switch, and the result of
goto moveof [mymanin[square]]
is to call the appropriate procedure with the correct parameter. Note the colour of a pawn is checked to decide which table to use, and the moves of a queen are the result of a rook and then a bishop call.
In the example, the 11th man is considered first (the loop runs faster if written this way). He is in square 62 of the white men board which contains the number 2, i.e. a knight. Therefore, moves[c] is 11, moves[c+ 1] is 2, and moves[c+2] is 62.
The program then jumps to label a knight, obeys the call knight or king move (knight), and generates the moves for a knight located in square 62, i.e. the list 56, 47, 45, 52. The program then jumps to label nextman, which checks if any moves have been generated (the identification will be overwritten if the man cannot move). If so, it stores - square in the moves list ( -62 in the case of this knight) to indicate the termination of the man's moves, and then considers the next man in the list piece. It similarly continues until the list is exhausted. The resulting list of numbers in moves is given in Fig. 3.2. Note that two pawns (numbers 5 and 2) have no moves and are omitted.
|knight||11||2||62||56, 47, 45, 52||-62|
|bishop||10||3||57||50, 43, 36||-57|
|bishop||9||3||51||60, 42, 58, 44, 37||-51|
|rook||7||4||33||34, 35, 36, 41, 49, 25, 17, 9, 1||-33|
|knight||4||2||18||35, 28, 3, 1||-18|
|queen||3||5||14||15, 16, 13, 6, 23, 5, 21, 28,7||-14|
|king||1||6||10||1, 2, 3, 9, 11, 17, 19||-10|
Fig 3.2 List of moves of white for position in Fig. 3.1
After generating the moves of all the men, the position of the last entry is recorded in startat. This marker is used when the moves are actually being made. Illegal moves (the king cannot move to squares 11 or 19) will be detected when they are actually made and it is found that the opponent can then take the king (see next section).
Making a move
The procedure make move operates on the list generated by list moves. Its functions are:
- To alter the contents of the four arrays whitemen, blackmen,
whitepiece, and blackpiece, depending on which side has the move
(if the depth is odd then white, otherwise black). To do this, it needs to know:
- the squares from and to which a man can move (pointer into the list moves gives this information. In the example, pointer equals 3 for the knight's first move, hence from is 62 and to is 56);
- the position in array mypiece of the man it is about to move (in the example the knight is in the 11th position). This information is in locate [depth]; and finally
- the initial value of the man in case it is a pawn which queens. This information is in q[depth].
- A1: the value of the man (q[depth]) is stored in to (unless it is a pawn queening in which case a queen, rook, bishop and knight (5,4, 3, and 2) substitution is successively made);
- A2: the square from is cleared;
- A3: any possible capture on the man's previous move (when the square from was entered) is restored to the opponent's board;
- A4: any possible capture in the new square is now recorded, c[depth] usually becomes zero but this does not matter;
- A5: clear his board of any possible man in square to;
- A6: update the list of positions of men on the board.
- After making a move, the depth is increased (D:) and the opponent's replies are generated for the new board configurations (R:). This tests if the move just made is legal and, if not, the call of listmoves will return to the label illegal move effectively ignoring the move just made.
- If the move is legal, the list of opponent's replies is ready to be made. The number of the first opponent (N:) and his value (V:) are initialised and the procedure terminates (the purpose of back to [depth], (BT:) which records the initial square of the man just moved, is explained in Section 5).
The effect of make move operating on the list moves is to cycle a man around the squares he can move until a negative to square is reached. This means that the man has completed his moves. The man and board are, therefore, returned to their starting positions (the five operations labelled B1 to B5. N.B. We know hismen[-to] must be zero, otherwise the operations are identical to AI-A5). The next man's moves are initialised (NM:) and the procedure exits via label continue, which checks that the list of moves has not been exhausted and usually results in an immediate call of the procedure make move again, and the new man begins his moves.
Solving two-move mates
In order to test the validity and speed of the procedures listmoves and makemove, the complete program uses them to solve two-move mate problems with white to move. The program works in the same way as a human solves the problem, albeit rather tediously. That is, it makes white's opening moves one after the other until it finds the opening move which, regardless of what black does in his next two moves, allows white to check on his second move (to avoid stalemate) and to capture the black king on his third move.
To speed up the solution it is sometimes necessary to reverse a move. For example, white makes an opening move (W1), and black makes a reply (B1) such that white cannot check the black king with his second move. Now it is necessary to reverse the black reply (B1) before attempting another white opening move. This is done by calling procedure reverse move, giving the present square that the blackman occupies and his initial square. The initial square of all men, before beginning to make that man's moves, is always stored in back to[depth].
In order to show the flow of the solution, consider the position given in Fig. 3.3(a). There are 11 white men and 9 black men in the positions described by the arrays whitepiece and blackpiece (Fig.3.3(b)).
Fig. 3.3 Position is two-move mate inevitably. White has only one move, black has only one (legal) reply, and white still only has one move
When black's moves at depth 2 are exhausted, the solution has been obtained.
The flow of the program is given in Fig. 3.4, and the actual contents of the array moves, giving the moves generated at the five depths, is given in Fig. 3.5.
When run on an ICL Atlas computer the program can solve two-move mates in an average of about 45 seconds. Because of the table drive it is very easy to translate the program into other languages and run it on a variety of machines. The program was written in Atlas Basic Language which then took only 5 seconds on average; the CDC 6600 dialect of Algol (different card code and I/O statements are the main problem in this case), which took about 50 seconds; and finally in CDC 6600 Basic Language, which held the record at only 2 seconds per two-move mate. As the CDC 7600 is compatible to the 6600, and about four times faster, then the final program should solve problems almost immediately they are presented to the machine.
Fig. 3.4 Flow of program when solving problem given in Fig. 3.3
|listing of moves terminated|
Fig. 3.5 Contents of array moves on completion of problem given in Fig.3.3. Compare with Fig. 3.4
Fig. 3.6 Program fails to find two-move mate for white
This does not mean that the problem of two-move mates is completely solved. Fig. 3.6 is an example of a two-move mate problem which the program cannot solve without (at the moment) a lot of human aid. Can the reader see why? A hint is that Fig. 3.3(a) given here is legally possible, whereas the corresponding Figure in the original paper was impossible.
Finally, the techniques described here are designed mainly for speed. The program was compared to another Algol program which could do N-move mates (via recursion) using the traditional 12 × 12 board with no cut off facility (43). This latter program was over twice as slow but one quarter the size of the program listed here, the main saving being that no table drive was used.
Appendix 1 Algol program to solve two-move mate problems
begin integer i,j,k,l,m,n,depth,w1,b1,w2,b2; integer array knight,king[1:576], bishop,rook[0:259], wpawn, bpawn[36:227], whitepiece,blackpiece[O:16], whitemen,blackmen[1:65], c,q,locate,numberofmoves,backto[1:5], moves[1:500]; procedure listmoves(piece,mymanin,opponents,startat,cutoff); integer array piece,mymanin,opponents; integer startat; label cutoff; begin switch moveof := apawn,aknight,abishop,arook,aqueen,aking; integer c,i,j,k,l,pointer,square; procedure knightorkingmove(knightorking); integer array knightorking; begin j : = 9*square; for i := knightorking[j] step 1 until j-1 do if mymanin[knightorking[i]] = 0 then begin if opponents[knightorking[i]] = 6 then goto cutoff; c:= c+1; moves[c] : = knightorking[i] end end of knightorkingmove; procedure rookorbishopmove(rookorbishop); integer array rookorbishop; begin for j := 0 step 1 until 3 do begin k := rookorbishop[j]; k is increment: l := rookorbishop[4 *square + j]; l is terminal square: for i : = square + k step k until l do begin if mymanin[i] ≠ 0 then goto newdirection; c:=c+1; moves[c] : = i; if opponents[i] ≠ 0 then begin if opponents[i] = 6 then goto cutoff else goto newdirection end end; newdirection :end end of rookorbishopmove; procedure whiteorblackpawnmove(pawn); integer array pawn; begin for i : = 4*square,i + 1 do begin j : = pawn[i]; if mymanin[j] ≠ 0 or opponents[j] ≠ 0 then goto pawncapture; c:= c+l; moves[c] : = j end; pawncapture: for i := 4*square+2,i + 1 do if opponents[pawn[i]] ≠ 0 then begin if opponents[pawn[i]] = 6 then goto cutoff; c:=c+l; moves[c] : = pawn[i] end end of whiteorblackpawnmove; c : = startat; for pointer: = piece[O] step -I until 1 do begin square: = piece[pointer]; if mymanin[square] = 0 then goto continue; moves[c] := pointer; moves[c+1] := mymanin[square]; moves[c+2] := square; c:= c+2; goto moveof[mymanin[square]]; apawn: if whitemen[square] = 1 then whiteorblackpawnmove(wpawn) else whiteorblackpawnmove(bpawn); goto nextman; aknight: knightorkingmove(knight); goto nextman; aking: knightorkingmove(king); goto nextman; arook: rookorbishopmove(rook); goto nextman; aqueen: rookorbishopmove(rook); abishop: rookorbishopmove(bishop); nextman: if moves[c] ≠ square then begin moves[c+1] := -square; c : = c+2 end else c := c-2; continue :end; startat := c end of listmoves; procedure makemove(pointer ,mymen,hismen,mypiece, hispiece,continue) ; integer pointer; integer array mymen,hismen,mypiece,hispiece; label continue; begin integer from, to; goto start; illegal move: depth := depth - 1; pointer := pointer + 1 ; start: from := moves[pointer]; to : = moves[pointer + 1]; if to > 0 then begin A1: if q[depth] = 1 and (to>56 or 9>to) then pawn queening: begin pointer := pointer -1; mymen[to] := if mymen[to] = 0 then 5 else mymen[to] -1; if mymen[to] = 2 then pointer := pointer + 1 ; end else mymen[to] := q[depth]; A2: mymen[from] := 0; A3: hismen[from] := c[depth]; A4: c[depth] := hismen[to]; A5: hismen[to] := 0; A6: mypiece[locate[depth}} := to; D: depth := depth + 1; to := numberofmoves[depth] := numberofmoves[depth -1]; R: listmoves(hispiece,hismen,mymen,num berofmoves[ dept hI, illegalmove); N: locate[depth] := moves[to]; V: q[depth] := moves[to+1]; BT: backto[depth] := moves[to+2] end else begin B1:mymen[ -to] := q[depth]; B2:mymen[from] := 0; B3:hismen[from] := c[depth]; B4:c[depth] := 0; B5:mypiece[locate[depth}} := -to; NM: locate[depth] := moves[pointer + 2]; q[depth] := moves[pointer + 3]; backto[depth] := moves[pointer + 4]; pointer := pointer + 3; goto continue end end of makemove; procedure reversemove(from,mymen,hismen,mypiece); integer from; integer array mymen,hismen,mypiece; begin mymen[backto[depth}} := q[depth]; mymen[from] := 0; hismen[from] := c[depth]; c[depth] := 0; mypiece[locate[depth]] := backto[depth] end of reversemove; ENTRY We assume tables and problem have been read in: c := 0; No capture as yet: depth : = 1; numberofmoves : = 1; get ready to generate whites opening moves: listmoves( whitepiece, whitemen, blackmen,numberofmoves [1 , theend); locate := moves[l]; q := moves; store position and value of whites first man to move: for w1 := 3 step 1 until numberofmoves do begin makemove(w1, whitemen, blackmen, whitepiece,blackpiece, w1continue); for b1 : = numberofmoves+2 step 1 until numberofmoves do begin makemove(b1,blackmen, whitemen, blackpiece, whitepiece, b1continue); for w2 := numberofmoves + 2 step 1 until numberofmoves do begin makemove(w2, whitemen,blackmen, whitepiece, blackpiece, w2 continue); n : = numberofmoves; listmoves( whitepiece, whitemen, blackmen,n,notstalemate) ; if white is not checking king on second move then: goto w2continue; try another: notstalemate: for b2 := numberofmoves+2 step 1 until numberof moves do begin makemove(b2,blackmen, whitemen, black piece, whitepiece, b2 =continue); depth: = 4; black has avoided check mate therefore reverse his last move: and try another 2nd level white move: reversemove(moves[b2+1],blackmen,whitemen,blackpiece); goto w2continue; b2continue :depth := 4 end; depth := 3; white is always succeeding from his second move therefore reverse it: reversemove(moves[w2 +1],whitemen,blackmen, whitepiece); and let black alter his first reply: goto b1continue; w2continue :depth := 3 end; depth := 2; and let white try a new opening move: reversemove(moves[b1 + 1], blackmen, whitemen,blackpiece); goto wlcontinue; blcontinue :depth := 2 end; print position ; THE ANSWER: goto theend; wlcontinue:depth := 1 end; theend: end
|Square||WHITE PAWN TABLE|
|Square||BLACK PAWN TABLE|
This game is better known as checkers in America. Fig. 3.7 gives the official square designations used in reporting games. If one wishes to program this game in a high level language then tables, similar to those used for chess, can be designed. Because of the relative simplicity of the pieces, all the moves can be compressed into one array, of which Fig. 3.8 is an example. The reader who has understood how the pawn table works for chess should also understand this table.
Fig 3.7 Multiple capture described in standard notation
One greatly simplifying feature of the game is the huffing rule, which states that if a capture move is possible, then a capture move must be made. Because of this one should primarily look for captures, and only incidentally record normal (non-capture) moves. For example, a king (white or black) in square 10 would access the table thus:
|NORMAL MOVE||CAPTURE MOVE|
The first thing to do is examine the immediately diagonal squares (15,14,6,7) for the presence of an enemy piece. If any of these squares are empty then record them as normal moves in a separate list from the capture moves. If, however, an enemy piece is detected then a second test is made to see if it can be captured, using the corresponding number in the last four columns of the table. In this case, if any enemy piece is in square 15 then square 19 must be empty for a capture to be made. Once a capture has been found then the further recording of normal moves is ignored.
Fig 3.8 Table to generate moves of draughtsmen
An additional feature of a capture is that it may lead to further captures. This can be dealt with by recursive functions (see Christopher Strachey's paper in Scientific American, September 1966), but such built in features of a language are notoriously slow. It is much better to write one's own stack procedures (a language which allows recursion is basically providing an automatic stacker).
Fig. 3.7 is the most difficult example of multiple captures. It actually results in only four distinct final positions (A, B, C, and D), but as such situations are rare it is not worth having the program eliminate the superfluous paths. As each capture is detected the resulting position (for making that capture) is stored in a stack. In the example, when the king reaches square 22 it can continue in three directions (squares 31, 13, and 15). The resulting positions for moving to squares 31 and 13 are stored, and the program continues down the 15 branch. Eventually it exhausts that branch (incidentally stacking and unstacking to do so), and then recalls the 13 branch and finally the 31 branch. Stacking of non-terminal positions is discussed in greater detail in the next section on Kalah.
The use of tables is acceptable in higher level languages, but such programs run slowly. Most game playing programs (especially the listing of moves part) are written in more basic languages, usually the machine language itself. Apart from the advantage of the code being optimal, this also means the programmer can handle the actual bits of his information word and use more esoteric logical and shifting instructions. Arthur Samuel, in his now classic paper (11), did exactly this when he programmed checkers. He was so successful that no one since has really bothered to write another checker playing program.
Samuel's initial work was done on an IBM 704, which is a 36 bit machine. The board notation he chose is shown in Fig. 3.9. What the new notation (which can easily be mapped into Fig. 3.7 when actually inputting and outputting moves) allows is the ability to calculate all the moves given in Fig. 3.8 by adding or subtracting constants. Thus for square N:
To overcome the problem of edge effects (squares 9,18,27 and 36 don't exist), Samuel represented his Black men, White men, Black kings, and White kings in four separate 36 bit words. Fig. 3.10(b) gives the contents of two of these four words for the position in Fig. 3.10(a). EMPTY SQUARES is obtained by OR-ing the four words together and NON-EQUIV BALANCEing with:
Fig 3.9 Samuel's notation of the draughts board
Fig 3.10 Samuel's representation of a position within the machine
The cyclic shift instruction is then used to calculate available moves for all the pieces simultaneously. One can, for example, compute the moves for Black by shifting EMPTY SQUARES 4 bits to the left and then form the logical AND between BLACKMEN and EMPTY SQUARES thus:
BLACKMEN 111111110111100000000000000000000000 AND EMPTY SQUARES 000000000111101111000000000000000000 = 1111
i.e. pieces in 10, 11, 12, and 13 can move . If EMPTY SQUARES is now further shifted left by 1 bit (giving 5 bits left in total), and again AND-ed with BLACKMEN then black's ordinary moves in the direction are generated. Capture moves are handled by a simple extension of this technique.
One of the drawbacks of this method is that, although the moves have been generated, they still have to be interpreted from the resulting bit pattern. Some computers (the ICL Orion) can actually tell you how many bits are set in a word (how many moves), and also have instructions to help the programmer detect which bits are actually set (shift down to end most one-bit). Samuel did not have such powerful instructions, and had to use tables look-up to count the bits and locate them for move reporting. Despite these problems the notation and the logical operations on the pieces treated as bits is undoubtedly the fastest way to generate the moves for checkers. A further advantage is the compression of the position, which has many benefits, some of which are described in Chapter 4.2.
The board for this game is shown in Fig. 3.11. There are two players. Each player controls a row of round pits and the rectangular bowl at his right (his kalah). The object is to get more counters (playing pieces) in one's own kalah than the opponent can get in his.
Fig. 3.11 Kalah board and notation
There are usually six pits and, at the outset, six counters in each pit. To move, a player picks up all the counters in one of his pits and moving anti-clockwise (see arrow), distributes them one by one into each successive pit. If there are enough counters to reach beyond his own kalah they are distributed one by one into the opponent's pits and then belong to him. The only place ever skipped is the opponent's kalah. Once in a kalah, the counters remain there until the end of the game. The game ends when all the pits on one side are empty.
The method of play, by distributing stepwise to the right, is subject to two simple rules:
- If the last counter lands in an empty pit on your own side opposite a non-empty opponent's pit then you capture all the counters in his pit. They are placed, together with the one making the capture, in your own kalah. A capture ends a move.
- If the last counter lands in your own kalah then you have another turn.
This game is different to chess and draughts in that the pieces have no individual moves. One similarity with draughts is that rule 2 above allows a player to make several continuation moves from certain positions. For example,
From this relatively simple position there is a choice of six terminal positions. Ignoring captures, move 1 is the best in terms of filling the kalah.
If this game is programmed it is important to generate the continuation moves quickly and accurately. Recursive functions can be used but it is better to design one's own stack. Stacks are very common devices when writing and running game playing programs (they are used extensively in compilers also). The particular example of generating kalah moves (ignoring the capture test) will now be taken to illustrate how stacks work.
The pits are scanned in the following order from right to left.
The pits are emptied and their contents played round anticlockwise as already described. If the final counter lands in a pit then the position is output in the list of moves. If the final counter lands in the kalah, the position is stored in the stack, the stack is incremented and the next pit is considered. When the sixth pit has been dealt with (it could have contained six counters and, therefore, its move would have just been stored in the stack), the program checks the stack for any unfinished moves and, if there are any brings down the last unfinished position which was stored, decrements the stack, and then loops. When the stack is empty all possible continuation moves should have been dealt with. Note that because of the a priori unknown length of the continuation moves, it is better to store and output positions rather than how they are actually realised.
To illustrate the stack working, consider the position
This would result in the following stack activity and final output (a * means a move is terminal, a c means it is a continuation and is entered in the stack, a - means the pit is empty). Note how the stack never grows beyond 3.
|Right to left scanning|
Right to left scanning ensures that the stack never grows larger than the number of pits under consideration (in a normal game six pits are used). This is important, because if the pits are scanned from left to right then the following stack activity occurs. Note the growth of the stack before the first output is obtained, and also how the order of the generated terminal positions is almost completely reversed.
|Right to left scanning|
To allow for all possible continuations from six pits a left to right scan must have a stack which can go 35 levels deep! This is wasting space and time.
The point being made is that the direction of a scan does affect the stack activity. Another bonus of the right to left scanning is that the better moves (in terms of filling the kalah) are output last. This is very advantageous when it comes to using the pruning techniques described in Chapter 4.
The main part of the program to generate kalah moves is the stacker. Having written this part it is important to test it. Just as chess can be tested with two-move mates, so kalah positions can be entered which have a known number of terminal positions. The best known test is when each pit has the correct number of counters to cause a continuation move. For the ordinary board, this position is
which has 912 terminal positions or moves.
It is not necessary to restrict the program to playing on a board with only six pits; it is possible to ask the program to solve the above problem for any number of pits, with the following results:
|Number of pits||Number of moves|
The case of ten pits took a Fortran program 4.3 seconds to solve on an IBM 360/75 computer. Such statistics are not immediately relevant to game playing, but it is important to check that the program is operating correctly when listing moves. Thus tests, such as the above, should always be devised and run.
Another interesting test for the kalah move generator is to enter patterns which are known to have a sequence of continuation moves resulting in all the counters entering the kalah. Some simple examples are
For a board with 50 pits the following pattern can be cleared entirely into the kalah in 839 continuation moves:
50,48,46,44,42,40,38,36,34,32,30,28,26,24,22,20, 18,16,14,12,10,8,6,4,2,25,21,17,13,9,5,1,15, 9,3,12,4,9,11,10,6,8,4,1,1,1,1,1,1,1
The reader may like to discover how this (unique) pattern is calculated, and also how to generate the pattern for any number of pits. Some actual mechanics of selecting good moves in Kalah are dealt with in Chapter 4.
This oriental game is probably the most difficult board game to be played internationally and have recognised masters. It is the Japanese equivalent to chess in Russia. Good players are greatly respected and, in the last twenty years, the game has become very popular in America and Europe. Despite this spread, there exists only one paper on a GO playing program by Albert L. Zobrist (12), although Remus used the game to study machine learning (13), and Thorp (14), of Black Jack fame (see Chapter 2), considered GO mathematically and solved some simple versions of the game.
Description of GO
The rules of GO are simple. The complexity is caused by the size of the board, which is a 19 by 19 grid (see Fig. 3.12). The lines of the grid intersect at 361 nodes. One player, called Black, has 181 black stones and the other player, called White, has 180 white stones. Black plays first.
Fig. 3.12 GO board and notation
The two players alternate in placing their stones on empty nodes. Stones of the same colour which are connected by row or column (not diagonal) adjacency are called chains. The empty nodes which are adjacent to a chain are that chain's breathing spaces. A chain is captured and removed from the board when it has no breathing spaces.
A player, at his turn, may play his stone on any empty node, with two exceptions: (1) the suicide rule: he may not play in the last breathing space of one of his chains unless he captures, and (2) the Koh rule: he may not capture a single stone which has just captured one of his stones.
A player may also choose to pass at his turn. The game is terminated after two consecutive passes. The player with the greater (number of empty nodes surrounded by his stones plus number of opponent's stones captured) is the winner.
In Fig. 3.12 the left hand side of the board shows groups of captured stones. Although incomplete, the bottom left configuration (illustrating the ladder attack) is irretrievable; any further black stones played can also be captured eventually, so Black should cut his losses and treat the group as already lost. In contrast it is impossible for White to capture any of the chains on the right hand side of the board. This is because they all have or can form two breathing spaces (or eyes), and White cannot blind them both (it is forbidden by the suicide rule).
The most striking thing about GO (in contrast to chess) is that to list legal moves is easy, but to execute them for all configurations (e.g. the capture of a complicated set of chains) is very difficult. The middle configuration in Fig. 3.12 actually captures four distinct chains if White plays in the centre.
Despite the relative ease of listing all moves (and hence looking ahead), this method has not been successfully applied to GO. Instead the approach has been to develop programs which break the board up into, as far as possible, independent armies or segments. This reduces the problem, hopefully, to a point where templates (similar to those used in noughts and crosses) can be used to recognise (1) critical situations which must be replied to immediately, e.g. threat of capture, and (2) patterns which require a limited look-ahead, e.g. a possible ladder attack, splitting or merging of armies.
In Fig. 3.12 the black and white stones are arranged mainly in chains. However a player who always places his stones to form such compact formations will not be successful. In the opening stages of a game between experienced players the initial stones are spaced out over the entire board, rather like an artist sketching out the broad outline of a picture; the middle phase of the game is a more direct clash between the players when areas of the board are definitely won by one player or the other. Even at this stage the board is still only partially covered by many seemingly unconnected chains; nevertheless the board has been segmented into areas controlled by one or the other player.
Humans are surprisingly good at identifying and separating areas controlled by the two sides, and the first task for a program which plays GO is to segment the position into these domains of influence of black and white stones. This defines the boundaries of the armies where, usually, most of the vital play occurs.
Zobrist used the following technique. The board is a 19 × 19 integer array. The position is represented by a +50 for every black stone, a -50 for every white stone, and 0 elsewhere. Each positive point sends out a +1 to each of its four neighbours, each negative point sends out a -1 to each of its neighbours. This process is repeated four times.
Fig. 3.13 is a Fortran program to implement this algorithm (N.B. board is extended to 21 × 21 to save testing for nodes off the actual board). Fig. 3.14 shows the result for a single black piece, and Figs. 3.15 and 3.16 show the final board position of a game played by Zobrist's program against a university undergraduate. The computed domains of influence are shown in Fig. 3.16. The positive areas are Black's domains (the undergraduate), and the negative areas are White's (the computer). Note that it is impossible to have numbers between ±(17-33).
1 DIMENSION IGOR(21,21),IGOR1(21,21) 2 DO 40 I = 1,21 3 DO 41 J = 1,21 4 IGOR(I,J) = 0 5 41 IGOR1(I,J) = 0 CLEAR THE TWO BOARDS 6 40 CONTINUE 7 K = 50 8 DO 20 J1 = 1,2 9 15 READ(5,10) I,J 10 10 FORMAT(2I2) 11 IF(I) 12, 11, 11 12 11 IGOR(I+1,J+1) = K READ IN POSITION 13 GOTO 15 14 12 K = -50 15 20 CONTINUE 16 DO 100 L = 1,4 APPLY ZOBRIST'S ALGORITHM 17 DO 1 I = 2,20 18 DO 2 J = 2,20 19 K = 1 20 IF(IGOR(I,J)) 3,2,4 21 3 K = -1 22 4 IGOR1(I+1,J) = IGOR1(I+1,J) + K 23 IGOR1(I-1,J) = IGOR1(I-1,J) + K 24 IGOR1(I,J+1) = IGOR1(I,J+1) + K 25 IGOR1(I,J-1) = IGOR1(I,J-1) + K 26 2 CONTINUE 27 1 CONTINUE 28 DO 30 I = 1,21 29 DO 31 J = 1,21 30 IGOR(I,J) = IGOR1(I,J) +IGOR(I,J) 31 31 IGOR1(I,J) = 0 32 30 CONTINUE 33 100 CONTINUE 34 DO 200 I= 2,20 35 WRITE (6,202) (IGOR(I,J), J=2,20) PRINT RESULT 36 202 FORMAT(' ',19I4) 37 200 CONTINUE 38 STOP 39 END
Fig. 3.13 Complete Fortran program to demonstrate Zobrist's algorithm
Fig. 3.14 Zobrist's finite difference algorithm operating on a black stone
Fig. 3.15 Final position segmented by human GO player
Fig. 3.16 Final position segmented by Zobrist's algorithm (cf. with Fig. 3.15)
The game was stopped at this point by agreement. Black had captured 14 stones, and White, 21 stones. The final score (sum of nodes surrounded plus stones captured) was 59 to Black and 66 to the computer, a seven stone victory for the program.
This algorithm for segmenting the board is insufficient for assessing whether the computer is actually in control of the domains it has defined. Fig. 3.15 has been segmented by a good human GO player into only two domains, White controls the lower segment and Black the upper.
A further feature of Zobrist's program is that it can recognise that some isolated pockets it has computed (by the simple segmenting algorithm) are in reality lost chains. To do this a further algorithm creates an array which gives a direct measure of the size of the domains and the number of stones they contain. After this adjustment the segmentation of the board by the program is extremely close to that which an expert player would make. With the additional knowledge of how many stones each side has lost, the program is capable of evaluating how good or bad a position is with greater accuracy than a chess program evaluating a chess position.
Seven arrays are used to represent useful features such as breathing spaces, chains, domains of influence, etc. Having produced an internal representation of the board position the program then attempts to recognise certain critical patterns. It can, for example, recognise the position shown below.
Position to recognise
A black stone is about to be captured, but Black can connect with a stone which is part of a safe chain. The program recognises this pattern by applying a set of templates provided by the programmer. Reflections and rotations are performed to save storage space. The program has about 100 templates for a wide variety of positions. All these are used. The successful matching of a template results in (1) a certain weight being given to playing at some node as above, or (2) a heuristic look-ahead is performed on the recognised pattern. This look-ahead is usually only two moves, and again results in giving a weight to playing at some node. An example of this is a possible ladder attack, in which case the search depth can extend to 100 to see if capture eventually occurs. Having used all the templates and assigned all the weights the program then takes the node with the greatest weight as its next move. A more complete description of the use of such templates is given in Chapter 4.
Zobrist's program (incidentally written in Algol) is a good attempt at a game which has defied many attempts at automation. His finite difference algorithm for calculating domains of influence is intuitively the right approach, but his program seems to have one big failing, i.e. it cannot absolutely recognise whether an army is safe or not. It can detect some simple cases of an army with two eyes, but the general case of whether an army has (or can form) two eyes is not recognised.
An interesting problem is to design routines which can quickly recognise, and reply on request, whether certain patterns are safe armies or not, e.g.
Recognising safe armies
and also recognise patterns which can be made safe should the opponent attempt to capture them, e.g.
Making patterns safe
can be made safe, but
would be captured.
Chess is played with a fixed number of pieces, each with a value related to the number of moves they can make. It is a peculiar game in that losing one particular piece (the king) loses all the pieces; for this reason it is necessary to look closely at all the possible moves.
In contrast, GO is played with an indefinite number of pieces (the armies) whose values are slowly changing, and to lose any of them is critical. The game is therefore more closely related to noughts and crosses than chess. Zobrist's program is not so much concerned with listing all legal moves and looking into their consequences as with breaking a position down into these armies, identifying domains and areas of conflict (the boundary between two armies), and analysing critical situations in these areas (possible captures) by applying templates. The effect is that the program concentrates its attention on relatively few moves.