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

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

God morning, this is Games Without Chance. I'm Tom Morley.

Let's look a second over here is an ace. Over here is an ace Over here is an ace

and then we have one more. Okay.

So today, this week, we have some modules and the first one is new ways of

simplifying games. So let's look at two examples to start

with. Here's the first game and the second game.

The first game consists of a bunch of numbers for left options or left moves and

a bunch of numbers of right options. The second is a up and if we recall from a

while back Or you can look at one of the tabs on the left, for all the definitions,

up is 0, is the only left option removed, star is the only right option remove and

star is 0, 0. We've previously shown that up is positive

but less than any 1 over 2 n, for any interger end.

So, let's start with the first one and see how far we get.

If you look at this gain, left has many options, if three.

Three is many. But, the bigger the number is the better

it is for left so, seven is always better for left than either one or two.

So, there's no reason the left would ever play one or two, even if this game is in

context of a much larger game and just a small.

Peace So, left, as far as left is concerned, the left only will ever play 7.

Now on right, in right's moves, right wants to make numbers as small as

possible. Smaller is better for right and 8 is less

than 10, so. Right will always choose 8, even if this

is part of a larger context. So, these two are never used, these, this

one is never used in best play. So, this is the same as 7/8 and the

simpliest number between 7 and 8 is 7 and a half.

Path. So, we've simplified getting here by using

dominated moves. 7 dominates 1 and 2 because it's bigger

and it's a le-, left option or left move. 8 dominates 10 because it's the right

option that's less. So you, for domination we want.

On the left side we want bigger and on the right side we want smaller.

Ok, lets take a look at this game, up and 2.

We remember that, that up is positive and, and less than 1 over 2 to the n.

So, and, since 1 over 2 to the n is less than 2, up is less than 2.

All of the left options are, are less than the right options.

By claim, this is, this is a number and It's the simplest number that's in between

up and 2 and that's 1 but, if you want to prove it directly, all you have to do is

show that up 2 minus 1 is 0 and let's see if we can't argue that.

If left moves first, left moves to there are no left moves in minus 1, so left

moves to up and then we have up minus 1 which is negative to right wins.

So left moves first, right wins. If right moves first, right can either

move to Two, in which case you have 2 minus 1, which is one and left wins.

And then you have to check the other cases.

But in all cases if right moves first right loses if left moves first left

loses. Therefore, this is zero and therefore this

game is. One.

So here we've reduced to a number, even though it wasn't a kind of standard form

for numbers. Now if you go back a long time ago, we

looked at men back, way back in the introduction video.

We had three coins, we had two coins, and we had one coin.

And the rules of Nim are play, each player in turn can remove one or, must remove one

or more coins from one of these piles. Now this is a example of what's called an

impartial game which means that, that The rules are the same for both players.

If you, the negative of this game is the same as this game.

And one of the things I asked you to think about, in terms of this game in the

introduction video, was who wins this game?

And, in terms of what we do now who wins this game is the second part.

Player, whoever moves first loses, okay? So let's ask if extra coins help here.

So, so I have this nym game with these 3 nym piles.

Let's see I have them, that's a pile 1, that's a pile 2 and this is a pile 3 over

here. I'll put them under their numbers.

Star integer is just a notation for nim heap of that size.

Nim heap of size one, size two, and size three.

Now, if someone gives you some extra quarters, does that help you in any way?

So we already know that if you remove any of these then the player, who's next move

it is, has a winning move. So, the only possible winning move is to

perhaps to put more coins on here. So, I've put a bunch more coins on there

and it's a lot, you can count them if you want.

Now, what is the response to this? The response to this, is the other player

just removes the coins that you, that you just put on and puts a $1.25 in his

pocket. Now you're left back where you started.

It's still your move and now you loose again.

So, if, if it's your move and instead of removing a coin from here, you put on

extra coins, then the other player just removes them and he still wins.

So the extra coins don't do you any good. Now in terms of what we our vocabulary for

talking about games, this is called reversible move because once you make this

move, the other player will just reverse it and we're left back where we started.

Okay, this is the end of Module 1. Thank you.

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