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

Georgia Institute of Technology

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

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