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

92 ratings

Georgia Institute of Technology

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