One way out is to have evaluation functions where you kind of estimate how good your board looks,

even though you don't know the utilities. And as with the heuristics before, this is something

which is informed search. You're looking at the states. So if you're looking at the board,

in chess you're counting pieces, which is not something that is given in the problem description.

Remember in the problem description for chess, we only have states, black box states.

We cannot look into them, but we can allow the heuristic or evaluation function to do that anyway.

Because external information, that's kind of the way we encapsulate information here.

So evaluation functions help because they guide the search.

Because they have to be simple enough, we're analyzing some features, features like how many pawns are there,

how many rooks and so on, and then we weight them in a sum, which is easy and efficient to calculate.

Anything that's much more complicated than this, we are going to have problems in practice,

because we have to do this very, very, very often. We're getting exponentially large fringe,

which means we have to compute these evaluations exponentially often.

And if we do something expensive there, that's going to bog us down even more.

Okay, and kind of the idea is you search until you hit some kind of a horizon, you evaluate there,

and then do something. The problem with this is that in almost all games,

there's interesting things happening after the horizon, which you would like to look at

and know about, but which you can't because the search spaces are too big.

At least if you kind of search uniformly and systematically.

There are ideas where you just basically say, well, we're going to search in this kind of a wavy line,

depending on how interesting things look, and for many games that means how much movement there is.

The large parts of the game where essentially the evaluations are more or less constants over all siblings.

Those are part of the games where you just say, well, let's leave those.

They're uninteresting. We're not expecting anything interesting to happen,

which might be wrong. Very often you kind of have a very quiet thing and then something happens.

If you didn't search there, you're in trouble.

But at least when you know things are happening, that's the idea.

If you know that things are happening, then you can kind of spend more effort there.

That's what is Queer's Inserts and that's kind of what we start with last time.