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

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