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.
2.1 Tic-Tac-Toe to Hex
Loading...
來自 University of California, Santa Cruz 的課程
C++ For C Programmers, Part B
76 個評分
從本節課中
Hex as a graph and Inheritance
This module shows how Hex can be played as a game on a graph. This involves its representation as an undirected graph in C++. The module explores the inheritance logic and syntax of C++. A principal example is the base class student and a derived class grad_student.
與講師見面
Ira PohlProfessor
Computer Science
[MUSIC]
Welcome back, today's lecture is going to be on our term project,
how to implement the game of Hex, how to have a challenging
machine program that utilizes artificial intelligence,
how to embed all this in a C++ program.
And we're going to continue with the topic of inheritance in C++
inheritance is the hallmark idea behind object oriented programming
and then we're going to also continue to emphasize some of
the latest ideas in the new C++ 11 standard.
Ideas especially that relate to inheritance this in this case.
Okay, we all learned as a child how to play tic-tac-toe.
So here's a tic-tac-toe position, it's X's move.
X goes first, where should X move?
And what's the result of the game going to be?
I want you to think about it.
Where would you put X if you were the X player?
How would you decide it?
So I'd like you to answer what you thought x's best move in the last slide is.
If you know something about two person games,
you have an idea of what should be filled in.
Tic-tac-toe is a game of some kind of information
and with best play is tic-tac-toe a win, a draw or a loss for x?
And if you were to start with a blank board in tic-tac-toe what do you think
the first move for x should be, what would be a first best move?
Just think about that, may not have played tic-tac-toe for
a while but think about what you would answer.
Okay, here's what I think a first move in
that initial position should be If you put
your x there, you guarantee two things.
One, that you block any possible wins for
o, because o can only win on the bottom line.
Secondly, you have the possibility of winning as x,
because there's one place where x can win, as the top line.
Tic-tac-toe is game of perfect information.
In contrast poker is not a game of perfect information.
In a game of perfect information,
the opponents see everything that lets them make a decision.
There's nothing hidden.
Poker you have each opponent or multi opponents which have hidden information
namely the card deck and what the order of cards are and what's in a particular hand.
So in a game of perfect information,
you should be able to decide what the best move is.
Well, in tic-tac-toe, if
people play perfectly from the beginning, the game is always going to be a draw.
That's easy enough to prove.
It's probably why most of you stopped playing when you were five or six,
because it just got too boring.
And if you were to decide on a best move when you are playing as kid,
you probably quickly learn that the best move for the first player,
the x player was put the x in the middle.
And why was that?
The x in the middle gave you the most possibilities,
gave you the most opportunities for win and it gave the other player the most
opportunity to loose, the worst moves were the middle of the side boards and
the intermediate quality moves were the corners and
each one gave you more possibilities, the most being good.
Move in the middle, the next most being corners and
the least being the non corner moves on the side.
Now, tic-tac-toe isn't too interesting, why?
It's a very small game, it's easy to exhaust, it's easy for
a child even to quickly figure out what a best strategy is.
But people still play tic-tac-toe like games.
Why, you can make the board larger.
So, a frequent style of tic-tac-toe is
playing on a very large board, like a Go Board.
A Go Board is a 19 by 19 board and
trying to get five in a row rather than three in a row.
That starts making everything a lot larger.
And it deemphasizse the importance of the middle square because there's
in effect lots of middle squares.
Another thing you can do to make tic-tac-toe more interesting is have more
dimensions.
Obviously tic-tac-toe is played on a sheet of paper.
As two-dimensional, but what if you play it three-dimensionally?
So now you have a board that's three boards and
they're like a ground story, a first story and a second story board.
Each board now is three by three so there's basically 27 squares and
now you can win by having a row or column on any board.
But you could also have a row or column that goes on the third dimension as well.
So it becomes more complex.
There are more squares.
There are more ways to win.
There are more ways to lose.
Just gets more complex in general.
The final way that I'm going to talk about to make the game more interesting
is to make the board more complex.
If you look at tic-tac-toe, the simple ways to win
are rows, columns and diagonal.
In the game I'm about to describe, Hex,
the board has got hexagonal, six-sided squares.
And the six-sided squares have six squares adjacent.
In the square board, you have at most four squares adjacent to you.
It's a square, a square is a square.
In the hexagonal circumstance, there are six neighbors.
In the square circumstance, there's four neighbors.
So when you have six connected neighbors, you essentially will have more places
that you can extend, your three in a row, your five in a row, your n in a row.
Here's a Hex board.
Hex was a game invented by professional mathematicians,
was invented separately by Piet Hein who is Dutch
mathematician who invented it first in 1942.
And then later John Nash who if you recall,
Academy award winning movie, A Beautiful Mind who won a Nobel prize.
He invented it while he was a student at Princeton Getting his PhD in 1947.
And here is a seven by seven board and
you can see the little hexagonals and
you can see there are white squares,
white pieces, black pieces and empty squares.
White and black get to take turns.
And white has its boundaries.
Black has its boundaries.
Think of Here's north, here's south.
Blacks, black,
Makes a path, From north to south.
In this case, black has won, because it has a connected path from north to south.
White was trying to make a path from east to west has lost,
because it's whoever gets the first path to win.
Game is actually fairly complex if you start to play it.
It's not as simple as just a small version of tic-tac-toe,
but it is has tic-tac-toe like elements.
So, let's be more specific.
Here are the rules.
Each player has an allocated color, red and
blue or white and black is conventional.
We just saw white and black.
Players take turns placing a stone of their color on a single cell
within the overall playing board.
The goal is to form a connected or
their stones linking opposite sides of the board which is marked by their color.
So one player is the north south player, the other player is the east west player.
The first player to get a connected path
between their two sides wins the game.
Now what's been found to be the case is the first player has a huge advantage.
It's like tic-tac-toe, you get to go in the middle.
You have the most possibilities and pretty much,
if you know what you're doing, it's guaranteed to be a win.
Indeed, Nash actually proves that on the general
hex board, if the first player plays perfectly, must win.
So this is, again, a game of perfect information.
There's no bluffing, there's nothing hidden.
And winning would occur if the first player placed, put their piece
in the middle, and the game continued with perfect play from there.
So it turns out that there's a way to avoid that big advantage, and
that's what's called the pie rule.
And in the pie rule you decide there's a first player,
the first player makes a move and the second player only on this move
can make one of two decisions they can say gee I liked your move.
So I'm going to be become the first player and you're automatically now the second
player or they can say I didn't like your move.
So I'm going to stay the second player and make what I think is a better move.
Why is it called a pie roll?
Well, remember when you were a kid and you mother had a pie or
ice cream and said, here, I'm going to divide up the pie into two pieces.
And I'm going to let Johnny pick the piece first.
And Mabel pick the piece second.
But Mabel can pick Johnny's piece if they want.
And that's just a way to ensure fairness and
well that really works at the one of them is supposed to cut the pie.
So it's an incentive to cut the pie as fairly as possible.
Because first player who actually cuts the pie and
if they don't make it as a good job then other player can take over there piece.
So with that rule, actually the game is very fair,
becomes a case that you want to make a move but
you want to make a move that's not quite bad enough that you will end up losing.
But is good enough that if you become the second player,
you a chance to win the game at any case.
Okay, some facts about the game.
Nash proves that first player wins without the pi rule.
And the proof when something like this.
Gee, if I make a move, how can I possibly be hurt?
So if the second player after I move, just picked some square, I made a move.
The second player then plays perfectly and wins.
Well, why not have me play the second player's moves?
I will be able to play the second player's moves with this one extra piece on
the board, one extra piece can hurt me so if the second player had a way to win,
the first player playing perfectly has to be able to use that same way of winning.
So what that tells you is the first player has to win.
There is no way to have the game a draw, because whoever gets a path,
cuts the other guy's paths off, there's no way for
a path to, where there can be a deadlock.
Where there's no way from one side to the other without conceding some other path.
So, it can't be tied like the tic-tac-toe game can be tied.
So the first player if played perfectly wins but
this gives no insight into what the first players moves should be just
a proof that the first player must win because going first
is an advantage and the game must be won.
So, in smaller boards, boards like size 7 by 7,
computers and mathematicians have been able to examine the game exhaustively.
And indeed, they have ways of knowing how to win.
One the board sizes, I believe by now up to eight by eight.
I'm not sure whether nine by nine is completely solved.
But when you have tournament play, both human and
computer tournament, they now start with 11 by 11 or greater.
Sometimes 13 by 13, sometimes 19 by 19.
And best play is unknown on this much larger sized games.
Indeed, the game itself in general on an end by end board
is considered to be NP complete, which means from a computational view,
it's not expected to have a simple polynomial type solution of any kind.
Okay, so here's the board I'm going to feature for our homework.
The homework I want you to do is to be able to play on
an arbitrary sized board but typically at least 11 by 11.
But in your, the bugging stages you should use something a lot smaller.
And when you're going to represent this remember we did a lot of
work in our initial class with graph theory.
So think of X as a graph, if X is a graph the individual squares are nodes.
So here's a node.
So that's where I'm pointing is a node.
And its adjacency or its edges are the other squares next to it.
And in that case there are six squares next to it.
If you're a node that's sitting over there on the edge,
you only had three squares adjacent to you.
So there are, in effect, on this 11 by 11 board, 121 nodes.
And the corner squares can be either connectivity 2 or 3,
where the upper left and lower right have connectivity 2.
And the upper right and lower left have connectivity three,
they're relatively weak moves and
the center off the edges have the most moves and
then intermediate are the edges that are on the rim.
Quiz, how many squares are connected if they're internal hexes?
And I shouldn't really say the hexes.
I already told you this, I hope you've been paying attention.
What hex position has the least connections?
And if each node is a square, or a hex, with the degree being the number of edges,
then what are the ranges of the degree of the nodes?
Take a second to fill that out.
Let me just answer that.
On the hex-board,
a hex in the corner can either be connectivity two or connectivity three.
And therefore, the connectivity of the nodes that make up the hex board
vary from the low of 2 to a high of 6.
And if we go back and look at the square,
then a rim edge, like this, has 4.
