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