Transcript Document

Solitaire Puzzle
The solitaire puzzle is played with 32 pegs on a board with 33 holes.
Initially all holes are occupied except the central hole.
A move consists of
• removing a peg,
• hopping it over an adjacent peg,
• putting it into an empty hole one space further on,
• removing the peg hopped over
The object is to end with just one peg, in the central hole.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
1
Encoding positions
A program might represent a state of the puzzle as a 33-bit number.
Each hole’s bit has meaning: 1 = occupied 0=empty.
Of the many ways of assigning bits to holes,
• some will be completely arbitrary
• Some will be systematic but in a useless way
• Some will be systematic in a potentially useful way
 because they capture (some of the) symmetry in the layout.
For example, each of the four blocks can
be transformed into another by a rotation.
The central hole is out on its own.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
2
Exploiting a symmetrical encoding
Using 4 8-bit bytes, each hole (except the central one) can be assigned a bit
position within one byte that is the same as the position of related holes in other
quarters of the board.
This gives an easy way to find a canonical representation of a position
• Such as, pick the numerically least number of the four byte-rotated
representations of the position
So that, if rotationally-equivalent positions are reached by different sequences of
moves, three out of four may be ignored.
1 2 3
4 5 6
7 8
1 2 3
4 5 6
7 8
Which
is
least?
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
3
Encoding moves
A move involves 3 holes
• two particular holes must be full, and one empty, before the move,
• full holes become empty, and the empty hole becomes full, after the move.
A move can therefore be represented as a pair of 33-bits numbers, N1 and N2:
• N1 has 3 bits set to identify the three holes
 whose content must be tested before the move
 Whose content must be inverted after the move
• N2 has 2 bits set to identify the two holes that must be full before the move
If (( oldposition AND move.N1) = move.N2)
Then newposition := oldposition XOR move.N1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
4
Move example
Posn= 11111111 11111111 11111111 11111111 0
00000000 00000000 00000000 00001001 1
N1=
N2=
00000000 00000000 00000000 00001001 0
Posn:= 11111111 11111111 11111111 11110110 1
canonical 11110110 11111111 11111111 11111111 1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
5
Searching 1
Each position can be faithfully represented (this way) using 33 bits.
• From a 33-bit position you can generate new 33-bit positions.
• But when/if you solve the puzzle, you - presumably - want to show how
• So with a position, store an record of which move was played to get there.
There are 76 possible moves
• 2 from each “1” “3” “4” and “6”,
• 1 from each “2” and “5”
• 4 from each “7” and “8”
• 4 from the unique centre
A number 1…76 can be stored in 7 bits; so a position with move-number can be
stored in 40 bits.
A sorted sequence of 5-byte numbers could be maintained to record positions
that have already been generated, & how you got there or better how to get back
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
6
Searching 2
•
•
•
•
A breadth-first search could take the positions generated by N moves, and
build a sorted sequence of all possible positions generated by N+1 moves.
And repeat this until 31 moves have been played.
But
1. Breadth-first search consumes a lot of storage
2. It is possible to stop the search after only 16 moves
After the 16th move, generated positions will have 32-16 filled holes, 1+16
empty.
If we take such a position, and invert its positional bits (not its move number)
and canonicalise, we get something comparable to a 15-move position.
When searching forward from the start of the puzzle, we
were in effect also searching backward from the end!
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
7
Constructing the solution
Suppose that there are two sequences A, B, of (CanonicalPositions)+(moves)
PAN:MAN and PBN:MBN , so that (PA16) = canonicalise(NOT (PB15)).
PA1:MA1
PA2:MA2
PA3:MA3
PA16:MA16
P0
PB1:MB1 PB2:MB2
PB3:MB3
PB15:MB15
From any PAN:MAN you can reconstuct PAN-1 and look up PAN-1:MAN-1 ,
likewise with PBN:MBN .
• As canonicalisation effectively rotates positions, so too it rotates moves.
They should be numbered sensibly to facilitate this: symmetric moves
systematically numbered in steps of 19 or more.
The solution then consists of the concatenation of
1. Appropriately rotated MAN , N=1…16
2. Appropriately rotated MBN, N=15…1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
8
Storage requirements
Breadth-first search of a game tree always suffers from the need to maintain a
queue of unexpanded interior nodes
A node has 5 bytes of information, and we may expect approx
= 1B of them; to be kept in a sorted sequence of some sort.
1/4N=1..16(33CN )
Could instead arrange
• a vector, containing all nodes with same lowest positional byte
• a table, indexed by a) lowest positional byte and b) its no-lower neighbour
• Godel numbering of all positions, recording one byte containing 0 or move#
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
9
Where’s the AI? Where are the heuristics?
If “solving Solitaire” were scientifically or financially significant, it could be
solved by a brute-force method such as outlined earlier. 4+ Gb of storage and a
few hours (?) of CPU should either do it, or prove it cannot be done.
For “solving Solitaire” to be really interesting from an AI point of view, it should
be that there are heuristics which can be used to effectively prune the search
space.
Aggressive Forward Pruning - rather than the provably safe pruning of search
trees done by  - is useful in problem-solving domains (including game-playing
and puzzle-solving) where there is heuristic knowledge that can be used to tame
an unwieldy search space.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
10