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

99 ratings

Georgia Institute of Technology

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