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

113 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

>> Alright, welcome back. None of this, none of these, no dice, no

Â cards, games without random moves. Now, now that we know from last time how

Â to add things up, add up games, maybe we'll play them simultaneously in the ways

Â we described last time. We want to talk about what it means for

Â two games to be equal, which is going to mean something like, whenever we play

Â these games together with some other game, the same thing happens.

Â Now, I want to be much more precise about that in a minute.

Â But that's esesentially what's giong on. And so, to start this, I want to start

Â with a simple, a very simple case. And our definition of win a game is 0.

Â This is a definition and mathematics definitions are prescriptive, that means

Â they're, what is the case. Okay.

Â So what does it mean for game to be zero and this means in best play, the first

Â player to move, loses. So, just like the zero game, whoever moves

Â first in the zero game, loses, because there's no moves.

Â Let me, let me show you. The zero game happened to bush is this.

Â Nothing to cut. The zero game in, in a heap, is a heap of

Â zero coins, which you can see over here to your left.

Â And so that's the zero game. And then, we'll say the game is equal to

Â 0, if in best play the first player to move loses.

Â Okay, let's look at an example. Nim-heap of size 2 over here, nim-heap of

Â size 2 over here. It just matters that there's two dice over

Â here, two dice over here, the numbers on the dice don't change anything.

Â So, so if, if left, whatever left does over here, right does over here.

Â Whatever left does over here, right does over here, and left loses.

Â So, if left goes first, left loses. Similarly, if right goes first, right

Â loses. So, this game 2 nim-heaps, a nim-heap of

Â size 2, which we now take this way, plus a nim-heap of size 2, is first player lose,

Â so it's equal to 0. Okay.

Â So, we know when a game is equal to 0. So now, let's look, let's try to see what

Â a negative of a game is. We have a game, G.

Â We can compute, have an associated game called minus G.

Â Now, let me show you this for hackenbush. Say, this hackenbush game is G.

Â Then, minus G is the same thing with left and right interchanged, okay?

Â Now, let's look at other possibilities. In, in cutcake, remembering that right,

Â cuts left to right, and left cuts up and down.

Â Then, if that's a game of cutcake, if we'd simply interchange rows and columns, then

Â whatever became a, a, a possibility for left is now a possibility for right, and

Â whatever became a possibility for right is now a possibility for left, okay?

Â So, the negative of this cutcake game is this game.

Â The, the negative of, say nim-heap of size 3, is now interchanged the versions of

Â left and right, but since left and right are, are, have the same moves in them, the

Â negative of this is the same, same as, as that.

Â So, the negative, let's do it, of nim-heap of size 2, is a nim-heap of size 2.

Â Interchanging left and right, a nim doesn't do anything.

Â What is it in chess? Well, the negative of, of, the negative

Â chess game is a game, a chess game where black goes first, I guess.

Â Or maybe it's the negative of a chess game is where instead of you having white, you

Â have black. So it's the interchange of the, of the two

Â sides. Left becomes right, right becomes left,

Â black becomes white, white becomes black, whatever the, the moves in the game are.

Â In Go the negative of the game, which is corresponding to a different player going

Â first. So instead of white stones, you have black

Â stones etc., etc. So, that's, that's how a negative of game

Â is. And now, we're ready to, to define G

Â equals H, means G minus H is 0, or G minus H is just an abbreviation for this, okay?

Â We'll look at some examples. For next time, this is a short one.

Â Let's just take a look at, I'll give you an example to, to work on yourself.

Â Let's look at a cutcake and a hackenbush, and my claim is, are these equal?

Â Try it out and we'll see you next time. Take care.

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