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

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