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