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

99 ratings

Georgia Institute of Technology

99 ratings

This course will cover the mathematical theory and analysis of simple games without chance moves.

From the lesson

Week 6: Impartial Games

The topics for this sixth week is Nim: Students will be able to play and analyze impartial games.

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

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.