Contact us Heritage collections Image license terms
HOME ACL Associates Technology Literature Applications Society Software revisited
Further reading □ OverviewContentsIntroduction1. Algorithms2. Card games3. Board games4. Heuristics5. Some chess programs6. Practical problems7. Future developmentsAnswersReferencesIndex
ACD C&A INF CCD CISD Archives Contact us Heritage archives Image license terms

Search

   
ACLLiteratureBooksGames Playing :: Games Playing with Computers
ACLLiteratureBooksGames Playing :: Games Playing with Computers
ACL ACD C&A INF CCD CISD Archives
Further reading

Overview
Contents
Introduction
1. Algorithms
2. Card games
3. Board games
4. Heuristics
5. Some chess programs
6. Practical problems
7. Future developments
Answers
References
Index

Chapter 3: Board Games

INTRODUCTION

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.

3.1 CHESS

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.

Notation

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 tables

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.

65 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 (a) Board notation N S WB WN WB BP WR BN BQ BK WP BP BP WP WN BP WP WK WP WQ (b) Example of actual position 3 2 3 4 1 1 2 1 6 1 5 (c) "whitemen" 1 2 5 6 1 1 1 (d) "blackmen" 11 10 12 14 18 22 32 33 39 51 57 62 (e) Number and positions of white's eleven men - "whitepiece" 7 20 28 30 36 37 38 46 (f) Number and positions of black's seven men - "blackpiece"

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:

  1. from its starting position it can move either one or two empty squares up the board;
  2. from then on it advances 1 empty square at a time;
  3. captures opponents in the immediate north-east or northwest square;
  4. becomes a queen, rook, bishop, or knight on reaching the eighth rank;
  5. (
  6. 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:

  1. piece - an integer array (dimension 0:16) describing
    1. how many white or black men are on the board (in piece [0]) and
    2. 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.
  2. 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.
  3. 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.
  4. startat - the generated moves (stored in a large array called moves) begin at moves[startat].
  5. 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[0] 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

  1. pointer - his position in the array piece
  2. mymanin[square] - his value (pawn = 1, knight = 2, etc.)
  3. 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.

No. Man Present
Position
Back to
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
pawn 8 1 39 47, 46 -39
rook 7 4 33 34, 35, 36, 41, 49, 25, 17, 9, 1 -33
pawn 6 1 32 40 -32
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:

  1. 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:
    1. 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);
    2. 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
    3. the initial value of the man in case it is a pawn which queens. This information is in q[depth].
    To move a man requires six operations, labelled Al and A6 in the program:
    • 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.
  2. 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.
  3. 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)).

BB BR BK BP BP WP BP WP BP BP WP BP WP WB WP WP WR WP WR WK The simplest two-move mate position known 11 6 7 8 13 15 16 23 24 31 45 47 "whitepiece" 9 21 38 39 46 53 55 62 63 64 "blackpiece"

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.

DEPTH W1 B1 W2 B2 1 2 3 4 5 P * P BK - R2 P * BK i.e. last black move was illegal therefore try another P - N5 B * P does white now check the black king? Yes (R * K) BK - R2 P * BK i.e. last black move was illegal, there are no more, therefore, reverse last white move (B * P) and try another black move at depth 2 Black's opening replies exhausted hence answer is

Fig. 3.4 Flow of program when solving problem given in Fig. 3.3
Depth Number
of man
Value Initial
Square
To Back to Etc.
W1 1 9 1
P
31
*
38
P
-31
B1 2 9 6
K
64
-
56
R2
Illegal
-64 3 1
P
39
-
31
N5
-39
W2 3 8 3
B
24
*
31
P
-24
B2 4 9 6
K
64
-
56
R2
-64
5 11 1
P
47
*
56
K
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

WQ WN WB BK BR BP BP BP BP BP BP WN BB BN WP WP BQ WP WP WP WP WP WP BN WB WK

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[1] := 0; No capture as yet:
  depth : = 1;
  numberofmoves[1] : = 1; get ready to generate whites opening moves:
  listmoves( whitepiece, whitemen, blackmen,numberofmoves [1 , theend);
  locate[1] := moves[l];
  q[1] := moves[2]; store position and value of whites first man to move:
  for w1 := 3 step 1 until numberofmoves[1] do 
  begin
   makemove(w1, whitemen, blackmen, whitepiece,blackpiece, w1continue);
  for b1 : = numberofmoves[1]+2 step 1 until numberofmoves[2] do
  begin
    makemove(b1,blackmen, whitemen, blackpiece, whitepiece, b1continue);
    for w2 := numberofmoves[2] + 2 step 1 until numberofmoves[3] do 
    begin 
      makemove(w2, whitemen,blackmen, whitepiece, blackpiece, w2 continue);
      n : = numberofmoves[4];
      listmoves( whitepiece, whitemen, blackmen,n,notstalemate) ;
        if white is not checking king on second move then:
      goto w2continue; try another:
      notstalemate: for b2 := numberofmoves[3]+2 step 1 until numberof moves[4] 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 

Appendix 2(a)

Square KNIGHT TABLE Pointer
into
table
1 0 0 0 0 0 0 18 11 7
2 0 0 0 0 0 17 19 12 15
3 0 0 0 0 9 18 20 13 23
4 0 0 0 0 10 19 21 14 32
5 0 0 0 0 11 20 22 15 41
6 0 0 0 0 12 21 23 16 50
8 0 0 0 0 0 0 14 23 70
9 0 0 0 0 0 26 19 3 78
10 0 0 0 0 25 27 20 4 86
11 0 0 17 26 28 21 5 1 93
12 0 0 18 27 29 22 6 2 102
13 0 0 19 28 30 23 7 3 111
14 0 0 20 29 31 24 8 4 120
15 0 0 0 0 21 30 32 5 131
16 0 0 0 0 0 22 31 6 141
17 0 0 0 0 34 27 11 2 149
18 0 0 33 35 28 12 3 1 156
19 25 34 36 29 13 4 2 9 163
20 26 35 37 30 14 5 3 10 172
21 27 36 38 31 15 6 4 11 181
22 28 37 39 32 16 7 5 12 190
23 0 0 29 38 40 8 6 13 201
24 0 0 0 0 30 39 7 14 212
25 0 0 0 0 42 35 19 10 221
26 0 0 41 43 36 20 11 9 228
27 33 42 44 37 21 12 10 17 235
28 34 43 45 38 22 13 11 18 244
29 35 44 46 39 23 14 12 19 253
30 36 45 47 40 24 15 13 20 262
31 0 0 37 46 48 16 14 21 273
32 0 0 0 0 38 47 15 22 284
33 0 0 0 0 50 43 27 18 293
34 0 0 49 51 44 28 19 17 300
35 41 50 52 45 29 20 18 25 307
36 42 51 53 46 30 21 19 26 316
37 43 52 54 47 31 22 20 27 325
38 44 53 55 48 32 23 21 28 334
39 0 0 45 54 56 24 22 29 345
40 0 0 0 0 46 55 23 30 356
41 0 0 0 0 58 51 35 26 365
42 0 0 57 59 52 36 27 25 372
43 49 58 60 53 37 28 26 33 379
44 50 59 61 54 38 29 27 34 388
45 51 60 62 55 39 30 28 35 397
46 52 61 63 56 40 31 29 36 406
47 0 0 53 62 64 32 30 37 417
48 0 0 0 0 54 63 31 38 428
49 0 0 0 0 0 59 43 34 438
50 0 0 0 0 60 44 35 33 446
51 0 0 57 61 45 36 34 41 453
52 0 0 58 62 46 37 35 42 462
53 0 0 59 63 47 38 36 43 471
54 0 0 60 64 48 39 37 44 480
55 0 0 0 0 61 40 38 45 491
56 0 0 0 0 0 62 39 46 501
57 0 0 0 0 0 0 51 42 511
58 0 0 0 0 0 52 43 41 519
59 0 0 0 0 53 44 42 49 527
60 0 0 0 0 54 45 43 50 536
61 0 0 0 0 55 46 44 51 545
62 0 0 0 0 56 47 45 52 554
63 0 0 0 0 0 48 46 53 564
64 0 0 0 0 0 0 47 54 574
Square KING TABLE Pointer
into
table
1 0 0 0 0 0 2 9 10 6
2 0 0 0 1 3 9 10 11 13
3 0 0 0 2 4 10 11 12 22
4 0 0 0 3 5 11 12 13 31
5 0 0 0 4 6 12 13 14 40
6 0 0 0 5 7 13 14 15 49
7 0 0 0 6 8 14 15 16 58
8 0 0 0 0 0 7 15 16 69
9 0 0 0 1 2 10 17 18 76
10 1 2 3 9 11 17 18 19 82
11 2 3 4 10 12 18 19 20 91
12 3 4 5 11 13 19 20 21 100
13 4 5 6 12 14 20 21 22 109
14 5 6 7 13 15 21 22 23 118
15 6 7 8 14 16 22 23 24 127
16 0 0 0 7 8 15 23 24 139
17 0 0 0 9 10 18 25 26 148
18 9 10 11 17 19 25 26 27 154
19 10 11 12 18 20 26 27 28 163
20 11 12 13 19 21 27 28 29 172
21 12 13 14 20 22 28 29 30 181
22 13 14 15 21 23 29 30 31 190
23 14 15 16 22 24 30 31 32 199
24 0 0 0 15 16 23 31 32 211
25 0 0 0 17 18 26 33 34 220
26 17 18 19 25 27 33 34 35 226
27 18 19 20 26 28 34 35 36 235
28 19 20 21 27 29 35 36 37 244
29 20 21 22 28 30 36 37 38 253
30 21 22 23 29 31 37 38 39 262
31 22 23 24 30 32 38 39 40 271
32 0 0 0 23 24 31 39 40 283
33 0 0 0 25 26 34 41 42 292
34 25 26 27 33 35 41 42 43 298
35 26 27 28 34 36 42 43 44 307
36 27 28 29 35 37 43 44 45 316
37 28 29 30 36 38 44 45 46 325
38 29 30 31 37 39 45 46 47 334
39 30 31 32 38 40 46 47 48 343
40 0 0 0 31 32 39 47 48 355
41 0 0 0 33 34 42 49 50 364
42 33 34 35 41 43 49 50 51 370
43 34 35 36 42 44 50 51 52 379
44 35 36 37 43 45 51 52 53 388
45 36 37 38 44 46 52 53 54 397
46 37 38 39 45 47 53 54 55 406
47 38 39 40 46 48 54 55 56 415
48 0 0 0 39 40 47 55 56 427
49 0 0 0 41 42 50 57 58 436
50 41 42 43 49 51 57 58 59 442
51 42 43 44 50 52 58 59 60 451
52 43 44 45 51 53 59 60 61 460
53 44 45 46 52 54 60 61 62 469
54 45 46 47 53 55 61 62 63 478
55 46 47 48 54 56 62 63 64 487
56 0 0 0 47 48 55 63 64 499
57 0 0 0 0 0 49 50 58 510
58 0 0 0 49 50 51 57 59 517
59 0 0 0 50 51 52 58 60 526
60 0 0 0 51 52 53 59 61 535
61 0 0 0 52 53 54 60 62 544
62 0 0 0 53 54 55 61 63 553
63 0 0 0 54 55 56 62 64 562
64 0 0 0 0 0 55 56 63 573
Square ROOK TABLE
E W N S
1 -1 8 -8
1 8 1 57 1
2 8 1 58 2
3 8 1 59 3
4 8 1 60 4
5 8 1 61 5
6 8 1 62 6
7 8 1 63 7
8 8 1 64 8
9 16 9 57 1
10 16 9 58 2
11 16 9 59 3
12 16 9 60 4
13 16 9 61 5
14 16 9 62 6
15 16 9 63 7
16 16 9 64 8
17 24 17 57 1
18 24 17 58 2
19 24 17 59 3
20 24 17 60 4
21 24 17 61 5
22 24 17 62 6
23 24 17 63 7
24 24 17 64 8
25 32 25 57 1
26 32 25 58 2
27 32 25 59 3
28 32 25 60 4
29 32 25 61 5
30 32 25 62 6
31 32 25 63 7
32 32 25 64 8
33 40 33 57 1
34 40 33 58 2
35 40 33 59 3
36 40 33 60 4
37 40 33 61 5
38 40 33 62 6
39 40 33 63 7
40 40 33 64 8
41 48 41 57 1
42 48 41 58 2
43 48 41 59 3
44 48 41 60 4
45 48 41 61 5
46 48 41 62 6
47 48 41 63 7
48 48 41 64 8
49 56 49 57 1
50 56 49 58 2
51 56 49 59 3
52 56 49 60 4
53 56 49 61 5
54 56 49 62 6
55 56 49 63 7
56 56 49 64 8
57 64 57 57 1
58 64 57 58 2
59 64 57 59 3
60 64 57 60 4
61 64 57 61 5
62 64 57 62 6
63 64 57 63 7
64 64 57 64 8
Square BISHOP TABLE
NE SW NW SE
9 -9 7 -7
1 64 1 1 1
2 56 2 9 2
3 48 3 17 3
4 40 4 25 4
5 32 5 33 5
6 24 6 41 6
7 16 7 49 7
8 8 8 57 8
9 63 9 9 2
10 64 1 17 3
11 56 2 25 4
12 48 3 33 5
13 40 4 41 6
14 32 5 49 7
15 24 6 57 8
16 16 7 58 16
17 62 17 17 3
18 63 9 25 4
19 64 1 33 5
20 56 2 41 6
21 48 3 49 7
22 40 4 57 8
23 32 5 58 16
24 24 6 59 24
25 61 25 25 4
26 62 17 33 5
27 63 9 41 6
28 64 1 49 7
29 56 2 57 8
30 48 3 58 16
31 40 4 59 24
32 32 5 60 32
33 60 33 33 5
34 61 25 41 6
35 62 17 49 7
36 63 9 57 8
37 64 1 58 16
38 56 2 59 24
39 48 3 60 32
40 40 4 61 40
41 59 41 41 6
42 60 33 49 7
43 61 25 57 8
44 62 17 58 16
45 63 9 59 24
46 64 1 60 32
47 56 2 61 40
48 48 3 62 48
49 58 49 49 7
50 59 41 57 8
51 60 33 58 16
52 61 25 59 24
53 62 17 60 32
54 63 9 61 40
55 64 1 62 48
56 56 2 63 56
57 57 57 57 8
58 58 49 58 16
59 59 41 59 24
60 60 33 60 32
61 61 25 61 40
62 62 17 62 48
63 63 9 63 56
64 64 1 64 64
Square WHITE PAWN TABLE
+8 +16 +7 +9
9 17 25 65 18
10 18 26 17 19
11 19 27 18 20
12 20 28 19 21
13 21 29 20 22
14 22 30 21 23
15 23 31 22 24
16 24 32 23 65
17 25 17 65 26
18 26 18 25 27
19 27 19 26 28
20 28 20 27 29
21 29 21 28 30
22 30 22 29 31
23 31 23 30 32
24 32 24 31 65
25 33 25 65 34
26 34 26 33 35
27 35 27 34 36
28 36 28 35 37
29 37 29 36 38
30 38 30 37 39
31 39 31 38 40
32 40 32 39 65
33 41 33 65 42
34 42 34 41 43
35 43 35 42 44
36 44 36 43 45
37 45 37 44 46
38 46 38 45 47
39 47 39 46 48
40 48 40 47 65
41 49 41 65 50
42 50 42 49 51
43 51 43 50 52
44 52 44 51 53
45 53 45 52 54
46 54 46 53 55
47 55 47 54 56
48 56 48 55 65
49 57 49 65 58
50 58 50 57 59
51 59 51 58 60
52 60 52 59 61
53 61 53 60 62
54 62 54 61 63
55 63 55 62 64
56 64 56 63 65
Square BLACK PAWN TABLE
+8 +16 +7 +9
9 1 9 2 65
10 2 10 3 1
11 3 11 4 2
12 4 12 5 3
13 5 13 6 4
14 6 14 7 5
15 7 15 8 6
16 8 16 65 7
17 9 17 10 65
18 10 18 11 9
19 11 19 12 10
20 12 20 13 11
21 13 21 14 12
22 14 22 15 13
23 15 23 16 14
24 16 24 65 15
25 17 25 18 65
26 18 26 19 17
27 19 27 20 18
28 20 28 21 19
29 21 29 22 20
30 22 30 23 21
31 23 31 24 22
32 24 32 65 23
33 25 33 26 65
34 26 34 27 25
35 27 35 28 26
36 28 36 29 27
37 29 37 30 28
38 30 38 31 29
39 31 39 32 30
40 32 40 65 31
41 33 41 34 65
42 34 42 35 33
43 35 43 36 34
44 36 44 37 35
45 37 45 38 36
46 38 46 39 37
47 39 47 40 38
48 40 48 65 39
49 41 33 42 65
50 42 34 43 41
51 43 35 44 42
52 44 36 45 43
53 45 37 46 44
54 46 38 47 45
55 47 39 48 46
56 48 40 65 47

3.2 DRAUGHTS

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.

32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 BLACK KING BLACK 29 22 15 8 24 6 31 13 31 13 24 15 6 15 22 8 6 13 6 15 8 13 22 15 8 22 13 6 15 8 22 31 24 15 8 22 8 24 22 31 24 15 8 24 31 22 15 8 A B C D

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:

Direction nw ne sw se nwd ned swd sed
10 15 14 6 7 19 17 1 3
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.

Position NORMAL
KINGS
CAPTURE
KINGS
BLACK
MEN
WHITE
MEN
BLACK
MEN
WHITE
MEN
nw ne sw se nwd ned swd sed
1 6 5 - - 10 - - -
2 7 6 - - 11 9 - -
3 8 7 - - 12 10 - -
4 - 8 - - - 11 - -
5 9 - - 1 14 - - -
6 10 9 1 2 15 13 - -
7 11 10 2 3 16 14 - -
8 12 11 3 4 - 15 - -
9 14 13 5 6 18 - - 2
10 15 14 6 7 19 17 1 3
11 16 15 7 8 20 18 2 4
12 - 16 8 - - 19 3 -
13 17 - - 9 22 - - 6
14 18 17 9 10 23 21 5 7
15 19 18 10 11 24 22 6 8
16 20 19 11 12 - 23 7 -
17 22 21 13 14 26 - - 10
18 23 22 14 15 27 25 9 11
19 24 23 15 16 28 26 10 12
20 - 24 16 - - 27 11 -
21 25 - - 17 30 - - 14
22 26 25 17 18 31 29 13 15
23 27 26 18 19 32 30 14 16
24 28 27 19 20 - 31 15 -
25 30 29 21 22 - - - 18
26 31 30 22 23 - - 17 19
27 32 31 23 24 - - 18 20
28 - 32 24 - - - 19 -
29 - - - 25 - - - 22
30 - - 25 26 - - 21 23
31 - - 26 27 - - 22 24
32 - - 27 28 - - 23 -
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:

nw ne sw se nwd ned swd sed
N +5 +4 -5 -4 +10 +8 -10 -8

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:

000000001000000001OOOOOOOO1OOOOOOOO1

WHITE BLACK 35 34 33 32 31 30 29 28 26 25 24 23 22 21 20 19 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1

Fig 3.9 Samuel's notation of the draughts board

WHITE BLACK (a) The opening position BLACK KING = WHITE KING = 0 123456789 36 (b) Machine representation of opening position 11111111 1111 1111 11111111 1111 1111 36 bit words BLACK MEN WHITE MEN EMPTY SQUARES

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 ne 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 ne. 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 nw 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.

3.3 KALAH

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.

p KALAH p1 p2 p3 p4 p5 p6 PITS P6 P5 P4 P3 P2 P1 P KALAH

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:

  1. 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.
  2. 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,

p KALAH p1 p2 p3 p4 p5 p6 PITS P6 P5 P4 P3 P2 P1 P KALAH has the following terminal positions: Order of Pits Played (1)1, 2, 1, 3 P3 P2 P1 KALAH (2)1, 2, 3 P3 P2 P1 KALAH (3)1, 3 P3 P2 P1 KALAH (4)2, 1 ( 1 in p6) P3 P2 P1 KALAH (5)2, 3 P3 P2 P1 KALAH (6)3 P3 P2 P1 KALAH

Continuation moves

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.

Stacks

The pits are scanned in the following order from right to left.

P6 P5 P4 P3 P2 P1 KALAH

Scanning order

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

"> P3 P2 P1 KALAH

Kalah 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
UNSTACK START STACK OUTPUT
S1 S2 S3 (Pits only)
321 ccc 320 302 032
S3 032 -** 320 302 030
003
S2 302 c-* 320 013 300
S2 013 -** 320 010
004
S1 320 cc- 301 031
S2 031 -*c 301 030 002
S2 030 -*- 301 001
S1 301 c-c 300 012
S2 012 -** 300 010
003
S1 300 c-- 011
S1 011 -*c 101 002
S1 010 -*- 001
S0 STOP 010

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
UNSTACK START STACK OUTPUT
S1 S2 S3 S4 S5 (Pits only)
321 ccc 032 302 320
S3 320 cc- 032 302 031 301
S4 301 c-c 032 302 031 012 300
S5 300 c-- 032 302 031 012 011
S5 011 -*c 032 302 031 012 010 002
S5 010 -*- 032 302 031 012 001
S4 012 -** 032 302 031 003
010
S3 031 -*c 032 302 030 002
S3 030 -*- 032 302 001
S2 302 c-* 032 013 300
S2 013 -** 032 004
010
S1 032 -** 003
S0 STOP 030

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

"> P6 P5 P4 P3 P2 P1 KALAH

Board test

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
1 1
2 2
3 11
4 56
5 232
6 912
7 3333
8 12149
9 42800
10 149117
N Unknown

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

P3 P2 P1 KALAH Play 1 P3 P2 P1 KALAH Play 1, 2, 1 P3 P2 P1 KALAH Play 1, 3, 1, 2, 1

Board test

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.

3.4 GO

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ABCDEFGHJKLMNOPQRST Two potential eyes The ladder attack

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.

Zobrist's program

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


DATA 1 -1 2 -1 1 -1 2 -1 represents the position 3 2 1 ABC

Fig. 3.13 Complete Fortran program to demonstrate Zobrist's algorithm

1 2 2 2 2 4 6 4 2 2 4 8 10 8 4 2 1 2 6 10 62 10 6 2 1 2 4 8 10 8 4 2 2 4 6 4 2 2 2 2 1

Fig. 3.14 Zobrist's finite difference algorithm operating on a black stone

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ABCDEFGHJKLMNOPQRST

Fig. 3.15 Final position segmented by human GO player

ABCDEFGHJKLMNOPQRST 1 52 10 3 3 54 60 4 54 10 8 6 5 5 7 10 59 12 57 4 49 57 56 50 57 16 56 50 64 12 11 9 9 10 62 16 63 61 10 57 50 50 50 50 57 50 42 57 14 62 12 11 12 14 63 14 11 5 58 50 50 66 58 58 50 58 65 14 14 13 62 13 64 64 14 59 3 6 56 46 58 66 50 42 50 66 57 64 14 13 14 63 15 13 10 8 62 10 0 62 50 49 65 50 50 42 50 56 7 55 16 64 63 11 7 9 1 5 57 49 15 15 56 42 50 50 50 52 40 56 65 16 59 2 0 3 13 57 58 64 63 16 48 42 58 56 8 56 16 65 56 4 3 6 11 63 58 49 15 15 55 16 48 49 16 63 66 57 50 50 54 7 11 13 15 65 42 57 56 35 56 15 49 56 16 49 49 57 65 12 9 64 57 57 50 50 64 15 7 63 14 57 54 49 49 14 15 64 60 11 57 42 50 58 64 14 63 63 15 14 60 0 46 65 14 63 15 11 60 66 50 42 56 14 12 11 14 64 63 7 47 43 57 14 64 64 60 5 49 50 49 16 62 12 12 13 63 15 12 55 8 64 13 13 4 11 3 56 58 42 56 15 62 12 62 16 54 6 14 63 64 14 14 64 60 9 14 56 50 56 14 12 12 14 56 50 44 56 14 14 64 64 64 10 8 62 7 44 8 62 13 13 56 50 50 42 65 13 12 63 13 11 7 7 11 12 56 63 13 12 53 50 57 65 50 54 11 10 10 9 7 4 4 6 8 9 9 8 6 2 56 11 11 56 2 5 6 5 5 3 2

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

Unsafe pattern

would be captured.

Summing up

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.

⇑ Top of page
© Chilton Computing and UKRI Science and Technology Facilities Council webmaster@chilton-computing.org.uk
Our thanks to UKRI Science and Technology Facilities Council for hosting this site