This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.
3.5 Plausible Move Generator
Loading...
From the course by University of California, Santa Cruz
C++ For C Programmers, Part B
77 ratings
From the lesson
Hex and the use of AI and C++ Move semantics
This module explains Min-Max and the Alpha-Beta algorithm for game playing. Its programming topics include C++ 11 Move semantics and a detailed example of referential garbage collection.
Meet the Instructors
Ira PohlProfessor
Computer Science
Now again, Hex is going to be a very large game.
Why is it gonna be a very large game?
Well, we're expecting to play tournament Hex on an 11 by 11 board.
An 11 by 11 board has 121 positions.
So that means initially a player has 121 legal moves.
And that decreases one by one.
So for the longest time in the game your branching rate,
your legal branching rate in the game is over 100 moves.
That means even a relatively short ply like ten ply,
making ten moves, that's gonna be ten to the hundredth, very large number.
So in most instances, we're not going to be able to take such a tree, develop it,
and then apply some evaluation criteria, even a simple evaluation criteria.
The number of moves and possibilities are too large.
So we have to limit them.
And typically you limit them with something called
a Plausible Move Generator.
Now, in early chess game programs, chess,
as programmed on the computer, goes back to the 50s.
Actually, programs written in the 50s, that would play the game of chess.
Not very well, there were paper algorithms for playing chess even before.
Some of the most famous computer science and information scientists,
like like Shannon, like Touring,
all wrote papers on ideas in playing chess algorithmically.
They were all interested.
All these creative thinkers that really are the foundation thinkers for
computer science like Turing were deeply enmeshed in thinking about
how you could create an intelligent chess player.
Chess has this average 40 moves per ply.
The early chess programs that number,
plausible move generator was typically something around five to seven moves.
How would you decide to pick those moves?
Well you go to the literature, you would do what chess players do.
Chess players themselves, a very famous study by Dutch master and
cognitive theorist, de Groot, found that even chess masters
possibly only look at a few hundred positions in making an evaluation.
So they generally are very selective in their plausible moves and
the plausible moves in the beginning manuals talk about
capturing material, which is also true in checkers.
So you'd examine captures.
In chess, critical moves are check,
the old chess saying is why not check, it could be mate.
So, even beginners occasionally beat better players
by using these very simple ideas,
because just humans playing chess make many mistakes.
And they may overlook that there's a check in the position,
and conceivably the check is mate.
And then in different phases of the game,
in the early phase of the game, there are typically special rules.
So in the early phase of the game special rules include move your pawns
to the center, why?
Cuz control of the center is one of the important theoretical elements
of chess play.
And when you move your pawns to the center, not only do you gain control, but
you give more space to your background pieces.
So at different phases in the game, there might be different rules for
generating plausible moves.
In the later phase, in the final part of the game, in the endgame,
there's a lot of attention paid to advancing pawns called passed pawns.
And so in that phase of the game if you have a protected pass wand, that may be
a plausible move because converting a pass wand to what's called queening square,
on the opposite row, would again be a very high value and a game changer.
Hex you have to examine similar things.
So what would be useful in Hex?
Well, again, you can consider it part of your homework,
there are many Hex playing programs already on the Internet.
If you don't know the game, try and play one of those programs and
you get a sense of how these programs play.
Some of these programs are very good or
it will be frustratingly beat you over the head.
But maybe you will get some idea about what you're doing and
you can develop some of your ideas.
And plausible plays.
Which is analogous to playing an extended tic-tac-toe game,
is play towards the center of the board.
The center of the board, center of the X board, let's you have more opportunities,
or more ways to extend paths and block your opponent's path.
Okay so let's try and study plausible moves.
Here's a position game in 2011 between a random game I found on the Internet.
And the question here is white's to move.
And what's a good move?
So again, if you tried to look around at all the legal moves,
well there are legal moves like moving this.
You could think about moving this pawn, that's a legal move.
Good move at one or two.
You could move this pawn one or two.
So that's already four moves.
There are two pawn moves here.
So that's eight moves.
There's one, two, three, four, five, six, seven, eight bishop moves.
And then the queen has a whole bunch of diagonals.
So there's about three or five, six, seven,
eight, nine, ten, 11, 12, 13, 14.
14 queen moves.
This has about five rook moves.
This has about ten rook moves.
So you're looking at again, as we say, roughly speaking,
30 to 40 moves in this position.
Well, plausible move generators in the early style of chess would
say look at captures, look at checks.
Now, if your a chess player of any kind,
you'd recognize this is a very dynamic position.
Queen is being threatened, not a great thing.
The bishop's being threatened.
There's a pin on the king.
[COUGH] But white has some form of attack.
So.
A reasonable attempt would be a capture, and a check.
And that capture and check accomplishes a couple of things.
What does it accomplish?
Well, it's forcing.
So that's another thing that makes it easy to evaluate.
Once there's a check, the king must either block the check,
have the check blocked or take the checking piece or move out of check.
So if we look at this work page pawn capture.
We can't move the king away because
the queen is protecting the one square that could be moved away.
That's critical to this combination.
We could place the opponents queen here and block.
But then, all that we would have to do is queen takes queen and we'd be mate.
So you wouldn't do that.
So the obvious thing to do, is to capture.
Cause this leads to immediate mate.
Capture.
And the only capture opportunity is pawn takes pawn.
And here's where there is,
if you're a chess master, a standardly known theme.
Once that capture's happens and there's the re-capture this way.
This square becomes available for the bishop.
The bishop placed over here has king under a check again.
So again, notice the checks and captures are very powerful moves.
At this point, there's only one way for
the game to be saved,
and that's moving the queen over and blocking the square.
And then the bishop can take the queen, check, and it's still check.
Now, again, the only move is a force move.
King takes, and now we have a relatively easy
winning procedure.
We can just play queen takes look,
check, no not check excuse me.
With this rook being the last piece of any significance
the bishop is here and then our rook takes the queen.
Rook takes rook and now this player has an extra rook,
a bishop, and extra healthy pawns.
So the game is over.
So, I see that this is actually the wrong idea.
King takes,
this should've been
queen captures
rook on E8.
And plus plus just means, with winning advantage.
So at this point, it would be very easy to have a static
evaluator because you're up a full rook.
A full rook, in the general theory of chess, is worth five pawns.
And that's by far, in a simple position like this, easily converted to a win.
So that's how both a master would play and a computer program.
And actually, this is a very simple dynamic situation that almost any
computer program, starting in the mid 70s, would have played correctly.
Before that, it may have been
more variable as to whether the early program's in play.
If you recall some of the history of chess programs,
they got to master status in the 80s.
They got to average club player status in the early 70s,
and then they got to world champion caliber in the 90s with
the famous match with Kasparov IBM Deep blue.
Can spar off in the famous one million dollar match in 1996.
So now, turning to hex, how am I gonna think about hex?
That's your assignment.
You have to produce this kind of AI for hex player.
Can I make a winning move?
Here are some of the questions you might say that would generate plausible moves.
A winning move is a move that completes a path.
If you're a north to south player,
is there a move on the board, that lets you link up a path.
Do I have my opponent almost ready to win, but I need to make a blocking move.
So if I don't have a winning move but my opponent has
in their next turn a winning move, I'm going to make a blocking move.
If I don't have something that critical then there's a way for
me to extend my longest partial pay-off.
Similarly there's the inverse.
Can I block my opponents longest path?
And then if you've looked at hex literature at all, you'll see there
are things called fancy moves that involve what are called bridge positions.
And you may wanna try to make or extend with a bridge move, a potential path.
Okay, so that would be a way to build some AI into your first version
of your Hex program, by trying to generate moves of this sort.
Again, another overall rule in this kind of game is moves in the center are of
more value than moves on the periphery because they lead to more possibilities.
Now evaluating, well, in some games the games are fairly simple.
So, in tick tac toe uou just see who won.
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.
So bridge moves and center squares.
Path extension.
All of these should give you some ways of generating plausible moves and
then you need some evaluation of a resulting static,
what might be called leaf node.
And in Hex, that's probably going to be something
based on viewing what the longest potential
paths are for you versus your opponent.
So next time, we're going to go into the details of the alpha-beta algorithm and
show how to implement a more efficient algorithm than simple mini-max.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
