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