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

123 ratings

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

This course will cover the mathematical theory and analysis of simple games without chance moves.

From the lesson

Week 5: Simplifying Games

The topics for this fifth week is Simplifying games: Dominating moves, reversible moves. Students will be able to simplify simple games.

- Dr. Tom MorleyProfessor

School of Mathematics

Welcome back. Tom Morley, Games without Chance.

Actually that's not so bad. There's some game you play with these.

I, I, it, it has chance in it, so we won't use it.

We're looking now at examples from Nim and let's look at it.

Now, Nim is an example of an impartial game, so what we're going to do is

abbreviate impartial games like this. So what this means is the left player has

the option of moving to a Nim heap size 0, 1, 3, or 7 and the right player has

exactly the same options. The right player can, can move to a Nim

heap size 0, size 1, size 3, or size 7. Now, my claim is, so we neither leave 0 on

the table, leave 1 on the table, leave 3 on the table, or leave, let's see how many

more do we need. Leave 7 on the table and then the other

player can do so why is the, okay oh, all at once kind of proof like there in the

camera. So, so that's the game.

Now this is not by itself, not an interesting game, but you can be part of a

larger, a larger Nim game with other stacks of coins on the table.

Now, let's analyze this, in terms of analyzing this, my claim is, this is a

disguised version of a Nim heap of size 2. Why?

Let's take a look what you can do with a nim heap of size 2.

With a nim heap of size 2, you can leave no coins on the table.

That's star 0 or you can remove one coin, and leave one coin on the table and that's

star 1. So that's, that's star 2.

Now, this up here, these two moves don't do you any good, because they reverse.

If, if you put down three coins, another player removes one, we're left back with

star 2. If you put down 7 coins instead, one, two,

three, four, five, six, seven, then the other player removes 5 is that right?

Is that how you do arithmetic? Check it with your calculators.

Okay, and then you're left with two. So these two moves are reversible.

If you ever make those two moves, the other player can reverse, strike back to

star 2, so this impartial game is actually star 2.

It's actually the same as an n heap of size 2.

Try one for yourself. How, what about this one, star 1, star 0,

star 2, star 101. Try that, see what you can get.

You should conclude that this is the same as an n heap of size three.

Short module this time. You all come back now you hear.

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