This course will cover the mathematical theory and analysis of simple games without chance moves.
Toads and Frogs
Loading...
来自 Georgia Institute of Technology 的课程
Games without Chance: Combinatorial Game Theory
121 个评分
从本节课中
Week 5: Simplifying Games
The topics for this fifth week is Simplifying games: Dominating moves, reversible moves. Students will be able to simplify simple games.
与讲师见面
Dr. Tom MorleyProfessor
School of Mathematics
>> Welcome back. We have, what do we have?
We have, we have a straight flush. Small, small values.
But nonetheless, straight flush. Not quite in order, but you can check it.
We're doing toads and frogs now. You can, you can do this at home.
With people and it's fun play with people but you can also do it with, with coins.
Here's toads and frogs. Let's use nickels over here and Jefferson
nickels. Let's use Lincoln pennies over here.
Here's toads and frogs. The toads in this case are the nickels,
they move right and are controlled by left.
The frogs are the Lincoln cents, they move left and are controlled by right.
The toads can move one space to the right if it's empty.
The frogs can move one space to the left it it's empty.
But they also can jump over each other. A toad can jump over a frog, like this.
Note that the, the coin when you jump over isn't removed.
'Kay? But you can jump over and then they, then
say the Lincoln cent can move over here the, the nickel can do here.
The Lincoln cent can move over here My concern is the frog.
And we see at this point that neither the toads nor the frogs have a move so this
Lincoln cent, which was a frog, was right. Right made the last move, it's now left's
turn, left doesn't have any moves, left loses, Okay.
That's toads and frogs. And there's lots of examples involving up,
down and integers and all that good stuff involving with the small versions of toads
and frogs. So, so you can try this at home.
You can either do this with, with, with coins on a piece of paper or get your
friends and, that way you can jump over one another and you, you draw these on the
floor, okay? All right.
So but be careful. Don't hurt yourself and don't try that at
home. Probably do it with coins.
All right. So lets look at its, at a, toads and frogs
position. Now here we have toad, toad, they move
right, they're controlled by left. Blank means an empty space.
Frog, frog, frogs are controlled by right. They move left.
So, the only possible opening move for left is to move to toad, is to move this
toad one to the right and that leaves toad blank toad frog, frog.
And the only possible opening move for right is to move this frog one left and
that's leaves the position, toad, toad, frog, blank, frog.
Now, let's go over here and look at this position.
If left moves in this position, then this toad moves to the right.
And we're left with toad, toad, frog, frog.
That's a zero position. Okay?
Up and if right moves then right can jump out take this frog.
The only possible case is for right to move this frog jump over the toad and left
with toad, frog, toad blank frog. Now let me remind you that when we're
analyzing games we have to consider like two left moves in a row and right moves in
a row, because we want to analyze this game in the context of a much larger game.
So we might have this toads and frogs over here.
We might have a nim game someplace else, cut cake someplace else, a game of chess
going on, a game of Go going on. And then each player in turn chooses one
of these, one of these games and makes a move in it.
This is how we add gain. So and in doing so in adding this game to,
to others, left might make two, two moves in a row in this, okay?
So, I'm going to leave out some, some pretty long, I think, computation, but
this game down here. Toad, frog, toad, blank, frog is actually
equal to star so we have this game up here.
Toad, blank, toad, frog, frog. Its left option, only left option is to
move to zero only left move is to move to zero.
Only right move is to move to star and therefore this game toad, blank, toad,
frog, frog is up. Up, you remember, was left 0, right star.
Now, if you look at this game over here, it's the same as the game over here, with
toads and frogs interchanged and left and right interchanged.
Just, Just take the mirror image and change all the toads to frogs and all the
togs, frogs to toads. Therefore this gain on the right is the
negative of the gain over here. So this gain on the right is minus up
which is sometimes written down. So this whole gain is equal to up down.
And that's what I want to look at in this module.
Okay. So, there are no dominated moves.
Because there's only 1 move possible for each player.
But down here. If up is 0, star, then down is its
negative which is star, 0. Remember that the negative of star is star
and the negative of 0 is 0. And, so if right moves to down.
Left can move,[SOUND]. Left can move to star.
And my claim is, star is better. For left than the original game.
That is to say, g is less than or equal to star.
Which is the same thing as adding star to both sides.
G plus star is less than or equal to 0. Which says, that right wins this game
going second. Okay, who will bit the[UNKNOWN] there?
So, but what this means is that if right moved down, left moves immediately to up.
I'm sorry. Right moves to down, left moves
immediately to star. And now since star is 0, 0, the right
possibilities for to, to move From star are only 0, so this reverses all the way
down to just 0 which means that if right plays down left and mutely[UNKNOWN] plays
star and then rights only option is, is down[SOUND].
So this says that g is actually equal to up zero.
And this game simplifies a little bit. But that's part of the exercises,
homework, quiz. Whatever you want to call it, for this
week. Alright.
Now, let me make some general comments about this.
Simplifying games. We, we came up with 2 ways of simplifying
games. Dominated moves.
We can delete dominated moves. If a move is better for left than another
move, then you can, you never have to do the poor move.
If, if a move is better for right. You never have to use the move that it's
better than. And reversible move and that's a little
complicated but we have some examples and that's probably technically the most
complicated thing in the whole course. Now, the question is, is this enough?
That is are there other possible ways of simplifying games?
Of course there are. But what one can show is that this is
enough in the sense that if you keep doing dominated moves and reversible moves and
keep doing them over and over again, you'll reach a point where no moves are
dominated, no moves are reversible and what's left is called the canonical form,
and if, that's unique and there's so, and so in some sense some technical sense, in
fact that one can make very precise, the simplest possible version of that game.
So all that you really need is this. Now in terms, and that's how some computer
programs, and you can look up which ones that are available open source up on the
web actually simplified games And, they keep doing dominated moves and reversible
moves over and over again until there aren't any.
And then when its left, they say, this is as simple as possible, and that's what it
is. Okay.
Let me just leave you with this which will be posted in, in the assignments, et
cetera. And the directions this week are simplify.
So, write down the simplest form of, of each of these games.
Number 1 is numbers over here and numbers over here.
2 and 3 are turn out to be numbers, I think.
But, you try it yourself. Number 4 was what we ended up with in the
exact last answer. We took up down and simplified to this.
And now we want to simplify this further. The last one is the toads and frogs
position. Remember, frogs move right.
Toads move left. Take this and see if you can come up with
the simplest possible description of that and we'll see you all in a week or two.
Take care. Next week I think is NIM.
We finally will, will analyze NIM in general and answer the question, with the
arbitrary mid game how do you play and when?
Sp, we'll see that all next time. Take care.
