This course will cover the mathematical theory and analysis of simple games without chance moves.

Loading...

From the course by Georgia Institute of Technology

Games without Chance: Combinatorial Game Theory

91 ratings

Georgia Institute of Technology

91 ratings

This course will cover the mathematical theory and analysis of simple games without chance moves.

From the lesson

Week 2: Playing Multiple Games

The topics for this second week is Playing several games at once, adding games, the negative of a game. Student will be able to add simple games and analyze them.

- Dr. Tom MorleyProfessor

School of Mathematics

Welcome back. None of these, none of these. You know the rules by now, no random moves. I'm Tom Morley. Last time we were looking at these two games. The left is a cutcake. And I always have to remind myself, right cuts this way. Left cuts up and down. And the right game is a Hackenbush. It's a very simple game. Left has one move left and cut this left branch. Right has no moves. Left goes first, left wins, right goes first, left wins. Left always wins in this game here. These are two games G and H. We want to know, is G equal to H? And to do so, we have to look at G minus H and see who wins. If this is 0, then the games are equal. To say that this is 0 means that and minus H is, of course, an abbreviation for G plus the negative of H. We'll go ahead and just write it that way. And, and, say this is equal to 0, just means that, that whoever moves first in this game loses. So, we have to analyze the strategies in best play in G minus H. So, let's look at G minus H. G minus H is cut take over here. And the Hackenbush over here. But the negative of the Hackenbush is this. Now you, let's look at right, what happens when right goes first. Okay. So, let's look at right going first in this game. The best move for right is to chop down the cherry tree in order for Presidents' Day, which is coming up, except by the time you see this it's already passed left's best move at this point is to chop this in half. Right then has to take one of these 2 by 2s, it doesn't matter which one and chop it in half. And now look, look and see what's going on. Left has one, two three moves and right doesn't have much. So actually, there's a little bit more work to be done here, but left has lots more moves here than right ultimately does have. And so, it turns out that, that, that in fact, right loses. And there's a, there's a bit more to, in, in, in the whole process, but you can puzzle that out and, and, and try it yourself. You also might want to try if right, if left goes first. Left goes first the, the, the easiest move for, the best move for left going first is to chop up and down in the middle but still, left loses. So in this combination game of this cut-cake and this hackenbush, the sum is first player lose. The sum is zero and therefore this game here happens. Okay so we've done a couple of simple examples. One thing that we haven't done which you might think about is, is so that any game is equal to itself. That is to say any gain minus its negative equals zero. And the basic idea of showing this is what Conway and, and friends call Tweedledum, Tweedledee principle. If you have a complicated game over here, that it's negative over here then whatever one player does over here, the other player will do the opposite over here. Whatever one player does over here, the first, the other player will do the opposite over here. So, what that says the second player to move always has the advantage because there's always, always will be a counter. Whatever you do in one of these, the other player does the opposite in, in the other one. The branches over here that are right branches over here are left branches. The branches over here that are left branches are over right branches. So, if left moves over here, then right moves over here, for instance. So in general, this says any game is equal to itself, a not terribly surprising thing, but that's how we'll end the first week. And we'll come back check out some problems for you to work on in the, the homework/quiz, it will let you now how you're doing in the course and we'll go over them afterwards. So, take care.

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