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

105 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 no chance.

There's no chance the cards ended up like this,

because that's a perfect faro from new deck order.

Today we want to look at an example of ski jumps with jumps and

ski jumps without jumps, and we'll start with

jumps and ski jumps, without jumps.

Now, let's first talk about without jumps.

It's plain old board looks something like that.

We can have many more different rows.

The rows can be different lengths and each row is a counter.

The penny here represents left and the dime here represents right.

And you grab whatever you want for the starting configuration.

Even now, they're just one counter per row.

Now you can have as many rows as you like.

The rows can be as long as you'd like.

Here's one instance.

The penny that is left always moves right.

The dime that is right always moves left.

And as usual, the first player that can't move loses.

And so, let's play the game with left going first.

Left moves, then right moves, left moves, right moves,

left moves, right moves, left moves, right moves, and left has no where to go.

So left has no move, it's left move, so left loses.

So when left starts, left loses.

Let's look and see what happens when right starts.

It's almost exactly the same only upside down or something.

So right, left, right, left,

right, left, right, left, It's now right's turn.

Right has no move.

You have to stay inside the board.

So right has no move, it's right's move, right loses.

So, when left starts, left loses, when right starts, right loses.

And that says first player loses, which is another way of saying that it's zero.

First player loses.

Now let's look at possibility of jumps.

The possibility of jumps makes it a much more interesting game, I think.

With jumps, let's see what a jump is.

When we have two counters like this,

one directly above the other, a different, one's left and one's right.

In our game, left will be above right, but depending on the initial configuration,

right could be above left.

If they're over like this, on his left move, left has two options.

Left can continue on to the right, or left can jump over right and end up down here.

So, for instance, when

If the configuration is like this and if lefts move, Left can either

move to the right like this or left can jump over right and end up down here.

That's what a jump is.

It's always optional.

And so, let's see what happens.

Let's start off like here and look at right going first.

Right goes first.

Left- I'm sorry.

Left going first.

Left goes first.

Right, left, right.

Its now left's turn.

Left jumps.

Right continues onto the left.

It's left's turn.

It's right's turn.

It's left's turn. Now it's right's turn.

Right has no move and right loses.

So when left goes first, right loses.

As before, when right goes first, right loses.

Right doesn't have any possible jumps here.

So going second left wins and going first left wins.

That says the game is positive.

So this initial configuration of ski jumps

with jumps is always a left player win going first or second.

So it changes with jumps.

Now, so it's positive.

It's bigger than 0.

And so the question is, how much bigger than 0 is it?

So let's compare this while trying

to play the game G + (-1).

So we play several games at once.

We can either play in here or we can play in here.

This is a hack and bush with one red stock,

and so that's the same as minus one.

It gives a free move to right, and there's no moves in there for left.

Let's look and see what happens.

What happens here, the interesting case, and

there's a couple of cases, you can work out several of these yourself.

So when left goes first,

Now it's Right's turn, Right can cut the stalk and

now it's left's turn, and Left has nowhere to go, so Left loses.

So when left goes first, left loses.

When right goes first, left also loses.

And so, and you have to check that.

It's a small game so you can check that.

So what we have is that G- 1, right always wins first or second.

Let's play.

Let's see what that says.

G- 1 < 0, then just add 1 to both sides, they have G < 1.

We already know that G was bigger than 0.

So G is somewhere in between 0 and 1.

The question is where?

And the answer is, we'll see in a little bit.

Okay, there we have it and stay tuned for the next little piece.

Thank you.

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