Game Playing: The Sliding Tiles Puzzle

The Game Setup

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

The Search for the solution

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.

Representing board configurations

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.

Representing Game Nodes

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.

The Cost Heuristic

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 Search Itself

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

Generating Puzzles

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

Testing various Strategies

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.

The Greedy Algorithm

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.

Final Thoughts

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

.