Heuristic quality: monotonicity, informedness, and the 8-puzzle

Two ways to grade a heuristic

Admissibility tells you a heuristic is *safe* (it won't break optimality). Two finer properties tell you how *good* it is.

### Monotonicity (consistency)

A heuristic $h$ is monotone (a.k.a. consistent) if for every state $n_i$ and any descendant $n_j$,

$$h(n_i) - h(n_j) \le \text{cost}(n_i, n_j), \qquad h(\text{goal}) = 0.$$

That is, the estimate never drops by more than the actual step cost between the states. Monotonicity is a stronger, local version of admissibility: every monotone heuristic is admissible (sum the inequality along any path), but not every admissible heuristic is monotone.

The practical pay-off: with a monotone heuristic, the first time best-first reaches a state it has already reached it by an optimal path. So a re-discovered state can simply be discarded — no path-length comparison needed — and the $f$ values of successively expanded states are non-decreasing.

### Informedness

For two admissible heuristics $h_1$ and $h_2$, $h_2$ is more informed than $h_1$ if $h_2(n) \ge h_1(n)$ for all $n$ (while both stay $\le h^{*}$). A more informed heuristic gives a tighter lower bound, so A\* with $h_2$ expands a subset of the states it expands with $h_1$ — it reaches the optimum examining fewer states. (Caveat: a more informed heuristic can cost more to *compute*; the saving in states must outweigh the per-state cost.)

Worked example: two 8-puzzle heuristics

For the 8-puzzle, two classic admissible heuristics:

- Tiles out of place — count how many tiles are not in their goal cell. Each move fixes at most one tile, so this can never exceed the true number of moves ⇒ admissible. - Manhattan distance — sum, over all tiles, the grid distance (rows + columns) each tile must travel. Tiles can't teleport, so this also never overestimates ⇒ admissible — and it is a tighter count, so it is more informed.

Take a scrambled board and a goal board. Counting gives tiles-out-of-place $=4$ and Manhattan $=5$. Manhattan $\ge$ tiles-out-of-place on this state (and in general), confirming Manhattan dominates — it is the more informed of the two while remaining admissible.