Many many games which at first sight appear difficult have been solved. This means that for all legal positions of the game, it is possible to calculate the optimal move and ultimately arrive at the solution sought. Such decision procedures (which have a guaranteed outcome value) are called algorithms. In effect they convert a game into a problem.
The chess algorithm (see Chapter 3) illustrates the alien (table look-up) methods used by a machine to obtain a list of legal moves. The same translation difficulty always arises when a machine has to be programmed to implement an algorithm.
Many people can play the game of noughts and crosses perfectly, but are quite incapable of describing how they make their decisions. Some people have attempted to describe in words and diagrams what they think they are doing, but such attempts are almost impossible to translate into terms a machine can use.
To illustrate the sloppy language human algorithm, consider the puzzle of the knight's tour of the board. The problem is for the knight to visit the 64 squares of a chess board in 64 moves. A human being, conversant with chess and the problem, has about a 50% chance of succeeding if he is programmed as follows: Starting in a corner move anticlockwise round the board, always moving to unvisited squares as close to the edge as possible. At move (13-14) reverse to a clockwise direction etc. A successful result is shown in Fig. 1.1.
Whether a human succeeds or fails when he attempts to follow such an algorithm is irrelevant. The point is that no machine (as yet) can even begin to implement an algorithm expressed in such a fashion.
This chapter discusses four games which can be taught to and played by a computer. It describes how the strategies are usually programmed, and illustrates the very different ways in which humans remember and apply the strategies compared with machines. The difference is often due to the machine having a perfect memory but having difficulty in recognising patterns.
The crudest form of the game is a single pile of matches. The rules are simple: the players alternate in taking any number of matches from the pile, not exceeding half the total. For example, if there are 17 matches, the player can remove any number from 1 to 8. Whoever takes the last match loses.
An astute player soon realises that if he can leave his opponent with a number from the series 2n-1, i.e. 31,15,7,3,1, then no matter what the reply is he can always adjust the contents of the pile to the next number down in the series. This being so, and as 1 is the final number in the series, the strategy must win. The numbers given are termed safe positions.
Human players remember the numbers, and by identification and subtraction can calculate the correct move. Computers operate in binary and implement the algorithm differently, thus: consider the number 47, which is 25 + 23 + 22 + 21 + 20. The number appears to the machine thus:
| 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 | 1 |
The machine finds the most significant 1 bit, in this case bit 5. It then removes this bit and adds 1 to the number left, thus:
1* 0 1 1 1 1
1+
-----------------------------
1 0 0 0 0 = 16
-----------------------------
The machine has calculated that removing 16 matches is the correct move. If the position is unsafe then the answer cannot exceed half the original number; unfortunately if the machine is presented with a safe position then the answer will be illegal. The machine therefore checks for this case and, when it occurs, only removes 1 match.
The game can be played in reverse, i.e. the player who picks up the last match is now the winner. The strategy is easily obtained by calculating the new series of safe positions (2 is safe, then 5, and so on), and deriving the formula.
In a more complicated form of the game there are a number of piles and each player can now take as many as he wishes from any pile. Whoever picks up the last match is the winner or, again in reverse, the loser.
This game was demonstrated at the 1951 Festival of Britain on a machine called NIMROD. It attracted thousands of people many of whom did not believe the machine could be beaten In fact any person who knows the algorithm and has the choice of who starts could beat the machine. Practically every school with a computer has a program which plays a version of this game. At the turn of the century, this Nim was analysed by Charles Bouton of Harvard University (1). He proved that there existed a simple strategy which, once understood, enabled anyone to play a perfect game. As in the simple game already described Bouton showed that every position could be designated safe or unsafe. Any move from a safe position created an unsafe position and it was always possible to change an unsafe position to a safe one. To determine whether a position in the game is safe or not can be done by matching the binaries as follows.
Suppose the position is five piles containing 1,3,5,7 and 11 matches. These five numbers can be written down in binary notation, thus:
1 0 0 0 1
3 0 0 1 1
5 0 1 0 1
7 0 1 1 1
11 1 0 1 1 neqv 2
----------------------
1 0 1 1
---------------------
The columns are now added up but no carry operation is done i.e. 1 + 1 = O. This is called binary non-equivalence. The result in the example is 1011 and, because it is not zero, the position is unsafe.
Having discovered the position to be unsafe, the problem now is how to calculate a move which is legal and will produce a safe position. According to Bouton at least one such move exists and may be obtained by using the principle of non-equivalence again. Take the result of non-equivalencing all the original numbers together (1011). Non-equivalence this number with each of the five original numbers in turn. When a result is obtained which is less than the number of that pile, then we have a legal move which is also a solution. In this example:
1 0001 neqv 1011 = 1010 > 0001 FAILS 3 0011 neqv 1011 = 1000 > 0011 FAILS 5 0101 neqv 1011 = 1110 > 0101 FAILS 7 0111 neqv 1011 = 1100 > 0111 FAILS 11 1011 neqv 1011 = 0000 < 1011 SUCCESS
So the only answer is to leave zero matches in the fifth pile, i.e. remove the whole pile. (N.B. All the FAILS are illegal moves, but do generate safe positions.)
In the above example there is only one correct move. However, consider the unsafe position below:
1 0 0 0 1
3 0 0 1 1
5 0 1 0 1
7 0 1 1 1
11 1 0 1 1
13 1 1 0 1 neqv 2
----------------------
0 1 1 0
---------------------
In this case there are three moves possible to attain a safe position, thus:
1 0001 neqv 0110 = 0111 > 0001 FAILS 3 0011 neqv 0110 = 0101 > 0011 FAILS 5 0101 neqv 0110 = 0011 < 0101 SUCCESS 7 0111 neqv 0110 = 0001 < 0111 SUCCESS 11 1011 neqv 0110 = 1101 > 1011 FAILS 13 1101 neqv 0110 = 1011 < 1101 SUCCESS
Therefore the three winning moves are to (1) leave 3 in the third pile, (2) leave 1 in the fourth pile, or (3) leave 11 in the sixth pile. Incidentally, if presented with a safe position, the best thing to do is to take one from the largest pile and hope the opponent will make a mistake.
Only a slight change is required to play the reverse game. This is a more pleasing game because, if a safe position can be obtained, then ultimately the opponent is forced to pick up a solitary match at the end. The change is that when the game reaches a point when only one pile has more than one match (such a position is inevitable), then make the move that ensures an odd number of one-match piles is left. For example, if the position is 1,1,1,7, then take all 7 matches; if the position is 1,1,1,1,7, then take 6 matches from the last pile.
The above description is roughly the way a number of computers have been programmed to play the game. A randomiser can also be incorporated for use when a choice of winning moves exists, thus adding some variety. The game is dependent on the binary system and programs exist which can play up to 100 piles with up to 109 matches in each pile. Such calculation are beyond humans in a reasonable time, so here we have an example of a machine which can beat its creator.
A more difficult version of the game has the same rules except that players may take from any number of piles not exceeding an agreed integer N. The game just discussed was for N = 1. Surprisingly the same analysis for safe/unsafe positions still applies, except that non-equivalence is no longer binary (neqv 2) but is now defined to result in zero when (N + 1) 1's are added together. Put another way, the addition is modulo (N + 1) with no carry. E. H. Moore (2) proved that it was still always possible to produce a safe position from an unsafe position for all values of N.
The problems of finding which pile(s) to decrement to what value(s) has never been solved elegantly. The author submits the following (incomplete) solution.
Consider the position 1,3,5,7,11 again, but this time a player can remove matches from up to two piles (N = 2). First do the ternary non-equivalence:
1 0 0 0 1
3 0 0 1 1
5 0 1 0 1
7 0 1 1 1
11 1 0 1 1 neqv 3
----------------------
1 2 0 2
---------------------
The result is not zero and, hence, is unsafe. The presence of a figure 2 in the result means that two piles must be altered. But which two? And changed to what values?
Consider first the two largest numbers, 7 and 11. A ternary non-equivalence of these integers is
7 0 1 1 1
11 1 0 1 1 neqv 3
----------------------
1 1 2 2
---------------------
This result (1122) and the previous result for all the piles (1202) give four cross reference entries into Table 1 in Fig. 1.2. The result is two bits (either 0 or 1) which build up two new binary numbers. These, if they are less than the numbers they are replacing, are a solution, thus:
(7,11) neqv 3 1 1 2 2
(Whole position) neqv 3 1 2 0 2
-------------
0 1 1 0 = 6 < 7 SUCCESS
0 1 1 0 = 6 < 11 SUCCESS
-------------
a b c d
Therefore a solution is to leave 6 matches each in place of the two largest piles.
Fig. 1.2 also gives the tables to obtain a limited number of solutions for the cases N = 3, N = 4, i.e. players may take from up to 3 or 4 piles respectively. The calculation of similar tables for N > 4 is not difficult.
It is, however, possible that altering the two largest piles will not give a valid solution. To show this in a simple way, go back to the case of N = 1 for a position 3, 4, 5. Fig. 1.2 implies that the table for N = 1 is
0 1
------------
0 | 0 1 |
1 | 1 0 |
------------
First neqv 2 the position, thus:
3 0 1 1
4 1 0 0
5 1 0 1 neqv 2
----------------------
0 1 0
---------------------
According to the (N = 1) table altering the largest pile (5) results in (111) = 7, which is an impossible answer. Therefore, for the case N = 2, one must again discard illegal (incrementing) solutions, and permutate the piles in pairs until a legal solution is reached.
The above strategy is correct for all positions where the number of piles exceeds N. When the number of piles is equal to or less than N, then the machine must recognise this and remove all the matches (or leave one, depending on how a win is defined).
| 0 | 1 | 2 | |
| 0 | 0 0 |
0 1 |
1 1 |
|---|---|---|---|
| 1 | 1 1 |
0 0 |
0 1 |
| 2 | 0 1 |
1 1 |
0 0 |
| 0 | 1 | 2 | 3 | |
| 0 | 0 0 0 |
0 0 1 |
0 1 1 |
1 1 1 |
|---|---|---|---|---|
| 1 | 1 1 1 |
0 0 0 |
0 0 1 |
0 1 1 |
| 2 | 0 1 1 |
1 1 1 |
0 0 0 |
0 0 1 |
| 3 | 0 0 1 |
0 1 1 |
1 1 1 |
0 0 0 |
| 0 | 1 | 2 | 3 | 4 | |
| 0 | 0 0 0 0 |
0 0 0 1 |
0 0 1 1 |
0 1 1 1 |
1 1 1 1 |
|---|---|---|---|---|---|
| 1 | 1 1 1 1 |
0 0 0 0 |
0 0 0 1 |
0 0 1 1 |
0 1 1 1 |
| 2 | 0 1 1 1 |
1 1 1 1 |
0 0 0 0 |
0 0 0 1 |
0 0 1 1 |
| 3 | 0 0 1 1 |
0 1 1 1 |
1 1 1 1 |
0 0 0 0 |
0 0 0 1 |
| 4 | 0 0 0 1 |
0 0 1 1 |
0 1 1 1 |
1 1 1 1 |
0 0 0 0 |
There are many games related to Nim. They always depend on the binary system in their simpler forms, and are useful in introducing students to the basic operations of a computer. One of them, Grundy's game, is described in Chapter 6.
The game is played on a board as shown in Fig. 1.3. The first player, Black, joins any two neighbouring circles of his colour by either a horizontal or vertical line; it is then White's turn to join two circles of his colour. Play alternates until one of the players succeeds in forming an unbroken chain from one of his BASE circles to a GOAL circle. Note that it is impossible for this game to be drawn.
An interesting feature of the game is that it is possible to demonstrate that there must be a winning strategy for the first play, The argument is as follows:
Having established that Black should always win, Oliver Gross of Rand Corporation analysed the game and discovered a set of winning strategies. The simplest of these strategies (for humans to remember) works for any size board and is as follows. Mentally construct the diagonal AB, as shown in Fig. 1.4.
Play the first move (M1) as shown. Then apply the following responses:
To program a machine to play the game it is simpler to represent the board as shown in Fig. 1.5.
The machine plays 1 as an opening. From now on the opponent's move is reported as the number he crosses when joining two white circles. The reply is looked up in the table below (OM = opponent's move, A = answer).
OM A OM A OM A OM A 2 - 6 12 - 16 22 - 26 32 - 36 3 - 7 13 - 17 23 - 27 33 - 37 4 - 8 14 - 18 24 - 28 34 - 38 5 - 9 15 - 19 25 - 29 35 - 39 6 - 2 16 - 12 26 - 22 36 - 32 7 - 3 17 - 13 27 - 23 37 - 33 8 - 4 18 - 14 28 - 24 38 - 34 9 - 5 19 - 15 29 - 25 39 - 35 10 - 11 20 - 21 30 - 31 40 - 41 11 - 10 21 - 20 31 - 30 41 - 40
The machine plays well against a good player and badly against a poor player. A major fault in the program is that it is unable to detect when it has won!
The table given is relevant only to the board size (= 5) so far illustrated. It is therefore necessary, unlike the human algorithm, to inform the computer what size board it has to play on before the game begins. For a size 2 board, it would first have to generate the following table (I = increment):
For a size 3 board:
And, finally, the N = 4 table should reveal the structure (cf. with table for N = 5 already given).
TABLE FOR N = 4 OM I A OM I A OM I A 2 + 3 = 5 10 + 3 = 13 18 + 3 = 21 3 + 3 = 6 11 + 3 = 14 19 + 3 = 22 4 + 3 = 7 12 + 3 = 15 20 + 3 = 23 5 - 3 = 2 13 - 3 = 10 21 - 3 = 18 6 - 3 = 3 14 - 3 = 11 22 - 3 = 19 7 - 3 = 4 15 - 3 = 12 23 - 3 = 20 8 + 1 = 9 16 + 1 = 17 24 + 1 = 25 9 - 1 = 8 17 - 1 = 16 25 - 1 = 24
It is possible to write a program to generate such tables, but a more elegant (and slightly pattern recognising) algorithm is follows.
Given OM (the opponent's move),
OM R OM R OM R 2 2 10 2 18 2 3 3 11 3 19 3 4 4 12 4 20 4 5 5 13 5 21 5 6 6 14 6 22 6 7 7 15 7 23 7 8 0 16 0 24 0 9 1 17 1 25 1
A := if R < 2 then
begin
if R = 0 then OM + 1 else OM - 1;
end
else
if R-N ≤ 0 then OM + N - 1 else OM - N + 1;
Humans would not calculate the reply in the manner above; such calculations are forced on the machine because it required a notation for the board. One of the greatest problems in game playing programs is choosing or designing how the game is represented within the machine. Many researchers are working towards programs that would accept the human algorithm for this and other problems, rather than the numerical algorithm described (see Chapter 7 'Future Developments').
This trivial game has been completely analysed, and a variety of machines designed to play an unbeatable game. Such machines will always draw against correct play; hence the game has an outcome value of O.
Fig. 1.6 shows the correct responses to each of the three opening moves. The corner opening is the strongest because the opponent has only one correct response, the centre. If he plays incorrectly in one of the blank cells it is possible for the first player to construct a trap where a row can be obtained on the next move in two ways, only one of which can be stopped.
Programs which play the unbeatable game have a complete set of templates, with which they can recognise all possible situations and look up the correct response. Such templates are used for many positional type games (see Chapter 3.4, GO). A very crude estimate is that each cell can be X, 0, or blank. Therefore there are 39 possible templates = 19,683.
Ignoring the impossible positions (i.e. positions already won, positions with more than 5 X's or 0's), and positions which an redundant reflections and rotations, then the complete game tree reduces to about 500 templates, still a large number for such an apparently trivial game.
The author designed a simpler machine to play a defensive version of the game. The opponent always played first and was told it was possible to beat the machine. Because the strategy of the machine was unknown it was only beaten on rare occasions. A description of the strategy follows, and the reader is invited to find the loophole in the defence.
The incomplete defence algorithm
The nine cells of the board are numbered thus:
The opponent makes his first move 0. The machine's reply is to play 9 if possible, otherwise to play in a corner, i.e. 1, 3, 5 or 7. A randomiser is incorporated in the machine which allows it to choose between equally good plays.
The three possible positions at this point in the game (ignoring rotations) are
The opponent now makes his second move, thus:
The machine then plays in the cell containing the highest number. (If it has a choice it uses the randomiser.) Calculation of the numbers requires the tables given in Fig. 1.7. If the opponent does not have the centre cell the first table is used; otherwise it uses the second table. The blank entries are zero.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 3 | 1 | 1 | 1 | 3 | |||
|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 3 | 1 | |||||
| 3 | 1 | 3 | 3 | 1 | 1 | |||
| 4 | 3 | 3 | 1 | |||||
| 5 | 1 | 1 | 3 | 3 | 1 | |||
| 6 | 1 | 3 | 3 | |||||
| 7 | 1 | 1 | 1 | 3 | 3 | |||
| 8 | 3 | 1 | 3 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 3 | 4 | 3 | |||||
|---|---|---|---|---|---|---|---|---|
| 2 | 3 | |||||||
| 3 | 3 | 3 | 4 | |||||
| 4 | 3 | |||||||
| 5 | 4 | 3 | 3 | |||||
| 6 | 3 | |||||||
| 7 | 3 | 4 | 3 | |||||
| 8 | 3 |
For example, if he has cells 5 and 6 then the program adds the rows 5 and 6 together, thus:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 5 | 1 | 1 | 3 | 3 | 1 | |||
|---|---|---|---|---|---|---|---|---|
| 6 | 1 | 3 | 3 | |||||
| 1 | 1 | 1 | 3 | 3 | 3 | 4 |
It ignores the results for occupied squares, and hence the indicated play is in cell 7. This configuration is equivalent to (a)(i), and is a forced reply. If the opponent has played in the centre then his second play gives entry into table 2 and the program takes the indicated reply directly. The result is a simple blocking which usually results in a draw.
The loophole in the machine's play is the position (a)(iii). The machine will play on average once in three times thus:
and the opponent's winning move is shown. This configuration can be reached in many ways and occasionally the machine will lose. Human psychology is such that people will play this machine longer than the usual unbeatable machine.
When the machine has first move, an even simpler algorithm which can never lose was described by D. Michie (3). Again the machine plays M and the opponent plays 0. For every M on the board enter 6, for every empty cell enter 1, and for every 0 enter -4. For example,
Calculate the eight products of three numbers in a line, thus:
Sum for each empty square all the interesting scores.
The correct play is in the square of largest score, in this case the centre. N.B. This machine always takes the centre at its first move.
A weakness of both these algorithms is that they are defensive; they do not always take advantage of the opponent making a losing move. Despite their simplicity for a computer, a human would not use them.
Michie's menace
To demonstrate the way humans probably treat the problem, Donald Michie (4) designed a machine which could learn how to play an unbeatable opening game. Although primarily intended as a model of learning, the machine, in a sense, pruned itself to become an algorithm.
The machine consisted of 300 match boxes and was called MENACE (Match box Educable Noughts And Crosses Engine). It played the odd moves, i.e. 1st, 3rd, 5th, and 7th. Each box had a drawing of a possible position the machine could be faced with, i.e. a template, and inside were a number of glass beads of various colours. The number of colours in each box was the same as the number of possible responses the machine could make to the position represented on the box. The number of beads of each colour depended on the number of the move, thus:
1st move - 4 beads of 3 colours 3rd move - 3 beads of each colour 5th move - 2 beads of each colour 7th move - 1 bead of each colour
Inside each box was a wedge thus:
To make a move the position is identified. The relevant box is then selected, shaken, and opened. A bead will be in the apical position, and the move denoted by the colour of that bead is made. If the machine wins it is rewarded (reinforced) by adding 3 beads of the apical colour to each box used in the game. A draw is rewarded by 1 bead. A loss is punished by removing the offending bead from each box.
The result is a model of learning by reward and punishment. In its first series with Michie it would only make corner openings after the 17th game. After the 20th game it could always draw against correct play, but could still be trapped by unsound variations. At the end of 220 games the machine could cope with all variations and always win against unsound play. It had been supplied with a complete game tree (set of templates), and itself learnt the correct responses. Note that MENACE did not discover how to draw from a side or centre opening.
Another variation
Nine playing cards with values from 1 to 9 are dealt out, face up, on the table. Players alternate in picking a card. The first player to obtain 3 cards that add up to 15 is the winner.
This game is actually noughts and crosses in disguise. If the eight possible lines of a win are listed and interlocked into the magic square, thus (any row of three numbers sums to 15):
2 9 4
7 5 3
6 1 8
then MENACE could easily play this game and, because MENACE opens in a corner, any reply other than taking the 5 card would lose to the machine.
This illustrates one great advantage of machine algorithms compared with human ones, i.e. they are usually more flexible when faced with variations. In the above example the machine can make the conversion far more easily than human pattern recognition could.
So far all the games considered have been of the perfect information type: both players had a full view of the position and also saw the sequence of moves which resulted in that position. The majority of card games are of the imperfect information type. This does not mean that no algorithm exists for playing such games, but that it is impossible to guarantee a definite result of win or draw for a particular game. What an algorithm must now offer is that, over a series of games, a positive outcome value should be achieved.
A card game was invented and analysed by R. Isaacs (5). The game is called Guess It, and the rules are as follows. Eleven cards are taken from the pack; usually all the aces, kings, and queens except the queen of spades. The eleven cards are shuffled. One card is chosen, its identity unknown to both players, and put aside. To win the game a player must correctly name this card. The remaining cards are dealt, five to each player. The players now take turns. At each turn a player may either guess the hidden card (winning if he is correct, losing if he is incorrect), or ask the opponent if he has a certain card in his hand. If the opponent has the card demanded he must respond truthfully and place it, face up, in front of him. If the opponent does not have the card he replies NO. No card can be asked for twice. Irrespective of the answer it is then the opponent's turn to guess or ask.
These simple rules give rise to a number of complications. It is amusing to watch a novice at the game when he is first asked for a card he does not have, for he will usually ask for the rules to be repeated. The necessary element of bluff in the game is then revealed. If a player never bluffs then, whenever he asks for a card the opponent does not have, the opponent will know that the requested card must be the hidden one, so he calls and wins. Conversely, if a player always bluffs he will learn nothing of his opponent's hand, and his chance of guessing the card will remain unchanged at 1 in 6. Therefore, to play the game well, a strategy of occasional bluffing must be followed.
A further aspect now arises. The opponent is assumed to bluff on occasion and has asked for a card to which the answer is NO. At the beginning of the game the odds are that he is bluffing, but he may have been lucky enough to have named the card. We can terminate the game by believing he is lucky; if our suspicion is correct we win. Otherwise we must assume he has that card and is bluffing, and so we take our turn. On his next turn, if he does not guess the hidden card, we know that he was bluffing when he asked for the previous card. Thus successfully ignoring a bluff gives further information about the opponent's hand.
Isaacs showed that it was possible to program a machine to play this game. The problems are
Isaacs' analysis of the game showed that the problem of (a) when to bluff, and (b) when to ignore the opponent's possible bluff, were both functions of the number of cards each player held.
The optimal strategies are summarised in Fig. 1.8. To use the tables requires a random number generator in the range 1 to 100. A hand machine or book of random numbers can be used by a person who wishes to play the strategies himself.
The first table shows the percentage of times one should bluff. Assume we have three cards and the opponent has four. The number 23 is picked up. A random number is now generated. If the random number is less than 23 then we bluff, i.e. we ask for a card in our hand not previously mentioned. Otherwise we ask genuinely, i.e. a card the opponent may have.
The second table works in the same way, and is used whenever we have just responded NO. In this case, if we have three cards and the opponent has four, then the number 26 is picked up. If the generated random number is less than 26, then we guess that the card the opponent just asked for is the hidden card, i.e. we assume he was not bluffing. If the number is greater than 26, then the next step depends on how many cards the opponent has. If he has one, then we have assumed he bluffed with it, therefore we guess the remaining unknown card. If he has more than one card, then we must bluff or not bluff in our turn (using the first table), but remembering that we have assumed the opponent to have the card he just asked for and therefore his hand is one less than is actually is.
| Table 1: DO I BLUFF? | ||||||
|---|---|---|---|---|---|---|
| My number of cards | ||||||
| 1 | 2 | 3 | 4 | 5 | ||
| Opponents number of cards |
1 | 33 | 50 | 50 | 56 | 58 |
| 2 | 26 | 33 | 37 | 40 | 43 | |
| 3 | 19 | 26 | 29 | 31 | 33 | |
| 4 | 16 | 21 | 23 | 25 | 27 | |
| 5 | 12 | 17 | 19 | 21 | 22 | |
| Table 2: IS HE BLUFFING? | ||||||
|---|---|---|---|---|---|---|
| My number of cards | ||||||
| 1 | 2 | 3 | 4 | 5 | ||
| Opponents number of cards |
1 | 50 | 50 | 41 | 38 | 33 |
| 2 | 33 | 33 | 28 | 25 | 22 | |
| 3 | 38 | 32 | 27 | 24 | 21 | |
| 4 | 32 | 30 | 26 | 23 | 21 | |
| 5 | 32 | 29 | 25 | 23 | 21 | |
There are two other situations in which we guess the card. The first when we know the card, i.e. we didn't bluff and he replied NO. The second, is when we have no cards; this is a forced guess from a number of alternatives and must be done because if we do not the opponent will win at his next turn.
A program to play this algorithm is not difficult. The actual conversation with the opponent would be the biggest programming task. If written in Algol it could take the form
begin
I start;
BLUFF: if do I bluff [his number of cards, my number of cards]
< random number then
begin
I will bluff therefore: pick one of my cards;
I have one less card;
genuine query: = false
end else
begin
I will be honest and: make a genuine request;
he has one less card;
genuine query: = true
end;
wait for reply;
if reply = false and genuine query then goto
I know what it is;
wait for request;
if I have requested card then
begin
curses: say ('YES');
I have one less card;
if I have no cards then guess
end
else
if is he bluffing [his number of cards, my number of cards]
< random number then begin say ('THATS THE CARD'); stop end
else begin
I assume he has that card;
he has one less card;
if he has no cards then guess;
end;
goto BLUFF;
I know what it is: wait for request;
say ('SORRY, THE LAST CARD I ASKED FOR IS THE CARD')
end.
The program is not complete: declarations are missing, and many procedures ('pick one of my cards', 'make a genuine request', 'guess', etc.) are not included. It is intended to show the advantages of using a high level language such as Algol. Not only can the program run on any machine with an Algol compiler (ignoring the I/O problem), but also the algorithm is very readable and can be easily modified. Many research projects in game playing have been concerned with designing languages which are even closer to the English language.
If the program is realised and the machine plays first, then it has a probability of winning of 0.54 against an opponent using the same strategy. Against non-optimal strategies the program has a greater edge, allowing it to win more often than not, even when playing second.