This course will cover the mathematical theory and analysis of simple games without chance moves.
All Impartial Games Are Equivalent to Nim
Loading...
Del curso dictado por Georgia Institute of Technology
Games without Chance: Combinatorial Game Theory
115 calificaciones
De la lección
Week 6: Impartial Games
The topics for this sixth week is Nim: Students will be able to play and analyze impartial games.
Conoce a los instructores
Dr. Tom MorleyProfessor
School of Mathematics
Okay. Welcome back.
Week six. I just rolled the dice.
They all came up that way. You believe that?
It's pretty dark in here. I wish they'd turn off, turn up the lights
or something. I don't know what's wrong.
In the studio here. Let's see.
Oh, it's not so bad. Okay, so this week is a big, big theorem
due to Grundy. I believe in the early twentieth century
1930 later 30s is my guess. You all can look it up on, on, on the
interwebs or whatever it's called and, and here's the paper.
But let's first go back and answer the question from last week.
Okay, so we're at six, we can subtract one, two or five.
That's my subtraction game. 1, 2 or 5.
So 1, 2 there it goes. So that's the mex of 1, 1 and 2 is 0.
So it's 0. And I bet you the next ones a 1.
And the next, and I bet you it goes 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, forever.
It's periodic. A lot of these, a lot of these impartial
games are, are, if not periodic, at least ultimately periodic.
After awhile, they, they're periodic. And what this means is something very
Important in terms of computational complexity, it says we can solve all of
the games in a finite, amount of time. They all reduce to a Nim heap of size
zero, one or two regardless of how big they are.
And we can tell which one that it is simply by calculating[UNKNOWN] through
It's important. That, theorem like that for the game
Chomp, won of, one student once a hundred thousand dollars in a science fair.
You can look it up. Alright, now do the Grundy and if g is
impartial then g is star n for some, n for every, Every impartial gain is equivalent
to a nin haive And an example, here's our starting example as before, there we go.
Here look at the minimal excluded. So here, here, here's the proof.
And so don't panic, it's a proof. You know mathematicians do these kinds of
things. Then, oh.
There's induction. And the, the proof is so short, I can just
sit here and make noises. Okay.
The proof is so short that, that we kind of wonder afterwards, did I really do
anything? The answer is, yes you did.
You've proved a theorem. That's a big deal.
All right. So I will do induction.
If G is zero gain, then G is already equivalent to nim heap size zero.
Piece of cake. All right, so I suppose G is impartial.
Then by induction, the options of G, the moves of G are themselves.
Equivalent Nim makes this is by induction These are simpiler games than G, so
assuming that the theorem is true for all simpler games, all of these are equivalent
to Nim games and we're basically back this same ol' example, where is it?
Basically, example. If you have something like this, this is a
nim heap with, with possible adding coins, but adding coins doesn't do you any good
because you gotta play, you can just take them away.
Okay let me do an example here which relates back to what we started with this
week and that's nim sums. Okay.
Nim sums. So let's take a look at star 2 plus star
3. This theorem ought to tell us about how,
how, how, how we compute this. So suppose we don't know about nim's
signs, and we just want to compute this so, so star 2 is this game here and star 3
is this game. And so, if you add them together, what do
you get? You take one of these plus this, that's 0
plus 3 or this plus this. That's 1 plus 3 or you take the whole
thing here, plus 0. That's star 2 plus 0 or you take 1, star 1
plus star 2. That's this, this option plus the whole
game over here or you take star 2 plus this whole game, which is star 2.
So, so just by the definition of addition Star 2 plus star 3 which is this plus this
is this. Now 0 plus anything is anything.
So that's a star 3. A star 1 plus star 3, well that's a
simpler game. And we'll suppose we've already computed
that. We actually know how to do that.
That's 0,1 plus 1, 1 and then sum in binary which is 2.
0 plus 2 is 2 because 0 plus anything is 0.
1 plus 2 is 3. Both in ordinary arithmetic and nim sum
and two plus two in nim sum is 0. So, so, star 2 plus star 3 is this, and if
you look, 0 is here but one isn't so the minimal excluded is one.
So the whole thing is equivalent to nim heap size one.
And we knew this already. If, if you take nim a nim heap of size two
plus a nim heap of size three it's equivalent to a nim heap size one because
the nim sum of 2 and 3 is 1. Let me give you another game, slightly
more complicated. That you all can talk about in the forums.
We're not going to solve that explicitly here although I may comment in the forums.
And it's, we have a stack of coins, remove one coin and split into 2 nonempty piles.
So if you start off with 0 coins, then there's no moves.
And if you start off with 1 coin, there's no moves.
And if you start off with 2 coins, there's no way to remove 2 coins, and split it
into 2 pieces. There's not, I'm sorry.
There's no way to take 2 coins, remove 1 of them.
And take the remaining 1 coin, and split it into 2 non empty piles.
So that's 0, 2. 3 is the first, non trivial case.
And, you can work it out. And work out some higher ones.
This is an interesting game, called point 4.
And if you want to look this up on the internet or someplace else, it's called
octal game. Alright let's look at the quiz for this
week it's find the nim sum of one, five and 11.
Find the Mex of That's it. For, for subtraction game 1, 2, 5, find G
of 7 and find G of 4 for the subtraction game 1, 2, 3.
'Kay? So and this'll, this'll, this'll show up
actually on, on a quiz and you'll have a little bit of time to do it I think.
Those straight forward if you not let me know, and, that's we cast 6.
All come back now you're hear?
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
