So if you can identify the end of the game,

that's one way to go about evaluation.

Not always possible because to say if the trees are deep enough,

you may not get to a point in which you would have such an endpoint,

and then you might need some other evaluation function.

For example, in chess

the typical evaluation function taught to beginners is adding up material.

So there was a famous book that I learned chess from at

the very beginning which was called Point Count Chess.

In a point count chess you're taught a pawn is one, a knight or

bishop is three, a rook is five, a queen is nine.

You can't place a value on the king, cuz losing the king in effect,

checkmate is the end of the game.

So you just add up your pieces and subtract your opponent

pieces if you have them, the material balance is zero.

So by that rule of thumb, exchanging a bishop for a knight is leaves a balance.

But if I can exchange a bishop for a rook, I'm up two points.

Or if I can outright capture a piece like a queen, I'm up nine points,

which is almost in all cases, a winning advantage.

If we were playing backgammon,

the backgammon game is a game where men race around the board and

try to bail off on the ends of the board.

And so a typical measure of who's winning is counting how many

squares remain to complete the race and whoever's ahead in the race

at a simple level is typically thought to be winning the game, but

those are very simple when you get in to either more advanced backgammon or

even more advanced chess, there are other factors that come in to play.

Like in chess, there's the factor of the initiative,

there's the factor of space advantage.

Backgammon is factor of blocking situations on the board.

So these very simple ideas while they give you some insight into how to play,

they have to be modified if you're going to create

a better and better AI to play those games.

So here's the usual model.

You have move generation,

you have something called look ahead and

this is what I'm gonna focus on in this course.

We've already seen min-max and

the next segment I'm gonna show you a more refined and

algorithmic way, efficient way that implements

the equivalent to min-mx called alpha-beta.

So alpha-beta is just like sorting, there are several ways to get the same result.

Alpha-beta is a way that you can do min-max,

but do it way more efficiently.

So that's to be preferred though, min-max is a little simpler to understand.

And then we're gonna look at a much,

a radically different approach called the monte-carlo approach.

We've already seen monte-carlo algorithms, these are algorithms

in which we're simulating with some set of probabilities situations and

it turns out we can use a monte-carlo simulation

on the board to get an evaluation and that's actually startling.

We'll talk some more about that when we come to the monte-carlo approach.

So the usual model, you have to have some way of evaluating static positions.

That of course, will depend on the game and you get that out of the literature.

So what might be the game in Hexes who has the longest potential

path across the export, that's the person in the lead.

If I have a longer path than you, I'm probably ahead of you.

If you can't block that path, I'm going to win.

So, a longer path is a critical way

to evaluate a Hex position.

In checkers or chess, there's material count and backgammon,

we just talked about it.

There's some kind of notion of who's ahead in a race.

This is also backgammon, Something called points made on a backgammon point.

If you have two checkers of your color, you own that point and

owning that point allows you to block the other player's opportunities.

So points made become a more sophisticated view of

what you're doing in playing backgammon.

In Hex as we say, if we're on a standard board,

we're looking to see who's got a payout

that's nearly on an 11 by 11 board 11.

So that's our usual model.

Now in implementing your first version of the Hex program,

I want you to think about some effective way to do plausible move generation.

This is to say, you can read about min-max and alpha-beta,

get more information about how do the evaluation, do the algorithms and

the plausible move generation, you can also read on Hex and look at bridge moves.