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

99 ratings

Georgia Institute of Technology

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