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.

Loading...

來自 University of California, Santa Cruz 的課程

C++ For C Programmers, Part B

70 個評分

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.

從本節課中

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

This session we're going to detail in our term project,

which is implementing the game of Hex and using AI techniques to produce and

intelligent opponent and

as the techniques, we're going to use and they C++ world.

We're going to talk about inheritance.

Inheritance is a hallmark feature of object oriented programming.

So the Hex ideas

are the ideas that relate to our termed projects as sort of our final projects.

Pièce de résistance.

All of you out there are going to become a game designer and

know how to do things that allow the machine to play intelligently.

And among the critical software

methodology techniques in a language

like C++ is the use of Polymorphism,

code sharing through inheritance.

Hex, so we're going to discuss the game of Hex in some detail.

The first thing I want you to be able to do in your next

assignment is to produce a working program that plays legal Hex.

Makes legal moves.

Your program needs to be able to check that a move

that's being made is legal, and that it can make a legal move.

So it has to know that the opponent is making a legal move, and

knows how the game is won.

And then in this first version of the code,

I want you to use some fairly elementary playing strategy.

And recall that Hex is a game of connectivity.

It's what might be called a more complicated variant of tic-tac-toe.

And when you're playing connectivity games, namely, I have to

make a path across a map and I have to block you from making a path across a map.

The two critical strategies are offense,

where I extend my path and defense, where I keep you from making your path.

So one place to look for ideas in how to conduct

some intelligent way game playing in this environment,

is to see how to detect what makes longer paths for you and

what blocks longer paths for your opponent.

And here are some of the Hex ideas and there are many sites where

both you can play Hex, so if you haven't played hex,

you should get on Hex site that lets you play an app and give you some experience.

And you can also read about the game.

And one of the critical ideas in the game that you'll find, and

again, a very good place to build into your program,

the kinds of moves it needs to look for are what are called in Hex bridges.

So two groups of stones can be safely connected on the board, showing over here.

So one of the players is the blue player.

And the blue player is going from north to south.

And the red player might attempt to block

the blue player in their next move.

But if the red player tries to block by putting a stone here.

They can only block in one position and then when it's the blue player's turn,

the blue player can immediately do a connection.

So in some sense, it's okay for

the blue player to skip this row for the moment, and

only respond to the red player when the red player makes a blocking attempt.

And the character here is that this is called a bridge.

And so you can play the game by jumping down the board,

assume again that you're the blue player.

And you're going down the board, so you're making connections on the board like this,

and then you're leaving some spaces, and then you're making further connections,

and over here, you can always respond to some blocking attempt.

So when you write your program, we've so

far in the course done a lot with graph theory.

So a natural kind of representation of the Hex board is as a graph.

Now here, on this slide, we see an 11 by 11 Hex game.

So normally, when people play Hex,

they play Hex on boards that are N by N.

And very typical for championships is n equals 11.

And sometimes, it's larger than 11.

It actually turns out that if n is nine or

less, computers at this point can play perfectly.

But if you make the game large enough, the game gets combinatorially too large for

even really super computers to figure out best moves.

Now, we're going to in our homework represent this already as a graph.

Why? Because lots of what we're doing is

exploring paths.

And remember, we already did way back when, Dijkstra's shortest path algorithm.

Some sense Dijkstra's shortest path algorithm is foundational

in exploring an intelligent way to move across the board.

So again, we have two players.

In this case, the red and blue players.

And blue was going up east to west and red here is going

north to south, and they're trying to connect to the two boundaries.

The game can't be a draw, it turns out that

who ever makes the path blocks, the other player's path.

And there's no way to have a mutual blockage.

So there can't be a tie.

And in this case, we have 121 nodes, so we need a representation.

And it's very useful to think of this as a two dimensional space in which.

We have coordinates and the upper left-hand corner is (0,0),

so, that's this node, and then we go all the way

down here and that's a node (10, 10).

So, again we're using secant ventions we're starting our indexing at 0.

Moving along, we can go from

this node would be (0,10).

And that would actually be node if you want to think of it the 11th node.

So this is the first node, second node, third node, fourth node,

fifth node and so on.

And that's now we're going to try and represent it in our computer program.

When you try to accomplish this mapping and this mapping should work for

an arbitrary end by end board, so you should think it out, so

it works not just for 11 by 11 but here, we're going to show you how to do it for

11 by 11 and one of the things I want you to think about when you

do this on your own is think about what you need to do for end by end.

Critical to doing this two-dimensional mapping

is going to be the use of the remainder operator, so

again, people are always making mistakes with the remainder operator.

They're always forgetting how remainder works.

So you really want to make sure you fundamentally understand

the percent operator, or remainder operator.

So this is a binary operator, it's a binary arithmetic operator,

it's a binary integer arithmetic operator and the idea is 3 remainder 10 is 3.

35 remainder 10 is 5.

Why?

If you divide 10 into 35, the whole number part would be 3 and

then there's a remainder of 5.

So it's just how you learned in elementary school to do division.

Now, when we look at mapping from i and

j into a square, we can use this formula for a node number.

So, recall.

If we have 0,0, then i is 0 and j is 0.

So you'd get 0 times 11 plus 0.

So the first node would be labeled 0.

It'd be equal to 0.

The last node which is 10 by 10, would be 10 times 11,

which is 110, plus 10, which is 120.

So you end up with 121 nodes, again labeled starting at 0,

121 nodes in this description, if you implement your Hex game,

the way I'm suggesting you should.

You're going to end up with a graph for an 11 by 11 board of 121 nodes.

And it'll be really easy to go between the two dimensional representation.

Which you probably want for purposes of drawing the board.

because you want to be able to play against your program.

And that means you're going to have to develop

a drawing program that'll show you where the pieces are placed.

And that will probably be naturally done with the two

dimension representation and then you'll want to do

all of these internal computations, like a dijkstra or

a path algorithm computation using your graph representation.

Okay, so let's see if you understand this.

Here's a brief quiz.

What node is the square (3, 5)?

And conversely, what square is the node 21?

Take a second.

Write in your answers.

(3,5) is the 38th node.

Recall, you're going to start here at node 0, there'll be node 1.

You're going to go to node 10.

This is going to be the square, 0, 10.

And then you will have in the column 1,

0 you'll have the 11th node.

So this will be the 11th node.

And so on.

So.

(3,5).

Why does (3,5) get you 38?

Well, you have three rows.

And they go to 33 nodes.

And that will mean that the last node on the third

row that gets labeled will be node number 32.

And then you'll start the fourth row, and

3 5 will be 6 into the fourth row.

It's going to be that node and that will be node 38.

And again, if you were to multiply 3 x 11 + 5,

just using the formula would also see that you get node 38.

So you could either do it by counting physically on

the board and finding your at node position 38 or

showing that the formula works, you just use 3 x 11 + 5.

Now the other way, the mapping works in the other direction.

So, 21 divided by 11, get's you, entered your part 1.

So, the 21st node,

is really node, and

then the other part of that is to do your integer remainder,

and that remainder of 21, remainder 11 is 10.

And so the coordinate there is 1,

10 and again, you can see that that's the 21st node.

This is a 0th node at 0, 0.

You move over to 0, 10.

You go over to 1, 0.

You move over to 1 comma 10.

This is the node number 10, this is node number 11,

and so on, and this is node number 28.

So indeed, the inverse formula's also working.

Make sure you understand that and make sure you can do that.

For the general end by end case.