Problem solving and computer games

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

Contens

  1. Problem solving techniques, game playing
  2. Algorithms
  3. 2.1 Nim
    2.2 Bridget
    2.3 Isaacs' bluffer

  4. Card games
  5. 3.1 Brag
    3.2 Poker
    3.3 Black Jack

  6. Board games
  7. 4.1 Chess
    4.2 Draughts (U.S. Checkers)

  8. Solitairs and Puzzles
  9. 5.1 Peg Solitair
    5.2 Hares and Tortoises (and other coin problems)
    5.3 Magic squares
    5.4 Chessboard problems
    5.5 The tower of Hanoi

  10. References

  11. Appendix I - The Implications of Kasparov Vs. Deep Blue

  12. Appendix II - Checkers - game & strategy


1. Problem solving techniques, game playing

Artificial intelligence (AI)

The study of how to make computers do things at which, at the moment, people are better.

Problems contained in AI:

  1. game playing
  2. theorem proving
  3. perception (vision & speech)
  4. natural language understanding
  5. expert problem solving = problem solving in specialized domains (medical diagnosis, chemical analysis, symbolic math)

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:

  1. Define the problem precisely - What the initial situations will be, what final situations constitute acceptable solutions to the problem
  2. Analyze the problem - a few very important features can have an immense impact on the appropriateness of various possible techniques for solving the problem.
  3. Choose the best technique(s) and apply it (them) to the particular problem.

Formal description

  1. Define a state space - contains all the possible configurations of the relevant objects
  2. Specify initial and goal states
  3. Specify a set of rules that describe the actions available

 

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.)

 

1. Forward versus backward reasoning

How to choose:

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

    1. Generate a possible solution (a point in the problem space or a path from a start state)
    2. Test to see if this is actually a solution by comparing the chosen point or endpoint of the chosen path to the set of acceptable goal states
    3. If a solution has been found, quit. Otherwise, return to step 1.
    4. 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

    1. Generate a possible solution (and test see a)1,2 )
    2. From this solution, apply some number of rules to generate a new set of proposed solutions
    3. For each element of the set, do the following:
  1. Take the best element found above and use it as the next proposed solution (a move through the problem space in the direction that appears to be leading the most quickly toward a goal)
  2. Go back to step 2.

Problems:

    1. A local maximum (solution: backtrack, try another direction)
    2. A plateau (solution: a big jump or several small jumps)
    3. A ridge (solution: move in several directions at once)

Bad: if the value of the heuristic function drops off suddenly as you move away from a solution

c) Breadth-first search

d) Best-first search: OR graphs

  1. At each step we select the most promising of the nodes we have generated so far by applying an appropriate heuristic function to each of them.
  2. Then we expand the chosen node by using the rules to generate its successors.
  3. If one of them is a solution, we can quit, else add those new nodes to the set of nodes generated so far.

e) Problem reduction

g) Constraint satisfaction

Game playing

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)

Game trees

- useful in the analysis of games such as tic-tac-toe, chess and checkers, in which players alternate moves

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):

 

Alpha-beta pruning

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.


2. Algoritms

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.

 

2.1 Nim

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:

  1. leave 3 in the third pile
  2. leave 1 in the fourth pile
  3. leave 11 in the sixth pile

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.

 

2.2 Bridget

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:

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

OM

A

I

2

4

+2

3

5

+2

4

2

-2

5

3

-2

6

7

+1

7

6

-1

8

10

+2

9

11

+2

10

8

+2

11

9

-2

12

13

+1

13

12

-1

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 recognizing algorithm is as follows:

Algorithm

Given OM (Opponent's move)

  1. Divide by 2N and look at the remander R, e.g. for the case of N=4 we get:

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

Remark: One of the greatest problems in game playing programs is choosing or designing how the game is represented within the machine.

 

2.3 Isaac's bluffer

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. Do I ask genuinely or bluff?
  2. When I answer NO do I accept the card he named or assume he has it and is bluffing?
  3. Do I guess the card?

1-2 are both functions of the number of cards each player holds.

The optimal strategies

Do I bluff?Is he bluffing?

*\**

1

2

3

4

5

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

*\**

1

2

3

4

5

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

* Opponent's number of cards
** My number of cards

To use the tables requires a random number generator in <1;100>.


Do I bluff?

    1. Generate a random number r .
    2. If r < table1[his number of cards, my number of cards] then bluff (=ask for a card in your hand not previously mentioned) else ask genuinely (=ask for a card the opponent my have)

Is he bluffing?

    1. Generate a random number r .
    2. If r < table2[his number of cards, my number of cards] then no else yes (if he has 1 card, assume that he bluffed with it, guess the remaining unknown card; if he has 1 card, use table 1 again, but assume that your opponent has one card less -he has the card he just asked for)

2 other situations in which we guess the card :

  1. we know the card (he didn't bluff and he replied NO)
  2. we have no cards (forced guess from a number of alternatives, must be done otherwise the opponent will win at his next turn)

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.


3. Card games

3.1 Brag

- ancestor of poker (3-card poker )

Rules:

  1. The best hand wins
  2. Players can bet and re-bet according to the quality of their hard
  3. If the player making the largest bet is not 'called', then he wins without showing his hand (=>possibility of bluff)

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):

  1. Prile of 3s (three 3s)
  2. Prile (three cards of the same value)
  3. Straight flash (three cards, consentive in value and identical in suit)
  4. Straight (consecutive in valu)e
  5. Flush (identical in suit)
  6. Pair (2 cards of the same value)
  7. High card (none of the above)

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)

  1. Prile of 3's
  2. 3 as the first card: p=4/52
    p1=4/52*3/51*2/50=0.02% (once in approx. 5000 hands !)

  3. Prile
  4. p2=13*p1-p1=12*p1=0.22%

  5. Straight flush
  6. the first card: anything, e.g., 8:
    p3=(2/51*2/50+2/51*1/50)*12/13=0.22%

  7. Straight
  8. 16 possibilities - straight flush => p4=15*p3=3.26%

  9. Flush
  10. p5=52/52*12/51*11/50-p3=4.96%

  11. Pair
  12. PP* or P*P or *PP
    p6=3/51*48/50+48/51*3/50+48/51*3/50=16.94%

  13. High card

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
  2. the rules of bidding
  3. number of players
  4. the order in which the players bid (the last person has an advantage over the first person)
  5. bluffing

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.

Generalizing to n players:

    1. if first_bidder = 0 then first_bidder := me
    2. if value_of_my_hand >= (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

 

3.2 Poker

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 :

  1. Four flusher - 4 cards only of the same suit (p=0.04)
  2. Open straight - 4 cards only in sequence (p=0.04)
  3. Inside straight -one inside card is missing from the sequence, e.g. (4,5,-,7,8) (p=0.12)

(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.

 

3.3 Black Jack

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:

  1. Splitting pairs: If the player's first 2 cards are identical in value, then he may split them into 2 hands and receive a second card on each. In effect it allows a player to have and play 2 hands if he wishes.
  2. Doubling down: After looking at the initial value of his hand (or hands), a player may double his bet and draw one, and only one, more card.

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:

  1. To calculate the ratio Others/Tens, a player must be in a game where he can see almost all the cards played. Some casinos deal the cards face up (the dealer has fixed rules so he gains no advantage). If this is not the case then a player must either play by himself or with people who will turn then cards up.
  2. Knowing the ration Others/Tens, the amont of the bet must be calculated (the minimum has to be bet when the casino has the advantage - roughly half the line - and the maximum when the player has the advantage. Such behaviour is called 'betting wild' and is unwise, partly because it requires a very large bank roll as the fluctuations of fortune are enormous, and partly because it can win at such a rate as to cause the player to be banned from the casino. It is better to relate the amount of the bet to the amount of the advantage.
  3. Suggested scheme

    Other/Tens Ratio

    Bet (in units)

    >2

    1 (minimum)

    2 - 1.75

    2

    1.75 - 1.65

    4

    <1.65

    5 (maximum)

  4. The best strategy changes as the ration changes. All the results from the computer had to be combined into a system which allows for this. The resulting tables for strategy are complicated and require at least one week for a player to become proficient.

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

    1. all cards are dealt face down
    2. The dealer wins all ties
    3. The dealer is not constrained to a set strategy

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.


4. Board games

4.1 Chess

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

  1. 1-2 empty squares up from its starting position
  2. from then on 1 empty square at a time
  3. captures opponents in the immediate NE or NW square
  4. becomes a Q, R, B, N on reaching the 8's rank
  5. captures en passant

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:

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.

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

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

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:

  1. Give all captures.
  2. List the remaining moves in order of resulting mobility ratio.

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:

Board representation

    1. Shannon: 10x12 array
    2. 8x8 array
    3. bit patterns

 

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


5. Solitairs and Puzzles

5.1 Peg Solitair

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:

 

5.2 Hares and Tortoises (and other coin problems)

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:

  1. Get from Fig.1 to Fig. 2 with just 3 moves of 2 contiguous coins (the coins to be slid on the table, remaining in the same orientation and touching throughout).
  2. HHHTTT HTHTHT

    Fig. 1 Fig. 2

    Solution: (T is bold) Start form 012345, move 01 to 67, 56 to 89 and 23 to 56

  3. The same, but reversing the orientation of each pair of coins as it is moved.
  4. Solution: Start form 012345, move 01 to 76, 23 to 98 and 56 to 65

  5. Similar problems, but with more coins.
  6. Delannoy: With n pairs of coins can always be solved in just n moves.

    Tait: It requires n+1 moves if n > 4

  7. From the 6 coins of Fig.3 into a ring (Fig.4) with just 3 moves. At each move one coin must be slid on the table, without disturbing any of the others, and positioned by touching it against just 2 coins. For example, you might try Fig.5 for your first move, but then you wouldn't be able to slide the middle one out.

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.

 

5.3 Magic squares

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):

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.

 

5.4 Chessboard problems

  1. Chessboard of some given size and a knight are given. First such a path for a knight, so that each square on the board would be visited just once. The size of the board and the starting position for the piece are given. Find at least one solution.
  2. 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

     

  3. Chessboard of the given size NxM, some squares are occupied by pices. Find for any pair of empty squares a minimal connecting route which can be used by king to get from the first square to the other. (8-connection).

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

5.5 The tower of Hanoi

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:


6. References:

  1. E. R. Berlekamp, J. H. Conway, R. K. Guy: Winning Ways for Your Mathematical Plays, Academic Press, 1982, London
  2. J. H. Conway: On numbers and Games, Academic Press, 1976, London, San Francisco, New York
  3. A. G. Bell: Games Playing with Computers, George Allen & Unwin Ltd., 1972, London
  4. E. Rich: Artificial Intelligence, McGraw-Hill, 1983, New York
  5. D. Spanier: Hazardní hry. Kapesní pruvodce, Krok, 1991, Ostrava
  6. D. Steinwender, F. A. Friendl: Sachy na PC, Unis Publishing, 1996, Brno