We'll now go into a very simple idea which is surprisingly powerful.

Remember Minimax, we max, we min, we max, we min systematically and propagate the utilities

back up.

Turns out that this is wasteful.

So say we're in this situation here.

So Max has the choice here, somewhere down in the game, and Max has chosen to go left

here.

So he looks at what Min will be doing and Min will be giving a value of n.

Now if we're exploring the search tree further, so somewhere we're getting down in the search

to this node, we'll call that B, and then we see that Min node B, and we see that Max

can force a value m which is smaller than n.

We don't even have to look at this.

Why?

Because Max is always going to choose n here because n is bigger than m.

In particular, Max doesn't even have to look at this subtree here.

That's called alphabetic pruning.

Pruning comes from agriculture meaning to snip off branches from usually wine plants

and vineyards or kind of cherry trees and so on.

And that's what we're doing.

We're snipping off branches that are not fruitful.

This is the idea.

It takes a little bit getting used to, but let's look at this.

We have Max here, and Max has kind of explored this subtree and found out that Min cannot

prevent a 3 here.

The question is what do we have to look at?

Say we've explored this whole subtree, we're going down here, and we don't know the 2

yet, because that comes up.

We see a 2 here, and then we don't even have to look at these 4 and so on because we know

that 2 is smaller than 3.

We only get the 2 here by looking down here.

So this is really what we need.

We know at this situation that Min is going to be lesser equal than 2, so there might

be 1s and so on where Min can actually force it even further down, but we don't even care.

We have a 3 here.

So here's really that we can prune stuff.

There's stuff we don't have to look at, and this losing 2 branches down here may actually

look like a small deal, but let's think about we have kind of 10 levels down here, which

means even with a branching factor of 2, we're losing something like 2,000 or so nodes here,

which is nice.

That's the idea.

What we need to do here is we need to reformulate our algorithm so that we can remember this

value 3 that will guide me here.

So we need to add a little bit of memory, just one number in this case, and we'll just

call that the alpha parameter.

So in the beginning, just like we did for min-max, we keep our value of what we can

– our maximal utility value, but we're going to have an alpha value as well.

Alpha because it's the first letter in the Greek alphabet.

So we both initialize them to minus infinity because we know nothing about utilities yet.

That's the worst that maybe we could get.

So we look at the min-node, and min, we have to assume, can actually force plus infinity.