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.

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