Assignment Overview
Implement (using MATLAB) different heuristics to solve the 8-puzzle using A* search.
You will first implement a neighbor function to define the implicit graph, then two heuristic functions, and lastly the A* search procedure itself. As described in class, the 8-puzzle is a simple (one-person) game where tiles numbered 1 through 8 are moved on a 3-by-3 grid. Any tile adjacent to the blank position can be moved into the blank position. By moving tiles in sequence we attempt to reach the goal configuration.
For example, in the figures below, we see three different game configurations: configuration (b) can be reached from configuration (a) by sliding tile 5 to the left; configuration (c) can be reached from configuration (b) by sliding tile 6 up. Configuration (c) is the goal configuration. The objective of the game is to reach the goal configuration from some starting configuration with as few moves as possible. Note that not all starting configurations can reach the goal.
(a) The first thing you need to do is to implement a neighbor function. For any state of the game (i.e., any configuration), define a function neighbor(state) that returns a list of neighboring states. Feel free to use any representation to encode a state. One possible representation: a state is a list with nine elements corresponding to the tiles (or the blank space). For instance, the three states shown above could be encoded, respectively, as: [1,2,3,4,b,5,7,8,6] [1,2,3,4,5,b,7,8,6] [1,2,3,4,5,6,7,8,b]
In this game, we are interested in minimizing the number of moves necessary to reach the goal configuration, so you can assume a cost of 1 per move. For uniformity and ease of marking, the list of neighbors returned by your neighbor function should follow a specific order: each neighbor can be viewed as moving the blank position either up, right, left, or down; your neighbors should be listed in that order. Of course, if some of these neighbors are not possible (e.g., in configuration (b) above, the right neighbor of tile 5 does not exist), they will not be in the list.
(b) Implement the following two heuristic functions (to be used later in A* search):
– h1(state,goal) returns the number of tiles (excluding the blank) that
are out of their desired goal position in state state. The h1-values of the three states above are 2, 1, and 0, respectively.
– h2(state,goal) returns the total Manhattan distance of all tiles (excluding the blank) from their desired position. That is, for each tile, the Manhattan distance is the sum of the horizontal and vertical distances between its position in state state and its desired position in the goal state. The h2-values of the three states above are 2, 1, and 0, respectively.
(c) Implement a function astar(state,goal) to do standard A* search. This
function should return the path found from state to goal, the length of the
path and the number of nodes expanded (i.e., number of nodes removed
from the queue). Note that some state-goal pairs do not have any solution
(i.e., no path), hence you should limit the number of expanded nodes to
2000. Note also that when a solution can be found (before the 2000-node cutoff), it will be unique, assuming that your neighbor function produces neighbors in the order specified in part (a).
