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

124 ratings

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

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 to Week 2, games without, oops, what have we got here?

Dice. No dice.

Cards. No cards.

No cards. No cards.

No dice. No win moves at all.

Games without dice or cards. Combinatorial game theory, I'm Tom Morley

again. Welcome.

So, in the study of these simple games, what we need in order to look at examples

by hand, is a whole bunch of games. We have a couple that we've look at

already, and we'll look at again this week.

But I want to introduce you to a new game, new game.

It's called Cutcake. Okay, in this game, like all the other

games that we've looked at, the players are left and right, they move alternately

left moves, then right moves, then left moves, then right moves.

And the first player, who has no move at all, loses.

So, cutcake is played on squares like this, that's 2 by 2.

You could start off with a 3 by 3, a 10 by 10, a 6 by 4, whatever you like.

And let me show you the various moves that are possible just in this example, on a 2

by 2. Left always cuts up and down, right always

cuts left to right. We're actually looking at a couple other

cut games before we finish the course and we'll always use this convention, left

cuts, cuts up and down, right cuts left to right, okay?

So, if left goes for first here, left is, only move, possible move, is left to cut

the center seam here. Oops, left, left cuts up and down, I've

got that backwards. Okay, so left goes up and down, like this.

That leaves two pieces like this. Now, what is right's movement here?

Right doesn't get to cut in both of them, right has to pick one or the other and cut

in it. We see that they're approximately the

same, no matter which piece right picks. If right picks, say, the first one, right

cuts across like that, that's the way right cuts.

That leaves two pieces here. In both of these pieces, no cuts left are

possible. They've been cut into small squares.

There's this piece left here, which right has a cut in.

But remember, it's left's turn next, and left has no move.

Left loses. So in, in this cutcake, that's 2 by 2, if

left goes first, left loses. You might want to look and see what

happens if right goes first. Try it out.

Try it out for yourself. Let's remember a little bit about

Hackenbush. And let me actually extend the game

slightly. Hackenbush you played on we have this

ground here which is green. The green grass on the ground.

And growing out of the ground is red, blue, green plant of some sort, okay?

The, the edges are red and right can cut the red edges, and the edges are, some

edges are blue, and blue edges can be cut by left.

So, right for red, right has an r in it. Blue for left.

Blue has an l in it. And the green edges can be cut by both

players. Now, this is, these green edges are new

from last time. And I'll try to point this out.

On some monitors, this, this looks very similar.

The blue and the green look very similar. I'll try to point when there's some

confusion. Okay, let's look at this, this example

down here we have this whole plant here. Suppose it's, rights move and right cuts,

by pencil mark, this right edge, this right edge then disappears and then,

everything that's not hooked up to ground also disappears.

So, once this, this, this red edge here is disconnected, this whole piece of the

plant here will die because it's not connected to the ground.

So, we erase all of that. So, players alternate right cuts right

edges or green edges. Left cuts blue edges or green edges.

Each time you cut an edge, that edge disappears together with everything above

it. And the first player, who can't move,

loses. Alright.

Now, it's fun to play one game at a time, but it's even more fun to game, play five

or six games all at once. So, I don't know let, let's play over

here, let's play a game of chess. Over here, let's play a, a game of go.

Over here, let's play I don't know, a cutcake of some sort.

Let's, let's, let's, let's play a hackenbush.

Suppose some of these edges are green and some are red, I'm not going to draw it.

I just mean this to be a schematic. Over here, we have a nim-heap of some

size. And let's play all of these at once.

Now, what do I mean by playing all of these at once?

Well, the players now alternate. But instead of playing one game or the

other, you pick one game out of the five, and they can move in that game, and that's

your, that's your turn. The other player, if you're left, say you

do that first, the other player, say, right, picks one game out of the five,

makes a move or not, okay? We know the following, even though the,

the players go left, right, left, right, left, right, left, right, in each of the

individual games, the players may not, the plays in that, inside that individual game

may not be left, right, left, right, because left might make a move in here and

then right moves over here and then left moves again over here.

So, in the individual games, we may not have left, right, left, right, left, right

alternation but in this, this combination game of playing these games all at once,

we do have left, right, left, right alternation.

Now, if these individual games are called G, H, K, L, and M, then, then playing

these games at once simultaneously, like we just went through is called the sum of

the games and is written just like ordinary sums.

So, G plus H plus K plus L plus M, represents the game.

We have these, these 5 games, I guess. Let's see, 1, 2, 3, 4, 5, I'm not very

good at numbers. But I think there's five games there.

We have these five games and then each player, left and right, in alternation

picks one of these games and makes a move in that one game.

Now, the first player who can't move at all, loses, just like we have in all our

other games. So you can't move after you're checkmated.

Go, you can't move after you lose. Cutcake, we know the rules for cutcake.

Hackenbush, we know the rules for hackenbush.

We have a pile of, of 4 coins here, so whoever move, once the coins are gone,

then there's no moves there. So, once there's no moves left in any of

these games, then there's no moves left for that player, and that player loses.

So, let's, let's maybe look at a an example, and try to play through part of

the game. So here, we have a cutcake and two

hackenbush games. And we've been looking at left first for a

while. So, let's do right first.

So, suppose right moves first by cutting this in 2.

Therefore, what's left there on the table is, is one of these and another one of

these. And now, it's, in some sense this is now 4

games. This game, this game, this game, and this

game. Now, it's left's move.

Left I don't know, what does, what does left want to do?

Let's say, cuts one of these off. And so, this now becomes, and now, we have

this game, this game, this game, this game, and this game.

Right has a move. Right, maybe, cuts this off that gets rid

of the blue also. Every, this, this all goes up in the air.

There's no moves left in that game. Left's move again.

Oh, I don't know, left might cut off another square down here.

And we can continue on left, right, left, right, left, right.

And I think in a move or 2, you'll see that left can win this game.

So, so, try that out for yourself.

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