Why isn't Nilsson's Sequence Score an admissible heuristic function?

Question

I understand what an admissible heuristic is, I just don't know how to tell whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson's sequence score heuristic function isn't admissible.

Answer 1

I will use the 8-puzzle game to show you why Nilson's sequence score heuristic function is not admissible. In the 8-puzzle game, you have a $3 \times 3$ board of (numbered) squares as follows.

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 7 | 8 | 3 |
+---+---+---+
| 6 | 5 | 4 |
+---+---+---+

The numbers in these squares are just used to refer to the specific squares (to avoid saying the "middle square" or the "upper-left square"). So, when I say square 1, I refer to the upper-left square. In these games, you have 8 "tiles". Let's denote these tiles by $A, B, C, D, E, F, G$ and $H$. So, in this game, there is always one square which is free (or empty), given that there are $9$ squares. The goal of this game is to reach the following configuration of tiles

+---+---+---+
| A | B | C |
+---+---+---+
| H |   | D |
+---+---+---+
| G | F | E |
+---+---+---+

Note that, in the case of the 8-puzzle game, a "state" is a configuration of the board. So, the following two board configurations are two distinct states

+---+---+---+
|   | A | C |
+---+---+---+
| H | B | D |
+---+---+---+
| G | F | E |
+---+---+---+

and

+---+---+---+
|   | C | A |
+---+---+---+
| H | B | D |
+---+---+---+
| G | F | E |
+---+---+---+

The rules of the 8-puzzle are simple. You can move one tile (at a time) from its current position (or square) to another position, provided that the destination square is free. You can only move a tile horizontally and vertically (and one square at a time).

I will not explain in this answer how the Nilson's sequence score heuristic works. Here is a explanation of how is used in the case of the 8-puzzle game. You should read this explanation and make sure you understand how Nilson's heuristic works before proceeding! You can also find an explanation of how this heuristic works in the book "Principles of Artificial Intelligence" (at page 85), by Nils J. Nilsson (1982).

Why isn't then Nilson's sequence score admissible?

A heuristic function $h$ is admissible if $h(n) \leq h^*(n)$, for all states $n$ in the state space, where $h^*(n)$ is the actual distance to reach the goal (which is often unknown in practice, hence the need to use heuristics to estimate such distance).

Note that admissibility is a property that must hold for all states. So, if we find a state where the condition above is not satisfied for the Nilson's sequence score heuristic function, then we show that the Nilson's sequence score is not admissible.

Let us create the following state

+---+---+---+
| A | B | C |
+---+---+---+
|   | H | D |
+---+---+---+
| G | F | E |
+---+---+---+

Note that this state only differs from the goal state by one move: if we move the tile $H$ to square $7$, then we reach the goal state. So, the actual distance to reach the goal state is $1$ move. But what does the Nilson's score function tell us regarding the distance of this state to the goal state? You can see from the algorithm presented in this answer to compute the Nilson's sequence score (of a board configuration) that the score of the configuration (or state) above would be more than $1$ (you can immediately see this because you need to multiply by $3$). Therefore, Nilson's sequence score overestimated the distance to the goal (at least for one state), thus it cannot be admissible (by definition).