Search code examples
algorithmheuristics

Why is this heuristic admissible?

For Tic Tac Toe my lecturer has presented an admissible heuristic (meaning it never overestimates the distance) for the next move in Tic Tac Toe as follows (from the perspective of the O player):

The number of possible lines for O - the number possible lines for X

What I was wondering is why is this heuristic admissible?

Solution

  • It's not.

    O..
XOX
OX.

    Then distance to goal = (3-1) = 2

    Actual distance to goal, 1 (for win by O)

    2 > 1, thus it overestimated.

    Or am I missing something?