My artificial intelligence course this semester has been an interesting one, and the midterm exam is no exception. Rather than testing in-class on what we’ve been learning, our professor gave us a take-home exam that was a practical exercise in A* search algorithms.

The problem we were given was to design an A* search algorithm that can find the shortest path a chess knight can take on a 9x9x9 Rubik’s cube to reach a goal at any position on the cube, from any starting position. The algorithm should accommodate the following constraints:

  • The length of each side of a square is 1.
  • The knight can only move as it does in chess, in an “L” shape such that a move must consist of an orthogonal movement to a point two squares away, followed by a perpendicular movement to a point one square away.
  • The knight moves using the intersections between the squares of the cube, rather than the squares themselves.
  • To cross from one face of the cube to another, the knight must first land on an intersection that is on the common edge between the two faces, then jump to an intersection on the neighboring face.

Additionally, we were asked to demonstrate the algorithm by providing a sample search tree that shows the knight moving from a start point on the top of the cube to a goal point on the bottom of the cube.

I considered two heuristics for this problem:

  1. The distance to the goal can be measured as the three-dimensional Manhattan distance from the horses’s current position to the goal.
  2. The distance to the goal can be measured as a modified form of the knight metric, the minimum number of moves a knight (which moves the same as the above-described horse) must take to reach the goal.

Because the first heuristic is likely to overestimate the number of steps required to reach the goal, it is inadmissible and thus I chose to use the second heuristic. The knight metric is a complicated formula, so for the sake of this problem I simplified it to measure the maximum of either \(\lceil \frac{dx}{2} \rceil\), \(\lceil \frac{dy}{2} \rceil\), or \(\lceil \frac{dx+dy}{3} \rceil\), which accounts for the L-shaped movement that a horse makes on the grid. Given that this problem has three dimensions, the heuristic becomes:

$$max (\lceil \frac{dx}{2} \rceil, \lceil \frac{dy}{2} \rceil, \lceil \frac{dz}{2} \rceil, \lceil \frac{dx+dy+dz}{3} \rceil)$$

This accounts for four scenarios as lower bounds, choosing the maximum in order to avoid a large underestimation:

  1. The potential that the distance to the goal is reached mostly by movements in which the longer portion of each move is along the same axis (three possible axes).
  2. The potential that the distance to the goal is reached mostly by movements which reduce the total difference of all three axes by 3.

To ensure that the algorithm adheres to the constraints of the problem, I defined some rules for the algorithm to avoid invalid moves:

  1. Moving the horse into a position that is beneath the surface of the cube.
  2. Moving the horse from one sub-board to another when the horse is not currently on an edge.
  3. Moving the horse into a position in which any coordinate is outside the bounds of the cube’s dimensions.

Lastly, to optimize the algorithm and ensure consistent behavior:

  1. When all f-values of nodes in the frontier are equal, the algorithm will break the tie by comparing their Manhattan distances. This allows the algorithm to avoid unnecessary expansions while maintaining its optimal heuristic.
  2. Nodes will be placed in the frontier in order of lowest x-value first, followed by lowest y-value, then lowest z-value. (This effectively functions as a third tie-breaker.)

With these constraints and rules defined, the A* search algorithm should find the shortest horse jumping path from any given start cross point to any given goal cross point. The algorithm can be represented in pseudocode as follows:

Establish two lists, frontier and explored
Add node_start to frontier

while frontier is not empty:
    current_node ← remove the node from frontier with the lowest f(node) =
        g(node) + h(node) (or secondarily, the lowest Manhattan distance)

    if current_node is goal_node:
        return current_node as the solution and EXIT

    Generate a list next_nodes of each state that follows current_node

    for each next_node:
        next_path_cost = g(current_node) + d(current_node, next_node)
        if no coordinate of next_node is 0 or 9:
            CONTINUE
        if any coordinate of next_node is less than 0 or greater than 9:
            CONTINUE
        if current_node and next_node are in different sub-boards:
            if current_node is not on an edge:
                CONTINUE
        if next_node is in frontier AND g(next_node) <= next_path_cost:
            CONTINUE
        else if g(next_node) is in explored:
            if g(next_node) <= next_path_cost:
                CONTINUE
            Move next_node from explored to frontier
        else:
            Add next_node to frontier
            h(next_node) ← heuristic distance to goal_node
        g(next_node) ← next_path_cost
    Add current_node to explored

if current_node is not goal_node EXIT with error (failure)

The algorithm is demonstrated visually below with a search tree from a start node on the top face of the Rubik’s cube to a goal node on the bottom face of the cube. The coordinates are based on (0,0,0) being one of the bottom corners of the cube. The tree has been pruned for simplicity of demonstration; the algorithm expanded several dozen nodes during its search and the entire tree could not easily fit in a readable way.

Sample Search Tree

In this search, the algorithm expanded every child of the start node, and every child of each of those nodes, before finding the optimal path through (2,9,2). Once it reached the edge of the top sub-board at (0,9,3), it made its way easily down the cube without much looking back to check nodes further back in the queue.

At (0,0,3) the algorithm reached the bottom of the cube, at which point two of its child nodes on the bottom presented identical optimal paths to the goal. The selection of the first node reflects the algorithm’s priority of lowest independent coordinate values. With this behavior and the Manhattan distance as a secondary heuristic together functioning to focus the algorithm, it was able to orient toward the optimal path without getting too deep into other, less optimal paths early in its search.

I only had about 24 hours to turn this exam in while attending other classes and studying for their exams as well, so there’s likely plenty of room for optimizing this algorithm, or to take a more efficient approach overall. But for this quick turnaround I earned a 95, and given that this is a hybrid course for both graduate and undergraduate students, I feel pretty good about that!