Why is this heuristic admissible?

Question

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?

Answer 1

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?

Answer 2

From Wikipedia:

a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal

What that basically means, is that when you have a heuristic, this will only be admissible if the actual cost to the goal is guaranteed higher than or equal to the estimated cost. A good example for this is a heuristic for the A* path finding algorithm. For that algorithm, you usually use a heuristic that estimates the distance to the target like there is a road directly to it. If you would use a heuristic that would overestimate the distance, it it might not find the shortest possible path.