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

115 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

Oh, hi. Good to see you back.

Give me a second, I'll be right with you. Hey, so here we are.

Let's cut the deck a few times. See what we have.

One here once more. Okay.

Here's your card. My card, your card.

My card, your card. Ooh, what's that?

Ooh, another king, you're doing good. My card, your card, and my card.

Ooh, I got an ace. What else did I get?

I got all aces. No chance.

Okay, here we are in week 6. So what was the change of that?

As advertised, week six is all about Nim, how to win it, all about impartial games,

reversible moves, examples, minimal excluded function and the big theorem

[unknown] but all impartial games are equivalent to Nim.

So let's start off with nim and how to win.

Okay. Star n is our game.

It's a new heap of size n. If you go back and look at the

introduction video. You know it's like 2 or 3 years ago.

We look at the Nim heap of size one, two and three applied together, plus star one

plus star two plus star three. First players loses so that's zero and we

say that in terms of game theory, star one plus star two plus star three is zero.

All is okay, let's look at a, one nim heap all by itself.

This is not very interesting. So here I have a nim heap of f, four dice.

Now whoever comes along just picks them up and they're all gone.

So a nim heap all by itself is a loss. If there's to the first player, if there's

nothing there, there's a win to the first player if there's something there.

Okay? So that takes care of one nim heap all by

itself. So it turns out that, the sum of a bunch

of nim heaps is equivalent to another nim heap and d, the size of the heap that's

computable, which is called the nim sum a, b, c, d, a, b, and c etc is, is computable

from that and it's called the nim sum. And what we just proved or in the

introduction video, we, we kind of used the fact that star one plus star two plus

star three is zero star zero is the same as zero.

And so what this says in terms of nim sums, is the nim sum of 1, 2 and 3 is 0.

Another example which you can work out after we say how to compute nim sums is

the star two plus star three plus star 7 and star 6.

I hope that's right. But I'm not very good at arithmetic.

There are 3 kinds of mathematicians in the world, those that can count and those that

can't. All right.

So let's compute this. So here's how to compute.

Let's, let's look at an example. I want to compute the nim sum of 14, 11,

and 2. So, how many kinds of mathematicians are

there in the world? There are this many and that's two,

because this is binary. Binary is just like base 10 except instead

of 10 fingers You have just two factors one, two, three, four I can't do that 1,

2, 3, 4 et cetera., et cetera. So 1, 2, 3, 4, 5 et cetera, et cetera so

you can like that that's binary You all can look it up.

It's not something it's new. It's been around for a while.

And some time, and ultimately inside computers, it's binary.

So computer scientists know all about that.

There are 2 kinds, there are 10 kinds of computer scientists.

And this actually means there are just 2. All right.

So, so 14 is 1, 1, 1, 0 in binary. Because 8 plus 4 plus 2, 8 plus 4, yeah

it's 14, I did that right. 11 is 8 plus 2 plus 1 and 2 is just 2 all

by itself. And here's how you can be at the nim's

sum. You add these up, column wise, but.

Just mod 2. So 0 plus 1 plus 0 is 1.

1 plus 1 plus 1 is 1 mod 2. 1 plus 0 plus 0 is 1 mod 2.

And 1 plus 0, 1 plus 0 is 0 mod 2. So the nim sum of 14, 11, and 2 because 0,

1, 1, 1, which is 4 plus 2 plus 1 which is 7.

Okay, here's how to win the nim game. If you have a heap size 14, hepa size 11,

hepa size 2, you're Nim sum is not 0. So therefore, there's a winning move if

you start. And let me show you how to do the winning

move. You take the answer here, go and find the,

the right most oh, that's not right most, that's left most.

Find the left most 1, go up here and find 1 of the numbers.

It has a 1 there and circle it. Now take what's to the right of that zero

one over here, take this down here one, one, now do the same to here one plus zero

is one and one plus one is zero again mod two.

So we're going We, we take one because that's already there, take this one and

make it a zero, make this a zero and make this a one.

So that comes from the zero one over here. So that's 1, 0, 0, 1 which is what?

That, seems to me that's 8 plus 1 that's 9.

So take the 14 heap and remove how many, 5 coins.

So it's now 9 heap, and that's your winning move.

Okay. Here's something for you to try.

Try with an n heap of size 11, and then heap of size 13, and then heap of size 10.

If this is a win for the first player, find the winning move.

If it's a loss for the first player, then give up.

Or at least offer the other player. Say, why don't you go first?

That, the end of the first module.

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