I.Kolingerova, 1998
This text was prepared on the basis of References. Technical processing of the manuscript was done by Mr.D.Juhas and Ms.H.Maskova.
Get source
The study of how to make computers do things at which, at the moment, people are better.
Problems contained in AI:
Intelligence requires knowledge (voluminous, hard to characterize accurately, constantly changing).
AI technique - a method that explores knowledge.
Problem solving
Three major steps to build a system to solve a particular problem:
Formal description
Example.: "Play chess" problem
The starting position - 8 * 8 array where each position contains a symbol standing for the appropriate piece in the official chess opening position. Goal - any board position in which the opponent does not have a legal move and his or her king is under attack. The legal moves - provide the way of getting from the initial state to a goal state; described as a set of rules
Each state of the state space corresponds to a legal position of the board.
Control strategy
Key questions when analyzing a problem:
Basic problem solving methods
The search - a traversal of a directed graph (sometimes tree), a node corresponds to a problem state, an arc to a relationship between the states.
A heuristic - a technique that improves the efficiency of a search process, possibly by sacrificing claims of completeness. (No longer the best answer is guaranteed, almost always a very good answer is found.)
FR - building a tree, next level by finding all the rules whose left sides match the previous level nodes, right sides are used to create new configuration.
BR - next level by finding all the rules whose right sides match the root (or previous level nodes), left sides generate a new level.
Examples:
2. Problem trees versus problem graphs
Waste of effort when the same node in the tree is generated more than once can be avoided at the price of additional bookkeeping if we use the graph instead.
3. Weak methods
a) Generate-and-test
b) Hill climbing
c) Breadth-first-search
d) Best-first-search
e) Problem reduction
f) Means-ends analysis
g) Constrain satisfaction
a)+b)+c)+d) methods for traversing OR graphs
a)+b) depth-first techniques
Each search - a traversal of a problem graph
a) Generate-and-test
Systematic | random generation of solutions (= so called British Museum algorithm - if a sufficient number of monkeys were placed in front of a set of typewrites and left alone long enough, then their implementation of this algorithm would generate all the books the museum contains) | practical middle ground
Example: program DENDRAL (Lindsay, 1980) - for infering the structure of organic componets
b) Hill climbing
A variant of the generate & test that uses feedback to decide in which direction to move next
Problems:
Bad: if the value of the heuristic function drops off suddenly as you move away from a solution
modification: simulated annealing
c) Breadth-first search
It is guaranteed to find a solution if one exists (the one with the shortest path from the goal, if some arcs are more expensive than others, this solution may not actually be the best).
Problems:
d) Best-first search: OR graphs
Example:
- heuristic function used for evaluation : f '= g + h'
- it records the best path to the node
g - measure of the cost of getting from the initial state to the current node ( >0, if not, cycles will improve)
h' - estimate of the additional cost of getting from the current node to a goal state (problem domain knowledge used)
If we don't care about path : g = 0. Control only by path : h' = 0. Random choice : g , h' = 0.
Quality of result depends on how perfect the estimate h' is .
e) Problem reduction
AND-OR graph
Example:
Example:
f) Means-ends analysis
g) Constraint satisfaction
We want to discover some problem state that satisfies a given set of constraints Can be solved using any of the the search techniques already discussed.
There were two reasons that games appeared to be a good domain in which to explore AI:
Contraexample: chess has branching factor aproximatelly 35. Each player might make 50 moves. Complete game tree has about 35100 positions. It's straightforward that a heuristic is necessary.
Essentially: generate & test, one extreme: generate the proposed solution, evaluate; the other extreme: individual moves
To improve the efficiency of a search-based, problem-solving program:
=> incorporate heuristic knowledge into both the generator and the tester
Example - Turing: for chess - black's pieces | white's pieces
- Samuel: for checkers - c1*pieceadvantage + c2*advancement + c3*centercontrol + ...
(ci - obtained over learning mechanism)
- useful in the analysis of games such as tic-tac-toe, chess and checkers, in which players alternate moves
Example: nim
Initially, there are n piles, each containing a number of idential tokens. Players alternate moves.A move - removing one or more tokens from any one pile. The player who removes the last token loses.
All possible move sequences are listed in a game tree.
The first player: box mark, the second player: circle mark
Each vertex - a particular position in the game
A path - a sequence of moves
A terminal vertex end of the game circled = 1st player lost; boxed = 2nd player lost
See an example with 2 piles, 3+2 tokens:
Analysis: begin with terminal vertices
If the game tree is so large that it is not feasible to reach a terminal vetex, we do not evaluate vertices below some specified level (n-level evaluation - levels 0 to n only). An evalutation function E assigns each possible game position P the value E(P) of the position to the first player, then the minimax procedure can be applied.
Ex.: tic-tac-toc + 2-level evaluation
E = NX-NO , NX - no of rows, columns or diagonals containing an X that X might complete (O, resp.)
Game tree for TTT to level 2 (symmetric positions omitted):
Ex.: We want to evaluate vertex A using a two-level evaluation
B = min (E,F,G) = 2 => A is at least 2 (<= A = max (B, C, D)) => x >= 2
this lower bound for A - an alpha value of A
the upper bound for A - a beta value of A
I = 1 => C is at most 1 (<= C=min(H,I,J))=>y<=1 => y will not affect the value of x
Alpha cutoff
Beta cutoff
It has been shown that for game trees in which every parent has n children and in which the terminal values are randomly ordered, for a given amount of time, the alpha-beta procedure permits an n-level evaluation to a depth 4/3 greater than the pure minimax procedure, which evaluates every vertex.
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 guaranted outcome value are called algorithms. In effect they convert a game into a problem.
This chapter discusses games which can be 'taught to' and played by a computer. It describes how the strategies are usually programmed, and illustrates the very different way in which humans remember and apply the strategies compared to mashines. The diference is often due to the machine having a perfect memory but having difficulties in recognizing patterns.
The crudest form: a single pile of tokens (matches). The players alternate in taking any number of matches from the pile, not exceeding half the total. The player who takes the last match loses
Example:
Generally: If a player can leave his opponent with a number from the series 2^(n-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. The numbers given are termed safe positions.
The game can be played in reverse, i.e. the player who picks up the last match is now the winner.
Exercise: derive winning stretegy and new safe positons for this reversed game.
More compicated form: more piles, any number of matches can be taken; whoever picks up the last match is the winner or, again in reverse, the looser.
Charles Bouton, Harward University, the turn of the centure: To determine whether a position in the game is safe or not, match the binaries as follows.
Suppose the position is 5 piles containing 1,3,5,7,11. These numbers can be written down in binary notation:
23 |
22 |
21 |
20 |
|
1 |
|
|
|
1 |
3 |
|
|
1 |
1 |
5 |
|
1 |
0 |
1 |
7 |
|
1 |
1 |
1 |
11 |
1 |
0 |
1 |
1 |
________________________________________________________ |
||||
XOR |
1 |
0 |
1 |
1 |
binary XOR, the result is not equal 0 - the position is unsafe (instable)
How to calculate a move which is legal and will produce a safe postion? According to Bouton, at least one such move exists.
Non-equivalence the result with each of the original numbers in turn. When a result is obtained which is less than the numer of that pile, then we have a legal move which is also a solution.
1 |
0001 |
XOR 1011 = |
1010 |
> |
0001 |
fails |
3 |
0011 |
XOR 1011 = |
1000 |
> |
0011 |
fails |
5 |
0101 |
XOR 1011 = |
1110 |
> |
0101 |
fails |
7 |
0111 |
XOR 1011 = |
1100 |
> |
0111 |
fails |
11 |
1011 |
XOR 1011 = |
0000 |
< |
1011 |
success |
Results of XOR show how many matches to leave in the given pile. All the 'fails' generate safe positions, too, but they are illegal moves (more should be left than is originally in the pile). Succes generates a safe position and is a legal move Sometimes, more correct moves are possible, e.g.
23 |
22 |
21 |
20 |
|||||
1 |
|
|
|
1 |
||||
3 |
|
|
1 |
1 |
||||
5 |
|
1 |
0 |
1 |
||||
7 |
|
1 |
1 |
1 |
||||
11 |
1 |
0 |
1 |
1 |
||||
13 |
1 |
1 |
0 |
1 |
||||
______________________________________________ |
||||||||
XOR |
0 |
1 |
1 |
0 |
1 |
0001 |
XOR 0110 = |
0111 |
> |
0001 |
fails |
3 |
0011 |
XOR 0110 = |
0101 |
> |
0011 |
fails |
5 |
0101 |
XOR 0110 = |
0011 |
< |
0101 |
success 1 |
7 |
0111 |
XOR 0110 = |
0001 |
< |
0111 |
success 2 |
11 |
1011 |
XOR 0110 = |
1101 |
> |
1011 |
fails |
11 |
1101 |
XOR 0110 = |
1011 |
< |
1101 |
success 3 |
=> 3 winning moves:
If presented with a safe position, the best thing is to take one from the largest pile and hope the opponent will make or mistake.
The reverse game: If the game reaches a point when only 1 pile has more than one match then make the move that ensures an odd number of one-match piles is left.
When a choice of winning strategy exists, a randomiser can be incorporated to add some variety.
A more difficult version of the game: players may take from any number of piles not exceeding an integer N. The same analysis for safe /unsafe positions still applies, except that non-equivalence is no longer binary but is now defined to result in zero when (N+1) 1's are added together => modulo (N+1) with no carry
E.H. Moore proved that it is still always possible to produce a safe position from an unsafe position for all values of N.
Another modification - Poker-nim: Players can also increase the number of matches in any pile by adding to it some of matches they acquired in earlier moves. Whoever can win a position in ordinary nim can win in poker-nim. A reply on reducing moves: just as in ordinary nim, on increasing moves: restore the heap to the previous size again.
The game is played on a board as shown below. The first player, Black, joins any 2 neighbouring circles of his colour by either horizontal or vertical time, it is then White's turn to join 2 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.
It has been proved that Black should always win. The simplest of winning strategies (for humans to remember) works for any size board and is as follows Mentally construct the diagonal AB, as shown in the figure.
Play the first move M1 as shown. Then apply the following responses:
1. If White (the opponent) joins one of his circles on the diagonal with a horisontal line, then reply thus:
2. If White joins points above the diagonal then reply thus:
3. If White joins points below the diagonal then reply thus:
To program a machine to play the game it is simplier to represent the board as shown in the figure:
* * * * *
o 37o38o39o40o41o
*33*34*35*36*
o28o29o30o31o32o
*24*25*26*27*
o19o20o221o22o23o
*15*16*17*18*
o10o11o12o13o14o
* 6 * 7 * 8 * 9*
o 1 o 2 o 3 o 4 o 5o
* * * * *
The machine plays 1 as an opening. From now on the opponents move is reported as the number he crosses when joining two white circles. The reply is looked up in the table below (OM = opponents 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 mechine 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!
For other board sizes:
for N=3: | for N = 4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
It is possible to write a program to generate such tables but a more elegant and slightly pattern recognizing algorithm is as follows:
Given OM (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 |
ifR < 2 then begin if R=0 then OM A:=OM+1 else A:=OM-1; end else if R-N <= 0 then A:=OM+N-1 else A:=OM-N+1;
Remark: One of the greatest problems in game playing programs is choosing or designing how the game is represented within the machine.
The majority of card games are of the imperfect information type - this means 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.
Card game called Guess It was invented and analysed by R. Isaacs.
The rules: Eleven cards are taken from the pack, usually all aces, kings and queens except one. 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 players. 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 aks 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 opponents turn to guess or ask.
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 opponents hand, and his chance of guessing the card will remain unchanged at 1 in 6.
The problems to solve
1-2 are both functions of the number of cards each player holds.
The optimal strategies
Do I bluff? | Is he bluffing? | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
* Opponent's number of cards
** My number of cards
To use the tables requires a random number generator in <1;100>.
Do I bluff?
Is he bluffing?
2 other situations in which we guess the card :
If this strategy is programmed and machine plays first, then it has a probability of winning 0.54 against an opponent using the same strategy. Against nonoptimal strategies the program has a greater edge, allowing it to win more often than not, even when playing second.
- ancestor of poker (3-card poker )
Rules:
3 cards are dealt from a full pack to each of the players. The hands are graded into the following classes (from best to worst):
Betting now takes place. A player either bets (because he has a good hand), 'throws in' (because he considers his hand too weak to risk more money), or bluffs (not to win with poor hand, but to prevent opponents knowing the stength of your hand from the amount you bet on it ).
Good strategy: to let oneself be discovered in a bluff rarely in the game, this will encourage people to 'go with you' when you have a really good hand later on.
Other possibility: sometimes to underbid a hand.
The first thing to do in a game involving the concept of best hand is to calculate the relative values of the hands - i.e., the probability of being dealt, in this case, a hand in one of the 7 listed casses (52 cards together = 4*13)
3 as the first card: p=4/52
p1=4/52*3/51*2/50=0.02% (once in approx. 5000 hands !)
p2=13*p1-p1=12*p1=0.22%
the first card: anything, e.g., 8:
p3=(2/51*2/50+2/51*1/50)*12/13=0.22%
16 possibilities - straight flush => p4=15*p3=3.26%
p5=52/52*12/51*11/50-p3=4.96%
PP* or P*P or *PP
p6=3/51*48/50+48/51*3/50+48/51*3/50=16.94%
p7=100-(p1+p2+p3+p4+ p5+p6)=74.4%
The highest card |
Number of ways to obtain it |
description |
Approx.probability |
cummulative probability |
5 |
2 |
5 high |
1 |
1 |
6 |
5 |
6 high |
1 |
2 |
7 |
9 |
7 high |
2 |
4 |
8 |
14 |
8 high |
4 |
8 |
9 |
20 |
9 high |
5 |
13 |
10 |
27 |
10 high |
7 |
20 |
J |
35 |
J high |
10 |
30 |
Q |
44 |
Q high |
12 |
42 |
K |
54 |
K high |
15 |
57 |
A |
64 |
A high |
18 |
75 |
|
|
pair |
17 |
92 |
|
|
flush |
5 |
97 |
|
|
straight |
3 |
100 |
straight flush |
negligible |
|||
|
|
prile |
negligible |
|
|
|
prile of 3's |
negligible |
|
From this table a hand can be evaluated.
The values of all the better than average hands (only the 2 most significant card are identified):
value[%] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
50 |
K,9 |
K,10 |
K,10 |
K,J |
K,J |
K,Q |
K,Q |
A,4 |
A,5 |
A,6 |
60 |
A,7 |
A,8 |
A,8 |
A,9 |
A,9 |
A,10 |
A,10 |
A,J |
A,J |
A,Q |
70 |
A,Q |
A,Q |
A,K |
A,K |
A,K |
2,2 |
2,2 |
3,3 |
4,4 |
5,5 |
80 |
6,6 |
6,6 |
7,7 |
8,8 |
9,9 |
10,10 |
10,10 |
J,J |
Q,Q |
K,K |
90 |
A,A |
A,A |
6 high* |
9 high* |
J high* |
K high* |
A high* |
10 high** |
Q high** |
A high** |
* flush
** straight
Bidding
is a function of at least 5 parameters, namely:
1. Value of hand: look up the value in the table.
2. The rules of bidding: The mechanics of hidding can introduce complications. The simplest rules: Each player antes one unit. The cards are dealt. A player, at his turn, can either stay in the game by putting an extra unit in the pot or he may drop out. When only 2 players are left the highest hand wins. If only 1 player bids he wins without showing his cards.
3. Number of players: The particular case of 4 players will be discussed
4. The order in which the players bid: a player has an advantage over all preceding players.
Algorithm for the first player, A:
Once every 4 hands, on average, A will be dealt a hand with a value of 75 or more. Assuming he does not bluff he will bet only on these hands (otherwise he will steadily lose his ante money).
Algorithm for B:
If A has already bid, then B will drop out unless he also has a hand of value 75 or more. If A has not bid, then he has to beat C and D, he should have a better hand than them once every three times that he finds himself in this position. If B has a hand of value 67 or more, then B will bid.
Algorithm for C:
If A bid first and C has value >= 75 or B bid first and C has value >= 67 or if C is first to bid and C has value >= 50 then C will bid.
Algorithm for D:
If A bid first and D value >=75 or B bid first and D value >=67 or C bid first and D value >=50 or D bid first and D value >=0.
It shows the advantage of D, especially in the case when A, B, C all pass. To overcome this advantage the deal is rotated each hand.
Generalizing to n players:
The first bidder is in position 1, the last in position n It is now the turn of player 'me' (1<=me<=n) to bid. Assume first bidder = 0 at the start of a round of bidding but is reset to point to the first player to bid (if any). The player will decide to bid or not on the result of 2 questions:
Not optimal, but gives some indication of the factors to be considered when deciding to bid.
Example: 100 players, 98 have passed, the 99th player has a very poor hand but by hazarding 2 units he stands to win 99 units.
if value of my hand * (what I can win/what I must bid) >=(1-1/(n+1-first_bidder))
then I bid
else I pass;
When more than 2 players are still bidding at the end of a round, i.e., there must be another round of bidding
Example: 4 players, everyone has bid in the first round. The first player must now assume that everybody has a hand of value 75 or ( the same as being the first player to bid in a game comprising 8 players).
if (value of my hand*(what I can win/what I must bid) >= (1 - 1/(number_of_people_still_in * round_number + 1 - first_bidder)))
then I bid
else I pass;
It is not an optimal algorithm: The calculation of best strategy is extremely difficult (even using the simple betting rules described here).
5. Bluffing
How to weight and combine the features influencing bidding?
(There are more features than those listed above which could also be relevant, e g., psychological, but are much more dificult to access.)
Instead of writing just one program, a group of people could each write a program to play what they themselves feel is a good strategy. A master program is then used to deal cards and control the bidding. Such a system can play millions of hands and then declare which individual program was the best.
The squeeze
Unless the program gives a value of 100 to some hands, e.g. a prile of 3's, it will always have a limit to how far it will continue to bid. This means that if 2 players form a coalition against it, then the program will be 'squeezed' out of the bidding and never win.
The best answer: to have a limit to the total bet size or play only with people who are not cooperating or to have a set amount of money at the start - a player who loses all his money drops out.
Advantages of computer
There are 10 classes of hands in 5 card poker. Players can attempt to improve their hands by changing up to 3 cards of the hand originally dealt to them. Jokers may by used - may be valued as any card in the full pack.
A rough solution to the value of a hand by writing a simulation program to produce a random poker hand, classifying the hand and then counting the number of times each class is generated .
The 10 classes are: |
percentage probability |
high card |
50 |
pair |
42 |
2 pairs |
5 |
3 of a kind |
2 |
full house |
- |
4 of a kind |
- |
straight (or run) |
- |
flush |
- |
straight run |
- |
royal flush |
- |
How to improve your hand?
Usually the 2 highest card are kept, but there are 3 subclasses of high card for which it is better to keep 4 cards. These are :
(true high card p ~ 0.3 = 0.5-0.04-0.04-0.12)
The decisions are made as follows:
All the other classes are more likely to deteriorate if cards were changed The results of changing cards under these conditions were: (except 4 of a kind - but changing one card here won't alter its classification)
percentage |
|
|
high card |
36 |
|
pair |
41 |
2 cards of the same value |
2 pairs |
14 |
2*2 cards of the same value |
3 of a kind |
8 |
3 cards of the same value |
straight |
1 |
5 cards in sequence |
flush |
- |
5 cards of the same suit |
full house |
- |
a pair + 3 of a kind |
4 of a kind |
- |
4 cards of the same value |
straight flush |
- |
5 cards of the same suit in sequence |
royal flush |
- |
5 cards of the same value |
Assuming there is no bidding before changing cards, then the above values can be used in the same way as the values of hands in brag.
The joker
One joker in a full pack makes a great deal of difference in evaluating a hand. It is important for a player to try to keep track of the joker and have a good idea whether the card is in play or not. Assuming the joker was dealt before cards were exchanged is equivalent to having the program deal only 4 genuine cards. Classify the result as before, but re-interpret the results, i.e. a high card is now a pair. Ignoring royal and straight glush (which are still negligible), the results were:
4 cards hands |
class interpretation |
% probability |
high card |
pair |
65 |
pair |
3 of a kind |
30 |
2 pairs |
full house |
1 |
3 of a kind |
4 of a kind |
1 |
straight |
straight |
2 |
flush |
flush |
1 |
4 of kind |
4 of a kind |
0 |
Applying the same rules for exchanging cards gives a better than normal chance of improvement to the player holding the joker. Results were:
Class |
% probability |
Pair |
43 |
3 of a kind |
49 |
Run |
2 |
Flush |
1 |
Full house |
3 |
4 of a kind |
2 |
Another interpretation - the description of the least hand which has even chance of being the best when playing against 2 to 5 players with or without the joker:
# of players |
2 |
3 |
4 |
5 |
normal |
pair 8's |
pair Q's |
2 pairs, 4 high |
2 pairs, 7 high |
joker |
three 4's |
three 8's |
tree 10's |
three Q's |
Advantages of the simulation method: hands tend to be sorted before being thrown in (pairs are put together and so on), it is possible to allow for this in the program, but practically impossible mathematically.
Rules: Assume 1 player. He first makes bet, the limits of which are decided by the house (let say, 1-100) (The range is important because the winning strategy is to vary the size of the bet depending on whether the situation is favourable or not.) The dealer then deals 2 cards to the player and 2 to himself, One of the dealers card is face up. The goal of the game is to obtain a total which is greater than the dealer's but not greater than 21 The player can value an ace as either 1 or 11, J, Q, and K count as 10 and all other cards have their face value.
Example:
J,Q = 20 |
"hard" hand - it has a unique value |
A,5 = 6 or 16 |
"soft" hand - the ace allows for 2 totals |
A,10 = 21 (a 'natural' or 'blackjack') |
If the dealer shows an ace or a ten, he may himself have a natural. To save time he then checks his hole card and declares the hand if this is the case. If the dealer does not have a natural the player now looks at his cards. He may either stand or ask for extra cards. These are dealt one at a time and face up. If a card makes the player's total exceed 21 then he has 'bust' and loses his bet. If he does eventually stand then it is the dealer's turn to play.
The dealer is restricted to a simple strategy: he turns over his hole card and if his total is 17 or more he will stand, otherwise he must draw cards until the condition is met or he 'busts' (in which case the player has won his bet). If neither player nor dealer bust then the higher hand wins an amount equal to the player's bet. In the event of a draw no money changes hands.
There are 2 other features in the game:
The basic strategy
Example: A player has been dealt a hard total of 16 and the dealer is showing an ace (but does not have a natural)
Solution: simulation,
Extracts of the computers output for the player's gain by drawing rather than standing for all hard totals > 17.
All positive gains are situations where the player should draw and vice versa.
The same method was used to calculate the players strategy for 'soft' totals, i.e., one of the cards is an ace which is counted as 11, but the total is still <= 21. It recommends drawing to higher soft totals than hard totals (18).
This strategy reduce the casino's advantage to about 0.5%.
Another experiment: computer played the game with decks from which had been removed, in turn, all the aces, all the twos and so on
Cards removed from deck
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
A |
1.8 |
2.1 |
2.6 |
3.6 |
2.4 |
2.1 |
0.4 |
-0.4 |
-1.6 |
-2.42 |
Players advantage (with corresponding best strategy)
When there are high cards missing (9,10,A) the casino has the advantage, when low cards are missing then the player has the advantage.
Consider the particular case of the 5's missing. Assume only one player is in the game, used cards from previous hands being put aside. Then about 1 hand in 10 will be played from a deck which has no fives (this is equivalent to the original deck having no fives) - the player has a better than 3% advantage with best strategy play.
Assume the player takes 100 hands per hour. There will be about 10 situations when no fives remain and his advantage is about 3. If he bets 10 units in these situations his net gain will be
10*0.03*10 = 3 units
The rest of the time (90%) he plays the basic strategy, essentially waiting. His disadvantage is 0.5%. If he bets 1 unit in these unfavourable situations then his net loss will be
90*0.005*1=0.45 units =>
More powerfull system: The Ten Count System (Thorp):
The player's resulting advantage with varying numbers of Tens.
Number of Tens
0 |
4 |
8 |
12 |
16 |
20 |
24 |
28 |
32 |
36 |
-1.6 |
-2.1 |
-3.1 |
-1.9 |
-0.5 |
1.9 |
3.5 |
5.1 |
6.5 |
7.7 |
Player's advantage
Ratio of Others/Tens
infin. |
9 |
4.5 |
3 |
2.25 |
1.8 |
1.5 |
1.3 |
1.1 |
1 |
36/0 |
36/4 |
36/8 |
36/12 |
36/16 |
36/20 |
36/24 |
36/28 |
36/32 |
36/36 |
Ex.:20 cards left to be dealt, the player (by counting) knows that there are 10 Tens still to be dealt => 36/36 = Others/Tens => The player has an advantage of 7.7%.
3 problems to overcome before the Ten Count System can be used successfully:
Suggested scheme
Other/Tens Ratio |
Bet (in units) |
>2 |
1 (minimum) |
2 - 1.75 |
2 |
1.75 - 1.65 |
4 |
<1.65 |
5 (maximum) |
This system was used by many people and the casinos began to lose heavily. The Tropicana Hotel in Las Vegas accepted a match against a computer using methods similar to those described above. The machine won $360 in one hour. The casinos were so alarmed that the rules were changed to stop the system players winning.
The friendly game
Strategy for the player:
Always bet minimum stakes and wait for his turn to win the deal. Because the delaer shows no cards the player's best strategy is to stand on hard totals of 17 of more and soft totals of 18 or more. (This is the dealer's strategy also.) The player should split aces and eights and double down on 10 or 11 only.
A winning strategy:
to throw in stacked hands which increase the possibility of a natural being dealt, e.g. if 4 people are playing and one player has 5 cards from his last hand (probably 'bust'). Arrange them A, x, x, x, 10 before throwing them in. This is called a 'set up'. The more cards a player holds the easier it is to make a set up. The best strategy in this type of play is to stand on hard totals of 17 o more, always draw to a soft hand unless one already has the card for a set up, split, tens, and eights and double down on 11 only.
Internal chessboard representation + generator of moves + evaluation of moves
Data representation
Board can be coded with numbers 1-64. The 2 sides are placed on separate boards (to simplify the problem of detecting captures).
Example :
It is only necessary to know the colour (and therefore direction) of a pawn, the colour of a piece is immaterial.
Program may be driven by 6 tables which show all the possibilities of moves for each kind of piece in each square. The possible moves are stored seqentially in a list.
Tables for particular pieces (N,E,W,S - directions)
King: x-9(SW),-8(S),-7(SE),-1(W),+1(E),+7(NW),+8(N),+9(NE)
Knight: max. 8 moves
Bishop: x-9 (SW),-7(SE),+7 (NW),+9(NE) etc.
Rook: x-8(S),-1(W),+1(E),+8(N) etc.
Queen: a rook + a bishop
Pawn moves (the most complicated): white pawn up, black one down
2 cheks are made before accepting a move. Firstly, no man is allowed to move to a square which contains a friendly man. Secondly, if the man can move to a square containig the opponent's king, then the listing of further moves is pointless and will be terminated. (This device is really used to check the legality of the opponent's previous move.)
Comment on rules:
No move can be carried out to a square occupied by a friendly man. No man (except the knight) can skip either friendly of opponent's pieces.) For a king and a knight, only terminal squares are tested, for others also all the path:
if my man in [i] then goto new direction
if my opponent's man in [i] then
if this man is king then exit else this move is legal, for the next one goto new direction
For a white pawn, the tables deal only with moves of types (1), (2) and (3). Queening (4) is dealt with by the program. En Passant captures are omitted.
All the moves generated in this way are stored.
Example:
List of moves of white for position in the previous figure.
Man |
No |
Position |
List of moves |
N |
11 |
62 |
56,47,45,52 |
B |
10 |
57 |
50,43,36 |
B |
9 |
51 |
60,42,58,44,37 |
P |
8 |
39 |
47,46 |
R |
7 |
33 |
34,35,36,41,49,25,17,9,1 |
P |
6 |
32 |
40 |
N |
4 |
18 |
35,28,3,1 |
Q |
3 |
14 |
15,16,13,6,23,5,21,28,7 |
K |
1 |
10 |
1,2,3,9,11,17,19 |
(2 pawns - number 5 and 2 - have no moves and are omitted)
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 take the king.
After making a move, the depth is increased and the opponent's replies are generated for the new board configurations. This tests if the move just made is legal.
Value of particular pieces (approximately):
B or N = |
3 or 3.5 pawns |
R = |
(1B or 1N) and 2 pawns |
Q = |
2R or 3B or 3N |
Real value depends on the efficiency of pieces in the given position.
Notes to heuristics
mobility ratio = number of our possible moves/number of opponent's possible moves
In fact, it is a wrong reason for taking a particular move but it works.
The experiment was done: games of 10 great masters were taken. In the 10 games the masters were faced with 336 positions. All these positions were presented to a program which sorted the moves for each of them into order on the basis of 2 requests:
The result was that if the top 16 moves of the list were kept then for over 95% of the cases the move chosen by the master was in that list.
The weakness of the approach: it usually failed to include moves which were not captures, i.e. the important turning point moves. Thus the majority of moves it failed to include were those which did not have an immediate effect on the game, only becoming more understandable as to why they were made by the master at a much later stage, e.g. minor pieces strategically placed to prevent the opponent developing.
A further trick: to place the men so that the more powerful (i.e. more mobile) pieces will have their moves generated first for alpha-beta-pruning.
Notes to evaluation:
Usually, it is prefered to capture a piece to improving the position (but material is not everything)
Another viewpoint: To play in a human way: masters remember patterns from the chessboard. They have a vocabulary of 50 000 'chess words' - pieces constallation. (It is approximately a natural language vocabulary of an educated person). They also know to operate with functional relations. They are unable to explain structure of their knowledge to a layman => impossibility to formalize chess knowledge of chess masters (Or they don't want to describe?) => Attempts exist to introduce an 'intelligent' strategy - thinking over only several top variants.
Example: Bolvinnik's Pioneer - this program has not been ever completed, after 25 years, even most devoted fans dropped away.
Historical heuristic: If some move is found best very often, then the probability that this move is good in the current position is high => Keep historical value of moves (but up to some limit).
Aspiration-alpha-beta: During search, an approximate evaluation of the best move is vailable. It can be used before the search as: alpha = approx. val. - pawn, beta = approx. val. + pawn. If the value found is outside this window, the search must be repeated with more opened window.
Quiscence search: The model 'compute into some depth and evaluate a list of moves' is nice and simple but not that much practical, in dramatical positions in which our pieces are attacked by out opponent, there is probably no sence to think over importance of pairs of pawns => positional evaluation mirrors realistically only in tactically calm postions. Therefore, most programs do quiescence search - when searching quiescence, only tactical (attacking, en passant and to change directing) positions are investigated.
Permanent brain: a professional program computes also in time reserved to the opponent, it is supposed that the opponents move will be in the main variant.
Hashing tables: records from previous levels of search (position evaluation, best move out and a distance to the horizon are stored in a table). If program finds the resulting postion in a table, it can stop computing this variant => acceleration (in real life, about 2x).
Sometimes hashing tables can have collision - a position is then evaluated wrongly and program picks a mysterious, difficult to understand move.
Nearly all modern programs use a method called prescan - a position is investigated in detail before search starts. According to results of this analysis, parts of evaluation function are changed. The same positon is then evaluated differently in different starting positions. (Extreme behaviour of this kind show Fritz and Chess Genius programs. They are so strongly dependent on the starting position that they have to erase their hashing tables after each move, in the other case their old records would be in conflict with evaluation function.)
(In Nimzo 2 the evaluation function is changed also during search according to a particular position, while the starting position analysis has only a small influence. Therefore, hashing tables are kept from move to move.
Null-move: selective method - computing in some branches is cut before the maximum level is reached. Null- move is a pseudomove - it is tried in any position as the 1-st one => higher effectivity, it is able to search 1-2 levels more than without this technique as imbalanced positions (with clear dominance of one side) are cut and dismissed (up to 99%). But: probability of missing something grows (but it is overpowered by extra levels of search). Fundamental disadvantage: a move which is at least as good as null-move exists and we are giving an advantage to our opponent in this way
Board representation
Typical computer style of game
4.2 Draughts (U.S. Checkers)
The pieces are relatively simple. 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.
Example of board coding:
|
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 |
|
The first thing to do is examine the immediately diagonal squares (for 10: 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 seperate test from the 'capture' moves. If, however, an enemy piece is detected, then a second test is made to see if it can be captured (e.g., if an enemy piece is in square 15 then square 19 most be empty for a capture to be made. Once a capture has been found then the further recording of normal moves is ignored. A capture may lead to further captures => recursive function.
Another possibility of coding:
|
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 |
|
Advantage: all the moves can be calculated by adding or subtracting constants.
Thus for square N: x+5,+4,-5,-4,+10,+8,-10,-8
Making a solitaire jump:
Jumps are like captures in Draughts, but they never take place diagonally, but only vertically or horizontaly. One move - can be a series of consecutive jumps made with one peg.
Central solitair: a peg in every hole except the centre.
Goal: by taking a series of these jumping moves to reduce the situation to a single peg in the central hole. It is said to have been played for the first time by a French nobleman who played it on the stone tiles of his prison cell.
Labelling the places:
|
|
a |
b |
c |
|
|
|
|
d |
e |
f |
|
|
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
x |
P |
O |
N |
M |
L |
K |
J |
I |
H |
G |
|
|
F |
E |
D |
|
|
|
|
C |
B |
A |
|
|
Notation: St - a jump from S to t (if we don't need to indicate the direction, S)
Example: LJHljh can be written as L5 if there is no ambiguity
Dudeney's elegant 19-move solution: eJO2fmh2apFMH2APc2g2C2G2p6o
Bergholt's 18-move solution (not quite as symmetrical): elcPDGJm2igL5CpA2M2a3d5o
L5 - ambiguous, but the intended jump is the same as depicted before
d5 - also ambigous, but either interpretation brings success
Beasley: the proof that a solution in fewer than 18 moves is impossible
Packages and purges
It is nice to know the effect of a whole collection of moves before you make them - use instant packages, when a pakage is used to clear all the pegs from a region, we call it a purge.
Example: 3-purge
A parcel of packages:
A solution for central solitaire with packages:
Other one - peg reversal problems: start with only one empty space and finish with only one peg in the same place Example:
More difficult example (needs to be combined with extra moves:
Two-peg reversal problems - start with just 2 spaces on the board and end with just 2 pegs in those place
Another type of problem
We start with just one empty space and declare that some particular peg is to be the finalist (last on the board)
Example: b - the finalist d - the initial hole
There is an obvious Rule of Two - the peg can only jump an even number of places in either direction. But there is a much more interesting Rule of Three. One of the consequences is that if we start with a single space and finish with a single peg, then we can move in steps of 3 from the initial space to that of the finalist.
Both rules together can lead to surprises. See how they point to the unique finishing place H in both figures. Now that we know that H is the only place permitted by both rules, the problem is a lot easier. See a neatly packaged solution:
The position after the first 2 moves The position before the last 2 moves
We prepared the 3-jump move 9, which puls the finalist in his place and our second jump was to clear a space for this. But after we made this second jump most of the pegs parcelled themselves up naturally. The only apparent exception was the peg starting just right of the finalist, and the best way of clearing this seemed to be to use it to provide the final jump.
For other problems, a similar procedure can be recommended: plan the last few moves of your solution and let the first few be used to smooth the way for these and leave the remaining pegs in tidy packages. Remember that the catalyst for the very last purge must be among the pegs in your planned finale.
Explanation of the Rule of Three (Some pegs are more equal than others)
Let's have 4 pegs r, s, t, u,.
a) st = r
b) st = u
c) tu = s
=> r = u : Places 3 apart in any line are considered equal.
b)+c) => st = u, tu - s => sttu = us => tt = 1: Two pegs in the same place cancel.
(Catalysts do precisely this - they remove 2 pegs which are delivered to the same place by the other moves of a purge.)
Any set of pegs that can be purged cancel.
Example: (c) stu = ss = 1 => 3 adjacent pegs in line cancel (3-purge)
r = u, ru = uu = 1, ss =1 = rst => s = rt => 2 pegs at distance 3 cancel (2-purge)
This algebra implies that the Solitair board can be cut down to size, for since places 3 apart are algebraically equal, every place is equal to one of the nine in the middle of the board, e.g., a=p. Now we can use our most recent rule to express each of these nine in terms of the 4 corner ones i, k, I, K.
j = ik, P = Ik
p = iK, J = IK
x = jJ = ikIK
Since equal pegs cancel, every Solitair position is algebraically equal to one of the 16 combinations of the places i, k, I, K.
Any position on the board is algebraically equal to the complementary position which has empty spaces replacing pegs and pegs replacing empty spaces.
But it does not mean that each such a position is solvable. Some positions are impossible to solve:
Swap the Hares and Tortoises: HHH_TTT
Permitted moves: each creature may move ahead one square (to an empty square) or jump over an opposing creature (onto and empty square). More moves of the same kind of animal in series is allowed.
Solution: Make the moves in this order (jumps are bold):
HTTHHHTTTHHHTTH
If you move only 1 kind of animal for as long as you can before moving the other kind, you will soon see how to swap 57 Hares with 57 Tortoises.
Other problems wiht the same coins are:
HHHTTT HTHTHT
Fig. 1 Fig. 2
Solution: (T is bold) Start form 012345, move 01 to 67, 56 to 89 and 23 to 56
Solution: Start form 012345, move 01 to 76, 23 to 98 and 56 to 65
Delannoy: With n pairs of coins can always be solved in just n moves.
Tait: It requires n+1 moves if n > 4
Solution: one of the simplest examples of a psychological block. You notice that 4 coins are in position (Fig. 6), so you are reluctant either to move one of them (Fig. 7) or to waste time by replacing it (Fig. 8), but that's the only way to get to Fig.9 in 3 moves. There's a four-move version in which your start with a triangle.
Remark: How to infuriate your friends.
It is an old puzzle to arrange the numbers from 1 to n2 in an aray so that all the rows and columns and both the diagonals have the same sum which turns out to be 1/2*n(n2+1). The only 3x3 magic square, often called the Lo-Shu, was discovered several dynasties ago by the Chinese:
6 |
1 |
8 |
7 |
5 |
3 |
2 |
9 |
4 |
In 1693 de Bessy had worked out the 880 magic squares of order 4.
How to find them: it is handy to subtract 1 from all the numbers, because the numbers 0 to 15 are closed under XOR in binary numbers. With this convention the magic sum is 30 instead of 34. The square is called perfect if any number from 0 to 15 can be xored to its entires and still a magic square is obtained. If only 1/2 of these additons are possible, the square is called 1/2-perfect and so on. Since complementing in 15 is always possible (and also adding 0), every square is at least 1/8-perfect.
There are essentialy 3 ways how to start:
0 |
1 |
2 |
3 |
0 |
1 |
4 |
5 |
0 |
2 |
4 |
6 |
||
4 |
5 |
6 |
7 |
2 |
3 |
6 |
7 |
1 |
3 |
5 |
7 |
||
8 |
9 |
10 |
11 |
8 |
9 |
12 |
13 |
8 |
10 |
12 |
14 |
||
12 |
13 |
14 |
15 |
10 |
11 |
14 |
15 |
9 |
11 |
13 |
15 |
Then you can freely permute the rows and columns in any of these tables. Take any table obtained in this way, say
15 |
11 |
14 |
10 |
13 |
9 |
12 |
8 |
7 |
3 |
6 |
2 |
5 |
1 |
4 |
0 |
Apply the interchanges as follows (the so-called Quaquaversal Quadrimagifier):
swap [1,2] with [3,4], [1,3] with [4,2], [1,4] with [2,3], [2,1] with [4,3], [2,4] with [3,1], [3,2] with [4,1]
And you get the magic square:
15 |
2 |
1 |
12 |
16 |
3 |
2 |
13 |
|
4 |
9 |
10 |
7 |
[+1] |
5 |
10 |
11 |
8 |
8 |
5 |
6 |
11 |
9 |
6 |
7 |
12 |
|
3 |
14 |
13 |
0 |
4 |
15 |
14 |
1 |
By applying the Quaquaversal Quadrimagifier to the other forms of tables we get 432 essentially different magic squares. They are perfect.
Example:
15 |
2 |
1 |
12 |
-> |
1111 |
0010 |
0001 |
1100 |
4 |
9 |
10 |
7 |
0100 |
1001 |
1010 |
0111 |
|
8 |
5 |
6 |
11 |
1000 |
0101 |
0110 |
1011 |
|
3 |
14 |
13 |
0 |
0011 |
1110 |
1101 |
0000 |
XOR 0111 -> |
1000 |
0101 |
0110 |
1010 |
-> |
8 |
5 |
6 |
11 |
still a magical square |
0011 |
1110 |
1101 |
0000 |
3 |
14 |
13 |
0 |
|||
1111 |
0010 |
0001 |
1100 |
15 |
2 |
1 |
12 |
|||
0100 |
1001 |
1010 |
0111 |
4 |
9 |
10 |
7 |
The squares can be also classified by the disposition of complementary pairs. E.g., our particular square is central diagonal. There are more types, another interesting one is central horizontal (CH) or central vertical (CV): If we apply on central horizontal square the flip operation (swap [2,1] and [3,1], [2m4] and [3,4]), we will get 96 more CH squares. All are perfect. No more perfect squares exist.
Solution: backtracking (depth search,depth-first search)
Board is represented with an array, at the beginning set to all 0's. Now moves of the knight are generated and marked in the array by their order number (1, 2, ...) from the beginning of the game. If there is no other move possible, but still some 0's remained, we return - backtrack - and change the numbers of moves to zeros again. When the goal state is reached, all the array is filled with numbers and these numbers define the solution. For some board sizes, there is no solution.
To be considered: for a new attempt to go ahead, another way should be taken to avoid looping in the same blind alley. Corners should be prefered (and edges of the board) to bill them ASAP (=> some weights of squares in the neighbourhood of the active cell). Squares surrounded by filled squares should be prefered, too.
Example: 6x6
(backtracked moves are bold, the point where to try another direction is bold + underlined)
18 |
3 |
16 |
20 |
5 |
Backtracked |
18 |
3 |
16 |
20 |
5 |
Backtracked |
||
15 |
19 |
4 |
27 |
--> |
15 |
19 |
4 |
--> |
|||||
2 |
17 |
14 |
6 |
21 |
1 move |
2 |
17 |
14 |
27 |
6 |
21 |
3 moves |
|
13 |
24 |
9 |
26 |
13 |
30 |
24 |
9 |
26 |
|||||
1 |
11 |
22 |
7 |
1 |
28 |
11 |
22 |
7 |
|||||
12 |
23 |
8 |
25 |
10 |
29 |
12 |
23 |
8 |
25 |
10 |
18 |
3 |
16 |
29 |
20 |
5 |
Backtracked |
18 |
3 |
16 |
20 |
5 |
Backtracked |
|
15 |
30 |
19 |
4 |
28 |
--> |
15 |
28 |
19 |
4 |
--> |
|||
2 |
17 |
14 |
27 |
6 |
21 |
7 moves |
2 |
17 |
14 |
27 |
6 |
21 |
3 moves |
13 |
31 |
24 |
9 |
26 |
13 |
29 |
24 |
9 |
|
||||
32 |
1 |
11 |
22 |
7 |
30 |
1 |
26 |
11 |
22 |
7 |
|||
12 |
23 |
8 |
25 |
10 |
12 |
23 |
8 |
25 |
10 |
18 |
3 |
16 |
20 |
5 |
Backtracked |
18 |
3 |
16 |
20 |
5 |
Backtracked |
||
15 |
19 |
4 |
29 |
--> |
15 |
19 |
4 |
--> |
|||||
2 |
17 |
14 |
27 |
6 |
21 |
2 moves |
2 |
17 |
14 |
27 |
6 |
21 |
3 moves |
13 |
24 |
9 |
28 |
13 |
28 |
24 |
9 |
||||||
1 |
26 |
11 |
22 |
7 |
1 |
26 |
11 |
22 |
7 |
||||
12 |
23 |
8 |
25 |
10 |
29 |
12 |
23 |
8 |
25 |
10 |
18 |
3 |
16 |
31 |
20 |
5 |
Backtracked |
18 |
3 |
16 |
27 |
20 |
5 |
15 |
32 |
19 |
4 |
30 |
--> |
15 |
26 |
19 |
4 |
35 |
28 |
|
2 |
17 |
14 |
29 |
6 |
21 |
9 moves |
2 |
17 |
14 |
29 |
6 |
21 |
13 |
28 |
33 |
24 |
9 |
some more trials, then it is found then 25 and 24 must be also backtracked |
13 |
30 |
25 |
36 |
9 |
34 |
|
34 |
1 |
26 |
11 |
22 |
7 |
24 |
1 |
32 |
11 |
22 |
7 |
|
27 |
12 |
23 |
8 |
25 |
10 |
31 |
12 |
23 |
8 |
33 |
10 |
Input: a list of occupied squares, coordinates of a start and a goal square.
Solution: wave algorithm (breadth-first search)
(Application: search of the shortest route between electronical components - printed connections)
Board is represented by an integer array. Occupied squares are marked, e.g., -2, empty -1 and the starting position of a king 0. Now numbers -1 are gradually replaced by positive numbers which determine the shortest path of king from his initial position to the current place. Numbers are found by a principle of a wave starting at the initial position and proceeding until the ending position.
When the final positon is reached, the number written to its square shows the length of the path. The path is found by following the numbers in descending order back to the start. More paths may exist.
If the goal position is not reached yet and in spite of this fact, no other move is possible, then the problem is unsolvable (and the goal positon unreachable from the start position)
Example:
5 |
5 |
5 |
5 |
5 |
5 |
5 |
|
5 |
4 |
-2 |
4 |
-2 |
-2 |
-2 |
4 |
5 |
4 |
3 |
3 |
3 |
3 |
3 |
3 |
5 |
-2 |
-2 |
2 |
2 |
2 |
2 |
3 |
5 |
4 |
3 |
2 |
1 |
1 |
-2 |
2 |
5 |
4 |
3 |
2 |
1 |
0 |
1 |
2 |
5 |
-2 |
3 |
2 |
-2 |
1 |
1 |
2 |
5 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
(bold - the initial and goal positions)
The monks are ceaselessly engaged in transferring 64 gold discs from the first to the last of three pegs according to the conditions that only one disc may be moved at a time, and no discs may by placed above a smaller one.
Fig.a) shows the initial position in a smaller version of the puzzle and fig. b) shows the position 13 moves later.
To find out where you would be after m moves, expand m in binary, and then, according as the total number of discs is:
replace a digit
1 by the ternary no. 1 for even or 2 for odd number of discs,
2 - 21 or 12,
4 - 122 or 211,
8 - 2111 or 1222,
16 - 12222 or 21111,
32 - 211111 or 122222,
64 - 1222222 or 2111111 etc.
These ternary numbers, when added mod 3 without carrying, show what peg each disc should be on. For 13 moves and 7-disc tower, since 7 is odd and 1+4+8=13, we find the ternary numbers 2 + 211 + 1222 = 0001102 showing that disc 1 should be on peg 2, discs 4 and 8 on peg 1 and the rest on peg 0 (see the figure). The Tower of Hanoi puzzle and the table which usually accompanies it were invented by Messieurs Claus (Edouard Lucas) and De Parville in 1883 and 1884.