This course will cover the mathematical theory and analysis of simple games without chance moves.
New Ways of Simplifying Games
Loading...
来自 Georgia Institute of Technology 的课程
Games without Chance: Combinatorial Game Theory
115 个评分
从本节课中
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
God morning, this is Games Without Chance. I'm Tom Morley.
Let's look a second over here is an ace. Over here is an ace Over here is an ace
and then we have one more. Okay.
So today, this week, we have some modules and the first one is new ways of
simplifying games. So let's look at two examples to start
with. Here's the first game and the second game.
The first game consists of a bunch of numbers for left options or left moves and
a bunch of numbers of right options. The second is a up and if we recall from a
while back Or you can look at one of the tabs on the left, for all the definitions,
up is 0, is the only left option removed, star is the only right option remove and
star is 0, 0. We've previously shown that up is positive
but less than any 1 over 2 n, for any interger end.
So, let's start with the first one and see how far we get.
If you look at this gain, left has many options, if three.
Three is many. But, the bigger the number is the better
it is for left so, seven is always better for left than either one or two.
So, there's no reason the left would ever play one or two, even if this game is in
context of a much larger game and just a small.
Peace So, left, as far as left is concerned, the left only will ever play 7.
Now on right, in right's moves, right wants to make numbers as small as
possible. Smaller is better for right and 8 is less
than 10, so. Right will always choose 8, even if this
is part of a larger context. So, these two are never used, these, this
one is never used in best play. So, this is the same as 7/8 and the
simpliest number between 7 and 8 is 7 and a half.
Path. So, we've simplified getting here by using
dominated moves. 7 dominates 1 and 2 because it's bigger
and it's a le-, left option or left move. 8 dominates 10 because it's the right
option that's less. So you, for domination we want.
On the left side we want bigger and on the right side we want smaller.
Ok, lets take a look at this game, up and 2.
We remember that, that up is positive and, and less than 1 over 2 to the n.
So, and, since 1 over 2 to the n is less than 2, up is less than 2.
All of the left options are, are less than the right options.
By claim, this is, this is a number and It's the simplest number that's in between
up and 2 and that's 1 but, if you want to prove it directly, all you have to do is
show that up 2 minus 1 is 0 and let's see if we can't argue that.
If left moves first, left moves to there are no left moves in minus 1, so left
moves to up and then we have up minus 1 which is negative to right wins.
So left moves first, right wins. If right moves first, right can either
move to Two, in which case you have 2 minus 1, which is one and left wins.
And then you have to check the other cases.
But in all cases if right moves first right loses if left moves first left
loses. Therefore, this is zero and therefore this
game is. One.
So here we've reduced to a number, even though it wasn't a kind of standard form
for numbers. Now if you go back a long time ago, we
looked at men back, way back in the introduction video.
We had three coins, we had two coins, and we had one coin.
And the rules of Nim are play, each player in turn can remove one or, must remove one
or more coins from one of these piles. Now this is a example of what's called an
impartial game which means that, that The rules are the same for both players.
If you, the negative of this game is the same as this game.
And one of the things I asked you to think about, in terms of this game in the
introduction video, was who wins this game?
And, in terms of what we do now who wins this game is the second part.
Player, whoever moves first loses, okay? So let's ask if extra coins help here.
So, so I have this nym game with these 3 nym piles.
Let's see I have them, that's a pile 1, that's a pile 2 and this is a pile 3 over
here. I'll put them under their numbers.
Star integer is just a notation for nim heap of that size.
Nim heap of size one, size two, and size three.
Now, if someone gives you some extra quarters, does that help you in any way?
So we already know that if you remove any of these then the player, who's next move
it is, has a winning move. So, the only possible winning move is to
perhaps to put more coins on here. So, I've put a bunch more coins on there
and it's a lot, you can count them if you want.
Now, what is the response to this? The response to this, is the other player
just removes the coins that you, that you just put on and puts a $1.25 in his
pocket. Now you're left back where you started.
It's still your move and now you loose again.
So, if, if it's your move and instead of removing a coin from here, you put on
extra coins, then the other player just removes them and he still wins.
So the extra coins don't do you any good. Now in terms of what we our vocabulary for
talking about games, this is called reversible move because once you make this
move, the other player will just reverse it and we're left back where we started.
Okay, this is the end of Module 1. Thank you.
