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

>> Hey, welcome back. Good to see you, although I can't really

see you, but I'm looking that way and it looks like I can see you.

Okay. What are we doing now?

Examples from up, down, and star. Now, and the general reversible move.

This is probably one of the most subtle things we've done in the whole course.

And it's not something that's easily converted into hand computations and

examples. So if this seems like you have to go back

and look at it over and over again that's okay it's, it's something that, that's,

that's a little bit a little bit more Complicated than some of the other stuff

we've done. What I want to do is look at the general

reversible moves and then do an example. And the example is very, very small, so

what's really going on in, in talking about reversible moves is this is And

what's part of the general engine inside computer programs that analyze these

things. And although we can compute small examples

by hand, you can't really do much bigger examples by hand.

So bear with me, so here's a whole lot of text.

Just and this is, is a the definition of reversible moves in games without chance,

so we start off with the game which says certain left options and moves and certain

right options and moves then we say this game reverses through one of the left

options Or left moves. If there is a right move of this left

option, call that aR. With aR better for G, better for right

than G is, so remember is a game is less it's better for right.

So this means aR is better for right than G was to begin with.

So think about it this way. Left moves to a then right immediately

moves to one of the options inside a namely aR and right now is better off than

when right started. So right may as well do that.

All left moves to A right immediately is better off by moving to AR is better off

than, than he or she was when the game started.

In that case right, may as well do this all the time whenever left moves to a.

And, and therefor left might as well move directly to the right opt, left options of

they are. Rather then rather than to a, itself.

Now, that's a little bit complicated. We'll look at an example, so don't panic

yet. Alright.

I, I read some book that had this in it, right?

I've forgotten what the book was. Don't panic.

Okay, it was a book of advice, and whatever you asked it, it said Don't

panic. All right, so don't panic.

Now, in games we always have to look at things from the point of view of left and

the point of view of right. So, here is the analog for reversing

through a right move. Now, so here's an example.

And feel free to go back and look at these definitions again.

Ask questions about them in the forum. And to re-look at this example.

So here's the example. The example is up plus star.

Now up is left move, only left moves to zero.

The only right move is to star. Star is the only left move is to zero.

The only right move is to[INAUDIBLE]. 0.

So, up plus star is the same as this plus this.

So, we have 2 games, we play them the, there sum by playing in one game or the

other. So, let's look and see what happens.

Left can move to this 0. Make that move.

In which case what's left is 0 plus star. So that's a star.

Or left can move over here to this 0. In which case what's left is 0 over here

and up over here. So the two possible left moves leaves star

and up. And now let's look at the right move.

The right can move to star, in which case you have star plus star.

You can check it out, star plus star is 0 or right can move to this 0 over here then

you have 0 plus op and that's therefore, the other right option.

Now, let's look at this. So, the first thing we want to notice is

the following. I'm going to recopy some of this.

So, up plus star is, by our computation. Star up 0 up.

Now we know that 0 is less than up. From a few slides ago remember?

0 is less than up, is less than 1 over 2 to the n, for any n.

If you look back, this, this was actually done in, in one of the earlier weeks.

Although maybe we, we didn't actually write it that way.

So, so that says this op is always worse for.

Right then this 0. 0 is always better for right than up.

So this move is dominates so we can leave it.

Okay, that's the easy part or the easier part, all right.

So now, let's look at this up. Up, that up is 0 star.

And so it has a right option of star. Right move of star.

Now, star is less than up plus star, because just subtract star, just add star

to both sides, star plus star is 0, and over here we'll have, we'll have up plus

star plus star which will be up. So, so since 0 is less than up we have

this. Which says that there's a right option of

up, this up here, that's better for right than the original gain.

So, right will move there automatically once left moves the star, and then left is

left with the if right moves >> If left moves to up, right moves to star, and then

since star is 0, 0, the only left option from there is to move to 0.

Go back. Rewind the video, look at the definitions

that says this reverses to 0. 0 is the left options of the right option

of up divided which is better for right then you would know gain.

I think I said that right. So, so that says opp plus star is actually

zero star zero. Now, where have we seen that before?

Take a look at this position here, Hackenbush.

Green edge down here, blue edge up here. Blue can cut the, cut the blue edge.

Left can cut the blue edge. In which case, what's left is star or left

can cut the green edge. In which case, what's left is zero.

Right can only cut the green edge. In which case, what is left is 0.

So, these are equal games and they're both equal to up plus star, which is sometimes

abbreviated in literature as up star. So it turns out that we've seen this thing

before and now viewing this game is up plus star with for instance now what

happens when we added to itself, so up star plus up star is up plus up plus star

plus star But star plus star is 0, so that's up plus up, which is sometimes

written in the literature double up. So double up to be sure and we'll see you

next module.

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