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

105 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.