Okay, so really what we're doing here is we're removing the problem from search to finding

good heuristics.

And so we want to study heuristics.

Okay, so first thing to do is probably to define that.

And so a heuristic function is a function into, say, the real numbers.

You want heuristics to be infinite if you know that you never, never, ever, ever want

to go there.

And one thing that's very natural for a heuristic function is that if you're at a goal state,

the heuristics should be zero.

Okay?

Anything else is certainly not a good heuristic.

Something that steers you away from the goal, bad idea.

So the idea is that you want to estimate the goal distance or the goal cost, the future

cost.

That's really what those things do, and when you're in a goal, then cost is zero.

Okay, so that's the definition we're going to look at.

And of course, we always know a good heuristic, which is the optimal heuristic, which is the

actual goal distance function.

Right?

Wonderful heuristic, except of course, to compute it is very expensive.

That's what you get when you, when, so there's a notion that a game is solved, for example,

in tic-tac-toe.

We know the goal distance function there.

And if we have that, that gives you a winning strategy.

So this is the one we would like to have.

Unfortunately, we cannot compute it, so it's kind of out.

So we want to have something that's possibly worse than this.

Well, certainly worse as a heuristic.

But it is so easy to compute that it actually gives us, that it actually gives us a hint

on where to search.

Okay?

So heuristic comes from this word, Greek word, you know the word eureka, which is I find

and it helps you find.

And yeah, it's kind of a rule of thumb kind of thing.

We humans are extremely good at this.

Okay?

So we want a heuristic to be accurate because of it.

It's very easy to make a heuristic that's inaccurate.

Any ideas how to very easily do that?

Generate a random number and.

Oh, but that wouldn't be a heuristic.

Why would that be a heuristic?

The only thing we want of a heuristic is that it's zero at a goal state.

And that is not random.

Okay we set the heuristic and the goal state to zero and generate random numbers for other

fields.

Okay, that's a little bit better.

Yes.

There's an even easier thing.

You can just always take zero.