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...

From the course by University of California, Santa Cruz

C++ For C Programmers, Part B

53 ratings

University of California, Santa Cruz

53 ratings

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.

From the lesson

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.

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.

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.

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.

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.

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.

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.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.