Okay, now you can hear me better.

And thanks a lot to the people in the background who are controlling the stream who've called

him who had a key.

Okay so, the algorithm is very simple.

We just basically have a loop.

We have a loop where we basically, and we keep in mind one of the states, and then we

compute the best successor by going over all the successors and then seeing how they look,

say in a heuristic function or something like this.

And then of course, if one of the neighbors is better than the one I am, I'll take the

next neighbor.

And you can see this idea of hill climbing, right?

Think of you're in a landscape, right?

And I'm maybe in this state and I see, oh, there's a neighbor state.

It's better than mine.

So I'm going here.

And you can imagine that I'll climb this hill by just going to the next, like the next best

thing.

It's actually of course, we would say, a greedy search, right?

We're trying to optimize, but we're not doing A star.

So we cannot even do A star because we don't have any way of remembering anything.

anything. So essentially greedy search without memory. And that works well. Right. If we,

for instance, take the eight queens thing here, right, then we basically could have

a heuristic cost estimate where we're looking at the number of queens threatening each other,

which is 17 here, and then we can just basically move, say, a queen in its column to reduce,

to find a configuration, a neighbouring configuration that has a better cost.

And if I'm lucky, I'll solve this.

But if you look at it, this thing has local minima, right?

There are sometimes configurations where you're not actually going to find a neighbour that

is better and you still haven't solved it.

There's one of those.

I should make the picture bigger.

I hope you all see the conflict in there.

Note that the designer of this example has already made a crucial optimisation.

Who can see that?

So we already, as the designer have realised that if there are two queens in a row, nothing

works. Right. So the kind of zero knowledge version of this would be to just basically

put the queens anywhere and allow random moves. But of course that is much more difficult

than what I'm doing here, namely put one queen in every row and only move vertically. Much,

much, much simpler problem. The branching factor is eight and not 64. Remember, we're

exponential anyway. So if the branching factor is almost 10 times bigger, you're sinking

much faster as an algorithm. I've already, as the algorithm designer, done something.

It's hard enough anyway. So we're doing local search in an eight-dimensional search space

instead of a 64-dimensional one. And what we're doing is actually hill climbing, as

I said. We're taking greedily the next best neighbor. And of course, that's wonderful

if you're in, say, Japan, where Mount Fuji essentially looks like this. And it's essentially

flat around that. You start randomly, you're in the global maximum. How nice. The world

isn't like this. The world is much more like that. This is a one-dimensional hill climbing

situation. And basically, if you're lucky, you basically start out here and you go to

the global maximum. Wonderful. If you start out here, you reach a local maximum, which,

of course, isn't even the worst thing you can have. You often have situations where