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