We've seen that we can develop systematic procedures and once we have systematic procedures

like Minimax we can actually by thinking a little bit more come up with clever tricks

that have quite profound impact on the search behavior.

And of course alpha beta isn't the last thing you can do.

Being more clever with reordering and all of those kind of things allows optimizations

that are not quite as good as alpha beta.

Alpha beta is so nice because it's easy to understand and has enormous impact which is

why it has to be in the AI lecture.

But for anything subsequent you really have to work much harder and get much less.

But still in a chess competition or something like that that might actually help you.

So there's a whole cottage industry of people who are doing these things.

Yes.

I have a question for the three, two slides before.

Is the reason that we go one step deeper than the normal step of the other sub-trees, is

this only because this is an example?

Yes.

I've doctored the example so that I can show a certain pruning step.

Normally we have the same depth for every sub-tree.

No, no, no.

That's not true.

Think about chess.

If you kind of march out your king into the enemy's territory while they still have a

lot of manpower, then that's going to be a short game.

So usually game trees have uneven depth.

The only reason we've been using even depth is because it fits so nicely onto the slide.

That has nothing to do with the real world.

Thank you.

More questions?

Okay.

Good.

So, completely different strategy going from systematic search essentially, which is nice

because we can prove good things about it, which makes it ideal for PhD thesis or so.

We now go to something where it's much more difficult to prove things about, but which

can handle kind of bigger things.

It's called Monte Carlo Tree Search.

It kind of consists of two parts.

Tree search is what we know already.

Whenever you add the word Monte Carlo to something, that means we do some randomness in there

somehow.

Okay?

And this is interesting because that's really what AlphaGo uses.

So AlphaGo really is Monte Carlo Tree Search plus neural networks.

When you're unsystematic, that can be great.

If you unsystematically do the right thing, wonderful.

You don't have to remember anything.

It becomes very easy.

Great.

If you unsystematically in the lottery hit the right number, wonderful.

You're going to be rich.

There's no guarantee.