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 1: What is a Combinatorial Game?

Hello and welcome to Games Without Chance: Combinatorial Game Theory! The topic for this first week is Let's play a game: Students will learn what a combinatorial game is, and play simple games.

- Dr. Tom MorleyProfessor

School of Mathematics

>> Hello, this is games without dice or cards.

Combinatoriai Game Theory. I'm Tom Morley.

So let's start by jumping into the water head first, and let's play a game.

Let me first introduce you to our two players.

Our two players are called left and right. These two players alternate.

One goes, what the other one makes a move, then the first one makes a move, then the

other one makes a move. Typically, left is associated with the

color blue and you can remember that because there's an L is blue and right is

associated with red, and you can remember that, because there's an r in red.

Now, these players are going to alternate, alternate, play and the 1st 1 that can't

move loses. So there's no ties.

At each stage of the game there will be various moves available to one player or

the other player or perhaps both, and whoever runs out of moves loses.

So let's take a look at something like this, and So let's start with a little

horsey. Okay.

So this is a game called Hackenbush, well, it's a particular position in the game

called Hackenbush. And you can start in various ways but we

start with this little horsey. The two players, red and blue, left and

right, take turns, and what they do is cut one of their edges of their own color.

So if blue starts, he could cut this edge, and that edge is no longer there.

Now, these, these edges have helium in them, so and they're attached to the

ground here, which is green. So if something gets disconnected from the

ground, it floats off and is not available to either player.

So, for instance maybe, right goes here maybe left goes here.

Now, at this point, this whole piece here is still connected to the ground.

But once right moves, it all floats up, and now left moves, and there's no moves

left for left. Okay, so, so whenever the two players

alternate, left cuts blue edges, right cuts red edges.

Any edge that's either cut or no longer connected to the ground to where the

nutrients are, the nitrogen and the water and whatever.

Any edges no longer connected to the ground, floats off and is not available to

either player. When a player has no edges to cut, the

game ends, that player loses, okay? We'll see a lot of examples in terms of

Hackenbush as, as the game goes on. Let's take a look at some very simple

positions in Hackenbush. Here's the ground.

It's green. And now we go, I don't know.

Blue, and blue, and maybe a red in between.

And maybe a red. And then, say, a blue on top.

Up, now up. It's okay that these aren't connected, but

they're connected to the ground, so that's okay.

So, they're there maybe, maybe red goes first and red says aha, I'm going to cut

this and now these float off and that top blue end is no longer available for blue.

Blue say, what's the best move for blue? I don't know offhand, but blue might cut

this, and then red cuts this, and then blue cuts this, and now red loses.

So that's how that works. And we'll, we'll look at various

variations of this where we start with, with, with more complicated pictures and,

and try to analyze in terms of, of who, who wins, if left goes first, who wins if

right goes first? Okay.

Let's take a look at another class of games.

And this is a class of games all played with coins.

In this case the coins are pennies and dimes, but and maybe right is pennies,

because the copper in pennies, although, there's very little copper actually in

pennies looks kind of red. And then the dimes, say are, are left.

Now both players push coins to the left in the direction of, of that and the three

games push, shove, and run over have slightly different rules.

Now you can, you can, you can push a coin off the edge, off the end, and if it's off

the end, it's no longer in play. So the two players alternate pushing one

coin to the left one space. And let's look at let's look at, say, this

position here in push, the first game. If left pushes this coin over this, this

coin over one, then that pushes also that, the, the coin next to it over.

So that's, that's called push. In, in, in shove, when you push a coin

over, everything to the left moves over one space also.

So with shove, this, this, this coin over here gets thrown off the cliff.

In run over, what happens is when you push, say this coin over here one to the

left, you run over that person and that, that coin disappear from playing.

So you can look at longer positions to start with, different relations of coins

on the thing. I think it's not too hard to show.

Whoever has the right most coin will win the game.

But, but if we have several of these going at once, then, then things get a little

bit more complicated. And still what we want to do, even if we

know who, who's, who wins the game what, what's the best play maybe to, to delay,

going off the cliff as long as possible. So, so here's four games to play with and

I urge you to start with pictures like this.

Find someone to play, find, figure out whether we want to be left or right

doesn't matter. Draw a picture like this and go play some

games get some coins out, draw pictures like this.

Play several of these at once and we'll explain as the course goes by how to do

that more carefully and, and see what see what looks like good moves and see what

looks like bad moves. So there's some games to start with and,

let's, continue next time.

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