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

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