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

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