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

>> Games without dice or cards, combinatorial game theory.

Â I'm Tom Morley and glad you're back. We've been doing a lot with games and some

Â of these games were numbers and they behaved like 1 or they behaved like minus

Â 1 or 0, or 1 half in, in one case. Not all games are numbers, some games are,

Â are much weirder than numbers. So let's take a look at this simple game.

Â It's Hackenbush, where you have one green edge.

Â Remember with a green edge you can. Green edge can be cut by either left or

Â right. And this game is, has a name, it's called

Â star. Okay.

Â Now let's see, who wins star. If left goes first, left cuts and right

Â has no move. If right move, goes first, right cuts and

Â left has no move. So whoever goes first wins.

Â That says star is fuzzy with zero. There aren't any numbers that are fuzzy

Â with zero. And to make matters worse, star plus star

Â is 0. Let's try, let's check it out.

Â Here's star, here's star. If left goes first he cuts that, right

Â cuts that and now left has no move. So whoever goes first in star plus star

Â loses, and so star plus star is 0. So that's not a number, numbers can't

Â behave that way. Here's another example, and it goes back

Â to, to illustrate our, our new way of writing out games.

Â This is a game called up. And it's, it's written this way.

Â And it's the game, the left option, left can move to 0.

Â And that's the only possible move. And right can move to star and that's the

Â only possible move for right. So let's look at up and see who wins up.

Â Okay, so, so let's see who wins up. Up is 0, star.

Â If left goes first, left moves to this 0. 0 has no moves for anyone, so left wins

Â because right has no moves. If right goes first, right's only move is

Â to star. Which is this.

Â Which is the same thing as 0,0. There we go, yes.

Â And so right then moves to star, and here's star.

Â And left moves to 0, and now right again has no moves.

Â So left going first, left wins. Right going first, left wins.

Â So that says that up is bigger than 0. But up is not a number, and here's, here's

Â why. What I want to do is show that in fact, up

Â is less than 1 over 2 to the n, for any n. Now 1 over 2 to the n is a, is a

Â Hackenbush position where you have one blue edge then a whole bunch of red edges

Â on top. And to show that, that up is less than 1

Â over 2 to the n is the same thing as showing that 2 to the n minus up is

Â greater or equal to 0. Which is to say that left wins this game.

Â Going first or second. So here's 1 over 2 to the n.

Â Here's minus up. Reverse the moves for left and right and

Â reverse all the moves for left and right in the options.

Â And so, all we have to do is show that left wins going first or second.

Â So let's look so you try this. And we'll be back with a solution, in a

Â little while.

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