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

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