A-Star (A*) Algorithm in Python February 2nd, 2005

Update: 25-Jan-2010

Since there have been many requests over the years for the source code referenced in this post, I decided to share it. A cautionary note to undergrad CS students (who I can only assume are the requestors): CS professors are pretty good at catching cheaters, so learn from others’ code, but write your own.

Source: astar.py

4 Knights Problem

4 KnightsWe start with two white knights and two black knights in the following configuration.

The goal is to move the knights so that the white knights and black knights effectively swap places.

Assuming we know nothing about the solution to this problem, the A-Star Algorithm is a good choice to search for the solution.

With no heuristic function or check for previously visited states, A* degenerates to uniform cost search. This is not an efficient method, especially in this particular domain. Consider: for every turn, one legal move will be the reverse of the last move made. The branching factor for this particular problem is greatly increased by this feature of the domain, and can thus be reduced by the same factor if we account for previously visited nodes.

It wouldn’t be A*, though, if we didn’t have a heuristic function to help guide our search. At first glance, misplaced knights may seem to be a good choice for a heuristic. For each knight that is not “in place”, we add one unit to the estimated distance (cost) to the goal. The function looks like this:

def distance(node):
  distance = 0
  if (node.contents[1] == "black"): distance += 1
  if (node.contents[6] == "black"): distance += 1
  if (node.contents[5] == "white"): distance += 1
  if (node.contents[7] == "white"): distance += 1
  return distance

Adding the above code into cost of each node does give us some improvement in time and space complexity, as we’ll see below. But the heuristic can still be improved.

In the previous heuristic, a knight “out of place” added at most one unit to the estimated cost. It is the case that a knight out of place is at least one move away from its goal square.

The graph to the left is another way of representing our 10 Square chessboard. Each node represents the corresponding square, and each node’s neighbors are the squares that are one move away. By examining the graph we can determine the minimum number of moves from each square to the appropriate goal square. The new heuristic will look like this:

def distance(node):
  distance = 0
  for square in node.contents.keys():
    if node.contents[square] != None:
      # no "switch" statement in python
      if square == 1:
        if node.contents[square] == "black":
          distance += 0
        else:
          distance += 1
      elif square == 2:
        if node.contents[square] == "black":
          distance += 3
        else:
          distance += 4        
      ...
      elif square == 10:
        if node.contents[square] == "black":
          distance += 2
        else:
          distance += 3
  return distance

Time and Space

Schema Nodes Searched Execution Time
Uniform Cost, no check for repeated states 46945… 18.5333 hours when I terminated the program
Uniform Cost, check repeated states 1204 14.42s
A-Star, misplaced knights 1112 12.77s
A-Star, minimum distance to goal 868 11.25s

It seems that the major savings achieved with the second heuristic is in space rather than time. While we reduce the search space by 22%, the cost of computing the new distance is substantially more, giving us negligible savings in time.

Check out the full source for the A* Algorithm in Python or let me know if you have any ideas for better heuristics.


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 

East Bay Psychotherapist
Licensed Clinical Social Worker provides psychotherapy and counseling services for couples and individuals in the East Bay Area.