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

72 個評分

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.

從本節課中

Monte Carlo Hex Program, Further advanced C++ Topics and Patterns

This module shows how to use Monte Carlo evaluation in complex games such as Hex and Go. This had led top championship level play in both these games. The module discusses C++ assertions and exceptions for error handling and the new C++ 11 feature static asserts. Finally, the last part of the module introduces the idea of “Design Pattern”, a feature of modern OO programming.

- Ira PohlProfessor

Computer Science

Here are some simple ideas.

Take a board, fill it from it's empty position with an equal number of red and

white stones equally distributed.

That's easy to do by the way.

If you are proficient in the use of the standard library,

you will notice in the standard library

that there is a pre-existing routine called the shuffle routine.

And if you shuffle all the nodes and

you have a data structure that's keeping track of the nodes of the hex board.

And you shuffle them, and you fill the first half of them with white stones and

the second half with black stones.

Then you've accomplished your random placement on the board of the white and

black stones.

So let me suggest that that is the method you use.

You don't have to use that method.

You could use the method where okay, I'm going somewhere at random in

the remaining empty squares that in placing a white and

then placing a black and taking alternate turns and placing white to black stones.

But then you're going to have to keep track of

all the coordinates of what remains empty.

And could do that readily but as they say might as well take advantage.

One of the things you're benefiting from this class and

we hope is a much better understanding and insight into the standard library and

it has relevant routines that let you do this efficiently.

So, The position is going to be one after you fill out the whole board.

I've already mentioned that, that's an optimization,

that's an important optimization.

And then the test thing, the Dykstra's algorithm only needs to occur once.

So rather than have to test 120 times on the 11 by 11 board,

you pass once at the end.

Even though you have to make more moves but making moves is cheap, really cheap.

So this is a big computational way, it's a breakthrough computational way and

it's not obvious.

How do we specialize Dijkstra?

We've already gone at length into the Dijkstra algorithm.

And the Dijkstra algorithm is a critical path finding algorithm underpinning

lots of stuff in computer science and it's a canonical greeting algorithm.

So understanding it, understanding algorithms like it, that's a takeaway.

I hope that's a real value though hopefully you came into the class

knowing that background already.

So winning amounts to seeing whether one player,

you can just assume on this full-up board.

If North/South hasn't won, let's call him player 1,

then it had to be East/West that won.

That's from the nature of Hex.

So all we need to do is examine whether

there is a complete path from the North boundary to the South boundary.

So here's a basic hex graph that I suggest you try to use.

Not required so if you write something that's as good or better or

your own, fine and dandy, I'm not unhappy with that.

But for those of you who need a little more guidance, this may be of value.

So this is code that I generated to do the problem.

And again, I have a general graph but I'm going to have a constructor.

I'm not going to worry about other constructors for the graph.

I'm going to have a constructor that's given the hex size of the graph.

And that hex size is one dimension.

So it's 11 when you have an 11 by 11 graph.

Now don't forget when you have an 11 by 11 hex board, or a 5 by 5 hex board.

Let's take the 5 by 5 case.

You have 25 nodes, so the graph is really the hex size squared, the graph size.

The number of nodes, the number of actual squares,

is the side because it's basically this hexagonal square, square.

And the other part of our interface is not only the constructor for

the hex board, but who won.

This is our specialized path algorithm.

And then internally again, you can do this in other ways.

I chose to use a vector or

vectors and

then that will be how I store my graph and

the graph will be for each node there will be a vector of edges.

So here's the zeroth node, and here's our vector of edges,

all the edges out of that zero node, 3, 7, 9, whatever.

24, however we're, in our board size.

This is the actual board size.

So it's going in effect when initialized

from this constructor, be A size squared.

And then we're going to have a simple representation of,

in each, square related to the graph node,

each square can be either 0 meaning empty, 1 meaning a white stone,

2 meaning a black stone, or whatever colors you like.

So we have those three states and

indeed one suggestion is to turn this into an enumerator.

So if I wasn't lazy in my own code I would have probably made

this its own class and then had three values empty white black.

To implement the who_won algorithm,

we can either use a specialized form of Dykstra,

that looks for a path between north and south or east and west.

Or we can use classically the union find algorithm.

Either one is appropriate, either one is okay for this project.