In this chapter we'll look at a one-person game that was popular in my childhood (long before computers). It's a bit like the Rubic cube which came later but was less challenging.

The game has a small platform with generally 16 slots in a 4 by 4 square. There are 15 tiles usually numbered from 1 to 15, one per slot. This leaves an empty slot. Any tile adjacent to the empty slot may slide into it, which then makes the tiles previous slot empty. The object is to slide tiles, one at a time, to bring them into order. The order is first by row and then by column, with the empty slot at the end.

To keep things simple we'll work with a 3x3 game with tiles numbered 1 to 8. Here is an example of the game in the final configuration.

1 2 3 4 5 6 7 8

The following shows how the moves may be made. Three moves are possible with the tiles in the 1st configuration on the left resulting in one of the configurations on the right.

1 2 3 4 5 6 7 8 ==>

1 2 4 5 3 6 7 8

1 2 3 4 5 8 6 7

1 2 3 4 5 6 7 8

This game can be played in a similar manner to the *water buckets* problem
where we used either a stack or a queue to control a depth first or breadth first search. To avoid having to repeat this material , please first
read Queues, Trees and Water Buckets if this material is new to you and then return.

What makes this game more interesting than water buckets is that the search space, even for the 3x3 version of the puzzle contains enough possibilites that we need be more clever in our approach. The number of possible *node* configurations in the 3x3 puzzle is 9 factorial or 362880. (why?). For a 4x4 puzzle the number is 20922789888000.

We'll look at doing the two brute force searches and then optimize them with 2 interesting algorithms that will greatly trim the work required. These are the *Greedy* and the *A-star* algorithms both of which require us to estimate the "goodness" of any particular configuartion with a "heuristic". And to make it even more interesting, we'll use a few different ones.

In the file tiles3x3.py we have some functions to manipulate the tiles board configurations in the 3x3 game.

Our basic configuration can be represented nicely in a 9 character string using the digits 1-8 and the underscore character '_' for the empty position. The function *printPuzzle* outpus a rudimentary character-based representation.

>>> import tiles3x3 >>> board = '1234_5678' >>> tiles3x3.printPuzzle(board,"sample board") ----------- sample board 123 4_5 678

The slots under the tiles are numbered as follows in order to align with the Python zero-based array and string indexing.

0 1 2 3 4 5 6 7 8

In the sample board above, slot 4 is empty and a move can be made by moving one of the tiles slots 1, 3, 5 or 7 into the empty slot 4.

The function tiles3x3.getMoves(board) returns the number of the empty slot and a tuple of slots that are legal moves.

>>> tiles3x3.getMoves(board) (4, (1, 3, 5, 7))

The function tiles3x3.makeMove creates a new board by interchanging the tiles in the two slots passed

>>> nextboard = tiles3x3.makeMove(board,4,3) >>> tiles3x3.printPuzzle(nextboard) ----------- 123 _45 678

So here, tile 4 (in slot 3) is moved to the empty slot.

Finally, a very useful function calulates the so-called "manhatten" distance between two slots. It is the number of moves needed to move from one slot to the other where no diagonal moves are allowed. Its name, of course, suggests that in Manhatten, even the crows fly through the streets and not over the buildings.

In addition to "tiles3x3.py" you can also well imagine a "tiles4x4.py" that would simply contain some pretty intuitive modifications. The tiles could be named 1 to 15 or perhaps hexidecimal '1' to 'F' or even 'A' through 'O'. I'll leave that as an exercise for the reader.

There is more information that must accompany the layout of the tiles. I want to take the approach of keeping this information in a tuple rather than creating an object class for the game nodes. One reason is keep the nodes immutable and at some point carry this code to Erlang where we can throw some parallel processing at it. Another is that by ordering the items in the tuple we will automatically get a very simple insertion into a priority queue.

Each tuple representing a game node will have the following 4 items in the order shown.

- The expected cost of the best solution containing the path so far
- The number of this node i.e. the order that it was created (bigger means later)
- The nine character tile configuration of the board discussed above
- A pointer to the parent node of this node

The ordering of the information in the tuple is very important. If you sort a set of node tuples, the order you get is by "least cost" and if the cost of two nodes is the same then the older node come first. The reason we want this will become clear later.

In the *water bucket* problem, we used brute force to search for a solution. The breadth first search let us examine and hold on to possible partial solutions and consider these evenly. As new step in a partial solution was taken the result was sent to back of the queue to let other partial solutions a chance. In this way the shortest and best solution to the problem is found first. The depth first approach, on the other hand, requeues the result at the front. This makes us hammer away at whatever we started and even if we do come to the the solution, it is unlikely to be the optimal one.

But supposing we do something between these extremes. If we can estimate how "good" a partial solution this, that is, how close it is to the final solution, and requeue it based on this, we can get surprising shortcuts in the search for the solution.

This is the heart of the *A-star* algorithm. Rather than depth-first or breadth-first, we use a priority queue to reinsert a partial result ahead of others waiting if there "cost" is greater. The queue itself will have entries sorted by their expected cost.

The other study we did on two player games also used a heuristic function for both the tic-tac-toe game and another for the Kalah pebble game.

The cost estimate consists of two parts. The past consisting of the number of moves made so far and the future which is need an estimate of the moves needed to complete the puzzle. It turns out that the estimates don't have to be terribly good as long they are *balanced*. The only use for the cost estimate is to order competing partial solutions within the priority queue.

The module tilesCost.py contains the function *cost* which computes
an estimate for a board from the number of its depth (moves so far) and how much the tiles are out of order. Specifically, for each tile, it is the *manhatten distance* from where it is to where it should be. In this heuristic we sum the distances for all eight tiles.

def cost(board,depth,number) : # estimate future cost by sum of tile displacements future = 0 for sq in range(9): occupant = board[sq] if occupant != '_' : shouldbe = Goal.find(occupant) future += manhatten(sq,shouldbe) past = depth # Simply the moves so far for this path return past + future*3 # best heuristic

And here is the function *manhatten* in the module tiles3x3.py

manTable = {} def manhatten(a,b) : # a,b are squares 0-8. 3x3. return manhatten dist global manTable if not manTable : print "Building table for manhatten distance" for aa in range(9) : for bb in range(9) : arow = aa/3; acol=aa%3 brow = bb/3; bcol=bb%3 manTable[(aa,bb)] = abs(arow-brow)+abs(acol-bcol) ans = manTable.get((a,b)) return ans

On the first call to the function, the dictionary *manTable* is built which then contains the distance for each possible pair of squares (how many?).

>>> tiles3x3.manhatten(1,8) Building table for manhatten distance 3 >>> tiles3x3.manhatten(0,8) 4 >>> tiles3x3.manTable {(7, 3): 2, (4, 7): 1, (1, 3): 2, ... (0, 2): 2, (8, 4): 2} >>>

The function *search* in tilesSearch.py is the top-most function and uses the *cost* function described above. It is very similar to the depth-first and breadth-first function in the *water Bucket* study. However, we use a priority queue (in the python library) to maintain the order the queue so that the "best" partial solutions go toward the head of the line.

# tilesSearch.py # # Search for sequence of moves to bring a randomized tile puzzle # into order import time, Queue from tiles3x3 import Goal, getMoves, makeMove, manhatten, printPuzzle from tilesCost import cost def search(board) : global nodeNum nodeNum = 1 closed = {} queue = Queue.PriorityQueue() orig = (cost(board,0,nodeNum),nodeNum,board,0,None) queue.put(orig) closed[orig] = True count = 0 solution = None while queue and not solution : entry = queue.get() # breadth first if just nodeNum sort junk1,junk2,parent,pdepth,grandpa = entry count += 1 empty, moves = getMoves(parent) for mov in moves : child = makeMove(parent,empty,mov) if closed.get(child) : continue closed[child] = True nodeNum += 1 depth = pdepth+1 priority = cost(child,depth,nodeNum) # low cost = high priority newEntry = (priority,nodeNum,child,depth,entry) queue.put(newEntry) if child == Goal : solution = newEntry

We start with the original configuration in *board* and insert the tuple for it into the queue. Its tuple has the cost, node number, configuration, depth and a pointer to its parent which in *None*.

Until a solution is found or none is possible, a parent node is pulled from the queue and its children nodes (possible moves) generated. Any move that takes us to a previous *closed* position is discarded to keep us from just getting into a loop. The tuple is constructed so that the ordering in the queue is first by *cost* (low costs go to the front) and then by the *nodeNum* which is unique.

Each node except for the original has a pointer back to its parent so that the solution can be easily reconstructed.

if solution : print count, "entries expanded. Queue still has " , queue.qsize() # linkage to parents make the path in reverse path = [] while solution : path.append(solution[2]) solution = solution[4] path.reverse() return path else : return []

Finally the *main* funtion just sets the egg timer sends the configuration on the command line to *search* and outputs the results.

def main() : import sys, re # board is a 9 digit board board = re.sub("[^_1-9]","",sys.argv[1]) startTime = time.time() path = search(board) endTime = time.time()-startTime print "tilesSearch.py:", len(path),"moves" print "took", endTime, "secs" print path

When you bought one of these puzzles, it came with the tiles in order. You then could slide the tiles around to scramble them into a puzzle to be solved.

The little program tilesScramble.py does a random walk (drunkards walk) of the empty space for the number of steps input and outputs a new configuration. It avoids returning to a previous configuration with the dictionary *used*. I won't explain the code as it is pretty straight-forward. Here are a few examples of its use.

$ python tilesScramble.py 10 5126_3478 $ python tilesScramble.py 10 41263875_ $ python tilesScramble.py 40 2546_7813

In this section we'll look at solving the problem by brute force in two ways, depth-first search and breadth-first, and then with an intelligent heuristic. Recall above that the *cost* function returns

return past + future*3 # best heuristic

which combines the *past* (moves so far) with an expected cost of *future* moves. The constant factor of 3 means we expect 3 moves to improve the puzzle by one less unit of manhatten distance. I arrived at this from just from playing around. We'll discuss how to test this a bit later.

In the *cost* function the node *number* (order of nodes creation) is passed as a parameter.
We can use this to force either a breadth-first or depth-first search by placing new nodes
onto the back of the queue or front of the queue respectively. We'll temporarily replace the *return* with one of these two.

return number # new nodes to the rear (breadth first) (or) return -number # new nodes to the front of the queue (depth first)

Let's look at the depth-first. The configuration was generated by 15 random moves with tileScramble.py and will be used for all three tests.

$ python tilesScramble.py 15 536_18247 $ python tilesSearch.py 536_18247 Building table for manhatten distance 42378 entries expanded. Queue still has 32302 tilesSearch.py: 37892 moves took 1.94441699982 secs ['536_18247', '536218_47', ... '1234567_8', '12345678_']

So, tens of thousands of nodes created and after about 2 seconds the first solution encountered takes 37892 moves. A few were left of the listing.

Next, a depth-first brute force search. This will come across the shortest solution first. Remember, we just have to remove the minus sign from the *return* statement.

$ python tilesSearch.py 536_18247 Building table for manhatten distance 5018 entries expanded. Queue still has 3159 tilesSearch.py: 16 moves took 0.194941997528 secs ['536_18247', '536218_47', '5362184_7', '53621847_', '53621_478', '53_216478', '5_3216478', '_53216478', '253_16478', '2531_6478', '2_3156478', '_23156478', '123_56478', '123456_78', '1234567_8', '12345678_']

That's much better. A nice solution with just 16 moves. But still a large amount of computation that created over 8000 nodes.

Finally, let's return to our "best" heuristic above, restoring the original return. This is basically the A-star algorithm.

$ python tilesSearch.py 536_18247 Building table for manhatten distance 314 entries expanded. Queue still has 208 tilesSearch.py: 22 moves took 0.0132250785828 secs ['536_18247', '5361_8247', '5361482_7', '53614827_', '53614_278', '53_146278', '5_3146278', '_53146278', '153_46278', '1534_6278', '1_3456278', '_13456278', '413_56278', '413256_78', '4132567_8', '4132_6758', '413_26758', '_13426758', '1_3426758', '1234_6758', '1234567_8', '12345678_']

This is interesting. Our solution is not as short but the computation is less than by about a factor of 15, both in time and in the number of nodes produced.

Finally, I'd like to look at one other algorithm that is somewhat simpler. This algorithm simply chooses the best move at any particular point but never backtracks. It would need a queue for that. But it can be very fast. tilesGreedy.py can get stuck and in fact fails to solve the above puzzle. But here is one it can. And we can compare it with the A-star solution.

$ python tilesGreedy.py 75126348_ # Greedy Algorithm Building table for manhatten distance tilesGreedy.py: 75126348_ 59 moves took 0.00218510627747 secs ['75126348_', '7512634_8', '751263_48', '751_63248', '_51763248', ... '1235_6478', '123_56478', '123456_78', '1234567_8', '12345678_'] $ python tilesSearch.py 75126348_ # A-star Building table for manhatten distance 1084 entries expanded. Queue still has 679 tilesSearch.py: 29 moves took 0.0440242290497 secs ['75126348_', '7512634_8', '7512_3468', '7_1253468', '71_253468', '71325_468', '7132_5468', '7132654_8', '713265_48', '713_65248', '_13765248', '1_3765248', '1637_5248', '1637452_8', '163745_28', '163_45728', '1634_5728', '1_3465728', '13_465728', '13546_728', '1354_6728', '1354267_8', '13542678_', '13542_786', '13_425786', '1_3425786', '1234_5786', '12345_786', '12345678_']

*Greedy* gave us a longer solution with some meandering, but run 22 times faster. There are problems (this is not one of them) where a greedy algorithm will find the optimal solution.

How good is a heuristic? Can we test it? Here's an idea.

I haven't done this but it should not be too difficult. Once a solution is found we can look at the cost attached to each node. If the cost estimates are good, they should not change by much. Another way of saying this is that as the solution proceeds the increasing cost of the *past* should balance the (estimated) decreasing cost of the future.

If the overall costs go up then the *future* part is being discounted, and if the costs go down then the *future* is being over-estimated. Adjusting the ratio to find the sweet spot could even be automated.

Have Fun.

Copyright © 2014-2015 Chris Meyers