This course will cover the mathematical theory and analysis of simple games without chance moves.
Cutcake and Adding Games
Loading...
En provenance du cours de Georgia Institute of Technology
Games without Chance: Combinatorial Game Theory
124 notes
Explorer les vidéos de cours associées
Vous trouverez chez Coursera les meilleures vidéos de cours du monde. Voici quelques-unes de nos recommandations personnalisées pour vous
À partir de la leçon
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.
Rencontrer les enseignants
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.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2019 Coursera Inc. Tous droits réservés.
