Thomas Wilk
An analysis of A* versus RBFS for 8-tile and 15-tile Puzzles
The 15-tile and 8-tile puzzles are children’s games where the implementation of A* search and Recursive Best First Search (RBFS) are complete, and optimal. The 8-tile puzzle can be represented by a 3x3 matrix, where there are 8 unique and identifiable tiles, and one blank spot (We will mainly focus on the 8-tile game in this report. The 15 tile game is the same, but with a 4x4 board with 15 tiles and 1 blank). A state is represented by a 3x3 matrix, where the tiles labeled one through eight can be shuffled into any tile within the board. This leaves one blank square.
Figure 1. Sample state of 8-tile puzzle (where 0 represents the blank tile)
All actions of this problem are represented by moving this blank square left, right, up, or down, when applicable. In practice, completing an action swaps the blank tile with the tile relative to that action’s direction (In figure 1, the action “right” would swap 0, and 5). If the blank tile is on the edge of the board, it is not allowed to take an action to move out of bounds. In our representation of this problem, the goal state is constant, regardless of initial state.
Figure 2. Goal State of 8-tile puzzle
The A* algorithm requires a heuristic, an estimate of how close a state is to the goal state. In my implementation, we have two admissible heuristics.
H1 is the Manhattan distance, which is calculated by summing the distance between each tile’s current position, and its goal position. For example, if tile 1 is in position (2,2), and its goal position is (0,0), we would get 4. Doing this for each tile (disregarding blank) gives us an admissible heuristic.
H2 is the number of tiles which are misplaced. For each tile, we check to see if its current position matches the goal position. If it does not, we add one to the counter and continue until all tiles are checked (once again, disregarding blank). This gives a second admissible heuristic.
An admissible heuristic has two requirements. The estimate of a goal state must equal 0. This is intuitive. The distance between the goal state and itself is 0. More importantly, the heuristic is strictly bounded by the real distance to the goal state. If h*(x) represents the exact distance to the goal state from the current state x, then h(x) ≤ h*(x) must always hold to be admissible.
If we were to have h*(x) available, we would always explore the direct path to the goal node. Thus, we can claim that having a larger h(x) (which still is bounded by h*(x)) is better than a smaller one.
In our application, we can see that h1 (Manhattan distance) will always dominate h2 (misplaced tiles) because of the aforementioned facts. In a less technical view, we can say that h1 is a better heuristic because it more accurately estimates how many actions must be taken to achieve the goal state (without overestimating it).