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

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