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

121 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

>> Well good morning, or afternoon, or evening, as the case may be again.

What I, we want to do today is just say a little bit about what is, and is not, a

combinatorial game. Alright.

No dice. No dice.

No cards. No random, randomization at all.

So, Monopoly has dice, it has you pick cards from the two piles.

Monopoly isn't a combinatorial game. All right.

There's two players, at least for what we're doing.

The two players we called Left and Right, call A and B, Bob and Susie, whatever you

want. There's just two of them.

They're different. Solitaire is not a[INAUDIBLE] game because

there's just one player. So[inaudible] games, there's two players,

no random moves. No ties.

Ooh, that looks like one word. No ties.

All right. So, chess can actually have a draw.

That's when neither black wins nor white wins, but, but they tie.

And so according to this, chess is not a[INAUDIBLE] game.

There, there are no, there's no dice in chess, there's no cards in chess.

There are two players but there is a tie. Now eventually we'll weaken that

assumption and, and allow for[INAUDIBLE] games with ties.

But for the time being, let's, let's only look at moves.

And ca, and games that are, that have no ties.

So either blue wins or red wins. But not both, and not neither.

Also it's finite. The game ends in a finite number of moves.

We might not be able to say ahead of time how many that is.

But we know that's finite. It doesn't go on forever.

Not that this is different than saying that there's only a finite number of

options available to each player. There can be, you can have games where

there's infinite number of things the players can do, but it still has to end in

a finite amount of[INAUDIBLE]. [inaudible] And so, we what we think of

this in the following way. The two players alternate playing the game

and when the first player that it's his or her turn and there's no move that, that

player can make, then that player loses. So in terms of chess, once you're in

checkmate, there's no move that you can make.

And therefore you lose. Two other things that are, that are close

to countertorial/g games, but not quite, which we'll look at are Go.

And you can look up. The details of Go.

Go is an interesting game. And also you may have, you may have played

this game in grade school. And it's called, or maybe high-school or

college, you know, you never know, it's called Dots and Boxes.

So, so players alternate drawing lines, and, and when, when you, when a player

completes a box you put your initials in the middle and you have to move again.

The score, then, is the total number of boxes.

And if you work out, if the number of boxes is odd then one player or another

must win. So, in that case, its a score but we can

think of it in terms of the score determining who wins, but again, there is

no ties. Each box is either red or blue and if

there's an odd number of boxes then one player or the other must have more boxes

at the end. This is actually a fairly complicated game

in terms of its analysis we hope to say a little bit about it towards the end of

the, of the course. Okay, so these are Kind of what is and

isn't a[INAUDIBLE] game. There, there are actually many things

that, that are very close to[INAUDIBLE] games in terms of, of ties and, and, and

whatever. These We'll eventually look at, but for

the time being we want to keep things fairly simple.

2 players, no random moves, finite, no tops, and that's where we're headed.

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