Many two-player games are games of 'complete information' in which both players know at every stage what the outcome of their alternative moves will be. Thus noughts-and-crosses is such a game, but bridge is not because each player’s cards are hidden from the other players. Games of complete information rely for their interest on their complexity; otherwise it would be possible for the players to work out from an early position in the game who has the forced win and how to achieve it.
In theory, one should be able to play any game of complete information perfectly. The strategy is simple: for every possible move at a given stage, examine every possible reply of your opponent's; for every reply look at every possible next move, and so on. In practice most games contain a prohibitively large number of possibilities, ruling out this strategy for even the fastest computers.
Many games of complete information have been 'solved'; in other words, a simple winning strategy has been found which, if known to one of the players, reduces the task of winning to a straightforward calculation. The following game, known as the 'Silver Dollar Game', is one such game, and it provides an excellent example of a game that a computer can play perfectly with a simple winning strategy.
The original Silver Dollar game is played with a number of coins which are moved by the two players along a line of squares. In his turn, a player must move one coin to the left along as many unoccupied squares as he wishes. For example, a possible move would be:
• • • < -- -- • •
The first player unable to move, when all the coins have reached the left-hand end of the line, loses.
In this version of the game the computer is one player; there are five coins identified with the letters A to E, and they move along a line of 30 dots. The starting position is chosen by the program at random, and the player moves a letter by typing the letter once for each place it is to be moved. The move is entered by typing 'return', and the computer will then make its move. The game continues in this way until one player has won.
For example, the game might start with the position:
A B • • • • • • C • • • • • D • • • • • • • • • E • • • • •
where the dots represent empty squares. The human player moves the 'D' to:
A B • • • • • • C D • • • • • • • • • • • • • • E • • • • •
The computer then moves the 'E':
A B • • • • • • C D • • • • • • E • • • • • • • • • • • • •
The human then moves the 'C':
A B C • • • • • • D • • • • • • E • • • • • • • • • • • • •
The game continues: computer:
A B C • • • • • • D E • • • • • • • • • • • • • • • • • • •
Human:
A B C D • • • • • • E • • • • • • • • • • • • • • • • • • •
Computer:
A B C D E • • • • • • • • • • • • • • • • • • • • • • • • •
and the computer wins!
The strategy used by the computer relies on the fact that there are certain 'safe’ positions in the game. No move by the opponent from one of these safe positions can achieve a safe position, so the computer simply waits until the player leaves an unsafe position, and thereafter always moves to safe positions until it has won.
To see if any position in the Silver Dollar Game is safe or unsafe, first determine the following three numbers:
Now split these numbers into their component powers of two. If there is an even number of each power of two, the position is safe; otherwise, it is unsafe.
As an example, take the following position:
• • • A • • • • B • • • • • C • • • D • • • • E 3 5 4 =1+2 =1+4 =4
Since there is only one '2', the position is unsafe. However, it can be made safe by moving the A two places to the left:
• A • • • • • • B • • • • • C • • • D • • • • E 1 5 4 =1 =1+4 =4
The final safe position is the winning position, when all the letters are moved to the left.
BBC Computer Version
5 REM ... Silver Dollar Game ... 10 DIM PP(5),TT(2) 20 PP(0)=-1: FOR N=l TO 5: PP(N)=PP(N-l)+ABSRND MOD 8+1: NEXT 25 P=R:CLS:PROCPRINT
Main loop; keep playing until someone has won.
30 REPEAT 35 IF FNWIN PRINT'"I WIN!":END 40 PROCMOVE 50 IF FNWIN PRINT'"YOU WIN!":END 60 PROCI:UNTIL 0
PROCI – Computer's move. Get Nim-sum of gaps, S.
If it is zero there is no winning move; otherwise look for move
that makes it zero.
1000 DEF PROCI S=0:FOR N=0 TO 2 1010 TT(N)=PP(2*N+1)-PP(2*N)-1:S=S EOR TT(N):NEXT 1020 IF S=0 GOTO 1100 1030 N=-1:REPEAT N=N+1: T-TT(N)-(S EOR TT(N)) 1040 UNTIL T>0:N=2*N+1 1050 GOTO 1200
Human has got a safe position, so can only make a random move.
1100 N=0:REPEAT N=N+1:UNTIL PP(N)-PP(N-1)>=2 1120 T=(PP(N)-PP(N-1)) DIV 2
Computer has decided its move – now do it.
1200 PROCURSOR 1250 PP(N)=PP(N)-T 1260 FOR J=1 TO T 1270 FOR K=1TO999:NEXT:PROCBUDGE:NEXT:PRINT CHR$(30);:ENDPROC
PROCPRINT – Print board with counters.
2000 DEF PROCPRINT
2005 N=0:PRINT CHR$(30)" ";:FOR J=l TO 5
2010 IF N<PP(J) REPEAT PRINT”.";:N=N+1:UNTIL N=PP(J)
2020 PRINT CHR$(J+ASC("@"));:N=N+1:NEXT:REPEAT PRINT".";:N=N+1:UNTIL N=30
2030 PRINT CHR$(30);:ENDPROC
PROCMOVE – Input human's move, and move selected counter. Bleep illegal move.
3000 DEF PROCMOVE
3010 Q=GET:IF Q<ASC("A")or Q>ASC("E")PRINT CHR$(7);: GOTO 3010
3050 N=Q-ASC("@")
3060 IF PP(N)-PP(N-1)<2 PRINT CHR$(7);:GOTO 3010
3070 PROCURSOR
3075 GOTO 3100
3080 Q=GET:IF Q=13 ENDPROC
3090 IF PP(N)-PP(N-l)<2 PRINT CHR$<7);:GOTO 3080
3100 PP(N)=PP(N)-1
3110 PROCBUDGE:GOTO 3080
FNWIN – Returns if game is won.
4000 DEF FNWIN W=1:FOR N=1TO5:IFPP(N)<>N-1 W=0 4100 NEXT:=W
PROCURSOR – Moves cursor to under piece N.
5000 DEF PROCURSOR 5010 PRINT CHR$(30);:FORJ=O TO PP(N):PRINT CHR$(9);: NEXT:ENDPROC
PROCBUDGE – Move piece N back one place.
6000 DEF PROCBUDGE
6010 PRINT".";CHR$(8);CHR$(8); CHR$(N+ASC("0")); CHR$(8);:ENDPROC
Variables:
J – Counter K - Delay counter N – Counter PP(0)..PP(5) – PP(0)=-1; PP(1) to PP(5) are the positions of the 5 counters Q - Character read by GET S - Nim sum S – Move needed to make Nim sum zero TT(0)..TT(2) – Sizes of Nim-heaps corresponding to a position W - Winner flag; W=l if game has ended
Atom Version
5 ... SILVER DOLLAR GAME ... 10 DIM PP5,TT2,Q0,R-1 20 PP0=-1; FOR N=l TO 5; PPN=PP(N-1)+ABSRND%8+1; NEXT
Assemble read-character routine at R.
25 P=R;PRINT$21;[JSR#FFE3;STAQ;RTS;] 28 PRINT$6$12;GOSUB p
Main loop; keep playing until someone has won.
30aGOSUB w 35 IFW PRINT'"I WIN!"';END 40 GOSUB m;GOSUB w 50 IFW PRINT'"YOU WIN!"';END 60 GOSUB i;GOTO a
i – Computer's move. Get Nim-sum of gaps, S.
If it is zero there is no winning move; otherwise look for move
that makes it zero.
1000iS=0;FOR N=0 TO 2 1010 TTN=PP(2*N+1)-PP(2*N)-1;S=S:TTN;NEXT 1020 IF S=0 GOTO r 1030 N=-1;DO N=N+1; T=TTN-(S:TTN) 1040 UNTIL T>0;N=2*N+1 1050 GOTO j
Human has got a safe position, so can only make a random move.
1100rN=0;DO N=N+1;UNTIL PPN-PP(N-1)>=2 1120 T=(PPN-PP(N-1))/2
Computer has decided its move – now do it.
l200jGOSUB c 1250 PPN=PPN-T 1260 FOR J=1 TO T 1270 FOR K=1TO999;NEXT;GOSUB b; NEXT; PRINT$30;RETURN
– Print board with counters.
2000pN=0;PRINT$30" ";FOR J=l TO 5 2010 IF N<PPJ DOPRINT".";N=N+1;UNTILN=PPJ 2020 PRINT$(J+CH"@");N=N+1;NEXT;DOPRINT”.";N=N+1; UNTILN=30 2030 PRINT$30;RETURN
m – Input human's move, and move selected counter. Bleep illegal move.
3000mLINKR;IF?Q<CH"A"OR?Q>CH"E" PRINT$7;GOTO m 3050 N=?Q-CH"@" 3060 IF PPN-PP(N-1)<2 PRINT$7;GOTO m 3070 GOSUB c 3075 GOTO v 3080qLINKR;IF?Q=13 RETURN 3090 IF PPN-PP(N-1)<2 PRINT$7;GOTO q 3100vPPN=PPN-1 3110 GOSUB b;GOTO q
w - Sets W to 1 if game is won.
4000wW=1;FOR N=1TO5;IFPPN<>N-1 W=0 4100NEXT;RETURN
c - Moves cursor to under piece N.
5000cPRINT$30;FORJ=0 TO PPN;PRINT$9;NEXT;RETURN
- Move piece N back one place.
6000bPRINT"."$8$8$(N+CH"@")$8;RETURN
Variables:
J - Counter K - Delay counter N - CounterPP(0)..PP(5) - PP(0)=-1; PP(1) to PP(5) are the positions of the 5 counters Q - Location containing character read by R R - Read-character routine; puts character in ?Q S - Nim sum T - Move needed to make Nim sum zero TT(0)..TT(2) - Sizes of Nim-heaps corresponding to a position W - Winner flag; W=l if game has ended