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

124 ratings

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

This course will cover the mathematical theory and analysis of simple games without chance moves.

From the lesson

Week 3: Comparing Games

The topics for this third week is Comparing games. Students will determine the outcome of simple sums of games using inequalities.

- Dr. Tom MorleyProfessor

School of Mathematics

>> Welcome back, still week three. What we want to do is take a look at an

example, and see how we can use inequalities, to analyze games and how we

can use inequalities to, to simplify games.

Example I want to look at is this example here in Hackenbush.

This is the game G. There's the, the ground here, the ground

is green. The blue edge, a red edge, and a blue

edge. This is Hackenbush, and if you go back to

week one, or at some point there should be a, dictionary on the site, with, with how

various games work. Players alternate.

Red is, can only be cut by right. Blue can only be cut by left.

And once an edge is cut, not only does that edge disappear, but any edge that's

no longer connected to ground disappears, will also disappear.

So if you look at the possible left moves, left can cut this blue edge on the top.

In which case what is left is just, blue, red, like this.

Or, blue can cut the edge down at the bottom, in which case what is left is just

nothing. Now, what I want to do now is, is, give

you another way of writing out games. Another way of writing out games, and

you'll see this on any of the references we look at, is left curly bracket, and now

list the possible left moves then a, pipe in unix vertical, vertical, verticals up

and down and then list the right moves. So, the possible left moves, are chop off

the bottom blue edge, and that's zero, this game is zero.

Whoever moves first loses. Now the other possible opening move for

blue is, or left, is to cut off the top here.

And that leaves this. And awhile back we called this game 1

half. And it turns out, this game, plus itself

is equal to 1, so we might as well call this 1 half.

Now the possible right moves are to cut off the red edge there, in which case,

what's left is just one blue edge, and one blue edge is one move for left and that's

the game 1, we'll call that the game 1. So this game up here could be represented

abstractly as the game, where left moves are to 0 or 1 half, and the right moves

are to 1. Now, you can prove, or, you can go through

the details, or you probably would guess, that 0 is less than a half.

That's true. Just look at 1 half.

To say 0 is less than a game means, left wins the game.

1 half, going first or second. And look at this game up here.

1 half,, and we see left always wins. Left going first cuts the blue edge.

Right has no move, right loses. Right going first cuts the red edge, then

blue cuts the then left cuts the blue edge.

And again left wins. So if 0 is left than a half which means

that 1 half is always better, for left, than 0 is.

So what that says, is there's no reason whatsoever, that left would ever choose 0.

1 half is always better. So this game is the same as this, and now

we've simplified the game, to an equivalent gain with fewer, fewer possible

moves. We've deleted the moves that are no good

because of inequality. Now in terms of right moves, there's only

one right move here. But, if there were several right moves, we

could delete all but the smallest, because right wants moves to be small, and left

wants moves to be big. Okay, so let me end with a problem, and

this is for you to work on. Here's two games, G and H.

And see if you can prove that G is less than or equal to H.

If you remember right, that says that H minus G wins the left going second.

So you can work that out.

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