Okay, and we briefly talked about an advanced algorithm called simulated annealing, which

essentially has the idea that if you want to, if you are randomly restarting, then you

never know whether you are in a good local minimum or in a bad local minimum. So if you

want to have a preference for the good ones, you kind of make your random jumps fewer and

less far. And if you do that, it's a simple idea. Surprisingly, you get a good algorithm.

There it is. If I gave you the homework, take these ideas into account and implement them,

I'm pretty sure you would end up with essentially that. Okay? A local search algorithm. And

it basically says, well, make this thing the kind of value difference small and smaller

and smaller again until you're fed up. That's the algorithm. Yes?

I was wondering, is this actually the same as a Gibbs search or Monte Carlo search?

It has. So Monte Carlo search, we'll come to that, is a form of local search. Yes. And

we'll come to these techniques for games because that's essentially what AlphaGo does. And

I thought we should probably cover that. But yes, so Gibbs sampling is a particular way

of computing the utility, which we get for free here. So if you don't know the sampling

thing is what you try to compute by a special method, these numbers. Here it's easy. You

can just count the conflicts in a configuration problem. But if you're in a game, you just

don't know the utility because it's just too far ahead when you win or lose, which gives

you kind of the evaluation. And then you can do Gibbs sampling. But we'll get to that.

Yeah, which probably I should have said, it's not always clear how to get these numbers.

Computing the relative merit of certain factory floor layouts might be quite a lot of work.

It might actually, the work involved in that might eclipse all the work you have to do

for search. Still have to do search, but the real work might be involved in computing these

numbers because you have to simulate or so. Who knows? Good. Okay. So that was local search.

Surprisingly good, given how embarrassingly simple the whole thing is. The next thing

was a set of remarks where I tried to tie local search to genetic algorithms. And the

idea is just very simple. A variant of local search is beam search or K-beam search, where

you instead of have one searcher have K searchers that communicate with each other. And then

if you add on top of that the idea of kind of weeding out the bad searchers and replacing

them with better searchers in some way, then you end up essentially with genetic algorithms

where you have a population of searchers with their current state. Every searcher has one

current state at the moment. Then you communicate in some way in genetics that's via crossover.

Right? And then you innovate by making random changes or random restarts and then you essentially

have evolution if you add survival of the fittest, and that is just K-beam search. And

genetic algorithms are for certain problems where you have the opportunity to organize

survival of the fittest. For instance, because you have games in which you can play against

each other for very little cost and relatively quickly, then genetic algorithms actually

help you do things. By the way, playing against itself is how many of gameplay AIs actually

get good. AlphaZero is the best example right now, which is a successor to AlphaGo, which

you don't tell about the game except for the rules, only the rules, and then it plays against

itself a number of times that only Google can afford. And then it gets better than everything

else on the planet in a variety of games, including Go and chess and all the ones that

have been solved, which is almost all. Okay, that's not quite genetic algorithms, but it's

a form of learning anyway, so they're doing it slightly differently, but they still have

a survival of the fittest kind of learning. Good, we looked at evolving eight queens,

and if you want to implement this, this is relatively easy to implement and is fun to

watch.