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 4: Numbers and Games

The topics for this fourth week is Simplicity and numbers. How to play win numbers. Students will be able to determine which games are numbers and if so what numbers they are.

- Dr. Tom MorleyProfessor

School of Mathematics

>> Games without chance. I did well this time.

I just dealt that the self, I dealt that to myself.

But that was a chance move, actually it wasn't.

But this is games without chance. I'm Tom Morley.

Here we are this week. We're now in the module, some games are

numbers. So, let's go back and look at this

alternative way we have of looking at games.

Left options, right options. Okay.

All of it, we can write down in terms of this notation.

The games that we looked at last time. 0 is no options for left, no options for

right. 1 is 0 for left and none for right.

2 is 1 for left and none for right. And we can get some of the fractions this

way. Okay, so here's the plan for this module.

We want to look at games that are given in this form and try to figure out what

numbers they are. Now the reason why we want to figure out

what number a game is, is because we know that positive numbers are positive.

And in positive games, left wins. Negative numbers are negative and in

negative games, right wins. 0 games are 0, and in 0 games whoever

moves next loses. So by, if once we know what number a game

is, we know who wins. So, this is partly to do with, with

connecting up games and numbers, but also partly to do with figuring out who wins.

And if we have a sum of games that are all numbers, all we got to do is add them up.

And, numbers add up like numbers. 1 plus 1 is 2.

You can prove that, I bet. Okay, so let's take a look.

So we know that 0 is, is this. But we also know that there are other

games that are equal to 0. A game is 0 if it's first person lose.

And any game that's 0, behaves like 0, like over here, even in a larger context.

So let's look at the game minus 3, 1. My claim is that this is zero.

Why? If left moves first, then left's only move

is to minus 3. And now right wins, because minus 3 is

negative. If right moves first, right moves to 1,

that's the only option for right. And 1 is positive, so left wins.

So if left moves first, right wins. If right moves first, left wins.

That's a first player lose, so this game is 0.

And I think you can actually get a much more general result, that if you have a

negative number over here, and a positive number over here, then any game like that

has got to be 0. Let's take a look at another example.

Let's look at. Let's do 1, 4.

My claim is that this is equal to 2. Now, what do I have to do.

I have to show that 1,4 minus 2 is 0. That is, whoever moves first in this game

loses. If left moves first, left has, remember

minus 2 is nothing minus 1, that's minus 2.

That's and then minus 2, left has no moves.

So in this game my left has no moves in minus 2.

So the, if left goes first left moves to 1, over here.

What's left is minus 2 which is minus 1. So if left moves first, we, left moves to

this 1, we still have this minus 2 over here.

1 minus 2 is minus 1 and right wins minus 1.

If right moves first, there's two moves to consider.

Right either moves to 4 minus 2, which is this 4 minus 2.

Or, 2 1, 4 minus 1. In either case, there's a little bit of

work to do, but ri-, left wins. So there is a lot of games written this

way that aren't the same, aren't the identical game to the Hackenbush games we

looked at before, but nonetheless turn out to be numbers.

And so here's one for you to try. And next time, we'll look at trying to

figure out, if it is a number, what number is it?

So, so try this one. Minus 4, minus 1.

What ga-, what number is this? The answer is that it's minus 2.

It fits in the middle and we'll see that's a key when the key stops.

And so to actually prove this, you would have to show that minus 4, the game minus

4, minus 1 plus 2 is 0. That is whoever moves first in this game

loses. Okay.

In 2, right has no move, so right has, if right goes first right has to move to this

minus 1. We still have minus 1 plus 2 which is 1.

Which is positive and so left wins. So there's half the argument and the other

is a little bit more complicated. But I think y'all can handle that.

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