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

'Kay. Welcome back.

Â Still week six and we're doing some more examples and talking a little about

Â minimal excluded. Okay, so let's, let's take a look at this

Â quickly. We have some examples of minimal excluded

Â and excuse me while I look around the camera.

Â Okay. So let's see.

Â Zero is here, one is here, two is here, three is here, four is here, five is here,

Â six is here, seven is here, eight. 8 isn't.

Â So the minimal excluded of this is 8. And so that's the solution from last time.

Â Alright, here's the general result. If we have an impartial gain, all of whose

Â moves are to nim heaps. And this game is equivalent to a nim heap

Â of size d, where d is the minimal excluded natural number in the set consisting of

Â this a, b, c, a, a, b, dot, dot, dot, up to c.

Â So the example from last time fits this context here we have this.

Â Here's a game, all of the options are nim heaps and 3 is the first missing number.

Â And so this game is equivalent to nim heap of size 3.

Â Okay. Let's take a look at, and Any, any of

Â these things we can think of as, as min heaps, where we can add more coins, but

Â you can reverse those moves by putting the coins in your pocket.

Â Alright. Let's take a look at a, a, a, at a case

Â yet another kind of case, another kind of game, it's called a subtraction game.

Â So we start with a heap of size n, n may be 1, 2, 3 or 17 or 40 billion.

Â A move for either player is to remove one, two or five Coins, or beans or dice,

Â whatever they are or bicycles, we could have a heap of bicycles that would be fun

Â to play. Okay, so let's take a look at that.

Â If we have, start off with a hepa size 0, then there's no moves so that's equivalent

Â to of size zero. If we start off with an in heap of size 1,

Â I'm sorry. We start off with a heap of size 1 and

Â play the subtraction game, 1, 2, or 5. Then our only move is to a nim, to a heap

Â of size 0. That's 0.

Â And the mex of zero all by itself is 1 so that's a 1.

Â Now, with a heap of size 2, we can remove 1 coin, giving us a heap of size 1.

Â Equivalent to a hepa nim heap of size 1 or we could remove 0 coins.

Â Giving us equivalent to an in equal sign 0.

Â The mex of 0 and 1 is 2. For three coins, we can remove 1 or 2, so

Â we can replace this by, a heap of size 1 or 2.

Â Which is equivalent to a nim heap of size 1 or 2, and the mex of 1 and 2 is 0 for a

Â heap of size 4. We can remove 1 giving, an equivalent to a

Â nim heap of size 0 or, 2, giving an equivalent of nim heap of size 2.

Â The max of 0 and 2 is 1. For 5 we can, we move 0, 1 over 5, ooh,

Â there we go. Alright I feel like I'm playing the piano

Â or something. Alright and, and so the mex of zero, 0 and

Â 1 is 2. For 6 here, this is for you to figure out.

Â An we'll start next time with the, the next module with this.

Â So, I can, it goes back to removing one, removing two or removing three so what do

Â you think that should be? Okay.

Â Not too hard. So, what we can do You say the file, in

Â general, we can have subtraction gain where we a, b, dot, dot, dot or c coins.

Â First player with no moves loses. And g of n is d this, the, the size of a

Â nim heap equivalent to this game. And this can be computed In exactly, this

Â way and I think we're done. It only works if you make a noise, take

Â care.

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