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