So the next question of course is how do we do that?

And the answer is simple.

The best way of finding good heuristics is cheating.

Again.

So say we have the eight puzzle.

And so let's look at two heuristics.

One is the number of misplaced tiles.

So we have the goal state here, we have this state here, and so to compute the number of

misplaced tiles you look at this.

Seven is it in the right place?

No it's not.

Two in the right place?

No.

Four in the right place?

No.

Five?

No.

Six?

No.

Why is that?

Why am I not getting six?

Help.

I don't know.

Maybe I have a, I have replaced some pictures so maybe I have to be very careful here and

look back at last year's.

I tried to get better pictures but.

If the empty tile would be on the right and down side then the two and the six would be

correct.

So you may.

I'll check up on it.

You can compute misplaced tiles, it's not very difficult heuristic.

The other thing you can do is essentially looking at how far misplaced the tile is.

Namely for instance the seven is here, should be there, so is one, two, three out of place.

And I hope that this is this three here.

So those are two heuristics.

And if you look how iterative deepening search or something like this, I don't know how A

star fares with these in comparison to say iterative deepening search, then if you have

a problem of depth 14, then iterative deepening search can barely do it.

Depth 14 means you need optimally 14 moves here.

Which is a relatively simple instance of a problem.

A star does better by several orders of magnitude.

And A star with the Manhattan distance heuristic does even better.

So if we go to depth 24, then iterative deepening search has no chance.

Again A star solves them easily.

Once with 40,000 nodes, once with 1600 nodes.

So A star does well, given a good heuristic, and it matters which kind of heuristic you

do.

Just experimental.

It's easy to implement these three and just run them against each other.

The question of course is why is this one better than that one?