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

125 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. We have, what do we have?

We have, we have a straight flush. Small, small values.

But nonetheless, straight flush. Not quite in order, but you can check it.

We're doing toads and frogs now. You can, you can do this at home.

With people and it's fun play with people but you can also do it with, with coins.

Here's toads and frogs. Let's use nickels over here and Jefferson

nickels. Let's use Lincoln pennies over here.

Here's toads and frogs. The toads in this case are the nickels,

they move right and are controlled by left.

The frogs are the Lincoln cents, they move left and are controlled by right.

The toads can move one space to the right if it's empty.

The frogs can move one space to the left it it's empty.

But they also can jump over each other. A toad can jump over a frog, like this.

Note that the, the coin when you jump over isn't removed.

'Kay? But you can jump over and then they, then

say the Lincoln cent can move over here the, the nickel can do here.

The Lincoln cent can move over here My concern is the frog.

And we see at this point that neither the toads nor the frogs have a move so this

Lincoln cent, which was a frog, was right. Right made the last move, it's now left's

turn, left doesn't have any moves, left loses, Okay.

That's toads and frogs. And there's lots of examples involving up,

down and integers and all that good stuff involving with the small versions of toads

and frogs. So, so you can try this at home.

You can either do this with, with, with coins on a piece of paper or get your

friends and, that way you can jump over one another and you, you draw these on the

floor, okay? All right.

So but be careful. Don't hurt yourself and don't try that at

home. Probably do it with coins.

All right. So lets look at its, at a, toads and frogs

position. Now here we have toad, toad, they move

right, they're controlled by left. Blank means an empty space.

Frog, frog, frogs are controlled by right. They move left.

So, the only possible opening move for left is to move to toad, is to move this

toad one to the right and that leaves toad blank toad frog, frog.

And the only possible opening move for right is to move this frog one left and

that's leaves the position, toad, toad, frog, blank, frog.

Now, let's go over here and look at this position.

If left moves in this position, then this toad moves to the right.

And we're left with toad, toad, frog, frog.

That's a zero position. Okay?

Up and if right moves then right can jump out take this frog.

The only possible case is for right to move this frog jump over the toad and left

with toad, frog, toad blank frog. Now let me remind you that when we're

analyzing games we have to consider like two left moves in a row and right moves in

a row, because we want to analyze this game in the context of a much larger game.

So we might have this toads and frogs over here.

We might have a nim game someplace else, cut cake someplace else, a game of chess

going on, a game of Go going on. And then each player in turn chooses one

of these, one of these games and makes a move in it.

This is how we add gain. So and in doing so in adding this game to,

to others, left might make two, two moves in a row in this, okay?

So, I'm going to leave out some, some pretty long, I think, computation, but

this game down here. Toad, frog, toad, blank, frog is actually

equal to star so we have this game up here.

Toad, blank, toad, frog, frog. Its left option, only left option is to

move to zero only left move is to move to zero.

Only right move is to move to star and therefore this game toad, blank, toad,

frog, frog is up. Up, you remember, was left 0, right star.

Now, if you look at this game over here, it's the same as the game over here, with

toads and frogs interchanged and left and right interchanged.

Just, Just take the mirror image and change all the toads to frogs and all the

togs, frogs to toads. Therefore this gain on the right is the

negative of the gain over here. So this gain on the right is minus up

which is sometimes written down. So this whole gain is equal to up down.

And that's what I want to look at in this module.

Okay. So, there are no dominated moves.

Because there's only 1 move possible for each player.

But down here. If up is 0, star, then down is its

negative which is star, 0. Remember that the negative of star is star

and the negative of 0 is 0. And, so if right moves to down.

Left can move,[SOUND]. Left can move to star.

And my claim is, star is better. For left than the original game.

That is to say, g is less than or equal to star.

Which is the same thing as adding star to both sides.

G plus star is less than or equal to 0. Which says, that right wins this game

going second. Okay, who will bit the[UNKNOWN] there?

So, but what this means is that if right moved down, left moves immediately to up.

I'm sorry. Right moves to down, left moves

immediately to star. And now since star is 0, 0, the right

possibilities for to, to move From star are only 0, so this reverses all the way

down to just 0 which means that if right plays down left and mutely[UNKNOWN] plays

star and then rights only option is, is down[SOUND].

So this says that g is actually equal to up zero.

And this game simplifies a little bit. But that's part of the exercises,

homework, quiz. Whatever you want to call it, for this

week. Alright.

Now, let me make some general comments about this.

Simplifying games. We, we came up with 2 ways of simplifying

games. Dominated moves.

We can delete dominated moves. If a move is better for left than another

move, then you can, you never have to do the poor move.

If, if a move is better for right. You never have to use the move that it's

better than. And reversible move and that's a little

complicated but we have some examples and that's probably technically the most

complicated thing in the whole course. Now, the question is, is this enough?

That is are there other possible ways of simplifying games?

Of course there are. But what one can show is that this is

enough in the sense that if you keep doing dominated moves and reversible moves and

keep doing them over and over again, you'll reach a point where no moves are

dominated, no moves are reversible and what's left is called the canonical form,

and if, that's unique and there's so, and so in some sense some technical sense, in

fact that one can make very precise, the simplest possible version of that game.

So all that you really need is this. Now in terms, and that's how some computer

programs, and you can look up which ones that are available open source up on the

web actually simplified games And, they keep doing dominated moves and reversible

moves over and over again until there aren't any.

And then when its left, they say, this is as simple as possible, and that's what it

is. Okay.

Let me just leave you with this which will be posted in, in the assignments, et

cetera. And the directions this week are simplify.

So, write down the simplest form of, of each of these games.

Number 1 is numbers over here and numbers over here.

2 and 3 are turn out to be numbers, I think.

But, you try it yourself. Number 4 was what we ended up with in the

exact last answer. We took up down and simplified to this.

And now we want to simplify this further. The last one is the toads and frogs

position. Remember, frogs move right.

Toads move left. Take this and see if you can come up with

the simplest possible description of that and we'll see you all in a week or two.

Take care. Next week I think is NIM.

We finally will, will analyze NIM in general and answer the question, with the

arbitrary mid game how do you play and when?

Sp, we'll see that all next time. Take care.

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