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

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

Still week six, wow. One more week to go.

So, here we're in impartial games, reversible moves and we'll have a few

examples and MEX. But I think that it's going to be two

pieces. So, let's take a look at this.

So, let's talk about impartial games. Impartial game is where like Nim, both

left and right have the same possible moves.

Not like five which gives five moves to the left and no moves to right.

Or minus five, which gives five moves to right but none to left.

Five and minus five are partisan games. They're games where it depends on whether

you're left or right. Whereas, Nim is impartial.

In general, a game is called impartial if every left move is also a right move, and

every right move is a left move. And every move in every position is also

an impartial game. So, let's look at an example.

Okay. Now, when we write down the impartial

games, we don't have to say what the left moves are and the right moves are.

All we have to do is say what the moves are.

This is because every left move is a right move and every right move is a left move.

So, let's look at the game where the moves are to Nim heap for size zero, size one,

size two, size five or size seven. Okay.

So, my claim is, is the same as this. So, so think of this as a Nim heap for

size three, that you can add two coins to or you can add let's see three, three,

four coins to. So, so start with start with a Nim heap

for size three, and either you remove one or more coins or you add two coins or you

add four coins. That's this game G.

Now if you add two coins, I'll just take them away and put them in my pocket.

And if you add four coins, I'll just take the, take, take the four coins and put

them in my pocket. So the, the move to star five, to five

coins, which you get by adding two coins and the move to star seven, which you get

by adding four coins, is irreversible. The other player just takes them away and

pockets them. And if they're like something really

exotic like a, like a rare year of the Morgan Dollars or something, it might be

worth something, it might be worth something.

In, say, grade 65 or so, that would be worth a lot of money.

So , so, if you add coins, the other player can just take them away and you're

back to where you started. What this says is, this game here is the

same as this game here. But this game here is the same as just the

Nim heap of size 3. Which you can then move from Nim heap of

size 3 or through a Nim heap of size 2, 1, or 0.

And we note here that 3 is the, what's recalled the minimal excluded number out

of 1, 2 and 3. That is, you look at 1, 2 and 3 and look

at the first natural number that's missing.

And in general, what happens, so let's take a look at some examples, of, of Mex.

And we'll leave that for you to compute for next time.

And then we'll have some, go back to examples of games.

So the minimal excluded of 1, 3, 2, 1, 17. Let's see.

One is there, two is there. I'm sorry.

0 is there, 1 is there, 2 is there, 3 is there, 4 isn't.

So it's 4. The minimal excluded of this is, well, 0

is not there. So, it's 0.

And the minimal excluded of this is 5, if I did this correctly.

And so here's the minimal excluded for you to get.

Now, it occurs to me that I didn't do the problem from last time.

And so let me just leave up some numbers here.

If we take a Nim heap of size 11, 3, and 10.

11, 13, and 10. Write them out in binary.

There's one here, go up to the one here. Circle that.

101, take 101 Nim sum 100. We get what do we get?

We get 001. So, the winning move is here.

Just keep the 11 the same. Take the 13.

And change it to a 1 and take the 10 and this is the same.

So that's, that's the solution, I believe to the to the problem at the end of the

last module. And there we have it, end of another

module.

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