Professor Ben Polak: So

last time we finished up by playing the game of Nim and

you’ll remember, I hope, that the game of Nim

was a game where there was two piles of stones–we made do with

lines on the board–and the winner was the person who picked

up the last stone. Remember you had to pick piles.

I want to use the game of Nim to make a transition here.

So what we had pointed out about the game of Nim was it

illustrated very nicely for us that games can have first mover

advantages or they can have second mover advantages.

A very small change in the game, essentially a very small

change in where we started from, could switch a game from a game

with a first mover advantage to a game with a second mover

advantage. Now today, I want to just draw

a slightly grander lesson out of that game.

So not only was it the case that the game sometimes has

first mover advantages and sometimes has second mover

advantages, but moreover,

we could tell when it had a first mover advantage and we

could tell when it had a second mover advantage.

Is that right? When we actually looked at the

initial set up of those stones, we knew immediately that’s a

game in which Player 1 is going to win,

or alternatively, we knew immediately that’s a

game which Player 2 is going to win.

Now it turns out that that idea is very general and actually has

a name attached to it, and that name is Zermelo. So today we’ll start off by

talking about a theorem due to a guy called Zermelo,

and the idea of this theorem is this.

We’re going to look at games more general than just Nim,

and we’re going to ask the question,

under what circumstances would you know about a game either

that Player 1, the person who goes first,

can force a win, or that Player 2 can force a

win, or will allow a third possibility,

which is it’s going to be a tie. So here’s the theorem,

suppose there are two players in this game,

like the games that we looked at last time,

and suppose–I won’t define this formally now–but suppose

the game is a game of perfect information.

So what do I mean by perfect information?

I’ll define this later on in the class, but for now all I

mean is, that whenever a player has his turn to move,

that player knows exactly what has happened prior in the game.

So, for example, all these sequential move games

we’ve been looking at are moves of perfect information.

When I get to move I know exactly what you did yesterday,

I know what I did the day before yesterday and so on.

So it’s a game of perfect information.

I’m going to assume that the game has a finite number of

nodes. So two things here,

it can’t go on forever, this game, and also there’s no

point in which it branches in an infinite way.

So there’s a finite number of nodes, and we’ll assume that the

game has three possible outcomes.

Actually there’s a more general version of this theorem but this

will do for now. The three possible outcomes are

either a win for Player 1, so I’ll call it W_1,

or a loss for Player 1, which is obviously a win for

Player 2, or a tie. So the game–like Nim last

time, that only had two outcomes.

So here we’re going to look up to three outcomes or three or

fewer outcomes I should say. So these are the conditions and

here’s the result. So I said three,

it could be three but it could also be two here,

I’m just allowing for three. (One is trivial.) So under

these conditions the following is true.

Either Player 1 can force a win, so either it’s the case

that this game is a game that if Player 1 plays as well as they

can, they’re going to win the game

no matter what Player 2 does. Or 1 can at least force a tie,

which means Player 1 can play in such a way that they can

assure themselves of a tie regardless of what Player 2

does. Or it could be a game in which

2 can force a loss on 1, so a win for 2.

So this theorem, when you first look at it,

it doesn’t seem to say very much.

You’re staring at this thing–you might think,

we already knew that we’re looking at games that only have

three possible outcomes win, loss, or tie so it doesn’t seem

so surprising if you look at this theorem,

it says, well, you’re going to end up

with a win, or a loss, or a tie.

However, that’s not quite what the theorem says.

The theorem says, not only are you going to end

up there–we knew that already–but the games divide

themselves. Games of these forms divide

themselves into those games in which Player 1 has a way of

winning regardless of what Player 2 does;

or games in which Player 1 has a way of forcing a tie

regardless of what Player 2 does;

or Player 2 has a way of winning regardless of what

Player 1 does, so these games all have a

solution. Let’s just go back to Nim to

illustrate the point. So in Nim actually there’s no

tie so we can forget the middle of these, and in Nim,

under certain circumstances it is the case that Player 1 can

force a win. Who remembers what the case

was, for when Player 1 can force a win?

Anybody? The people who played last time.

No, yes, Ale, there’s somebody here.

Shout it out. Student: Insuring that

the piles are equal for the other player.

Professor Ben Polak: All right, so if the piles start

unequal, then Player 1 can actually force a win.

So in Nim if the piles are unequal at the start,

then 1 can force a win. It really doesn’t matter what 2

does, 2 is “toast.” Or the alternative case is the

piles are equal at the start, and if they’re equal at the

start then it’s Player 1 who’s “toast.”

Player 2 is going to–rather–force a loss on 1,

so 2 can force a loss on 1, i.e.

a win for Player 2. Does everyone remember that

from last time? It’s just before the weekend,

it shouldn’t be so long ago. So this theorem applies to all

games of this form. So what games are of this form?

Let’s try and think of some other examples.

So one example is tic-tac-toe. Everyone know the rules of

tic-tac-toe? In England we call it Noughts

and Crosses, but you guys call it tic-tac-toe,

is that right? Everyone know what tic-tac-toe

is? Yeah, which category is

tic-tac-toe? Is it a game which Player 1 can

force a win, or is it a category in which Player 1 can only force

a tie, or is it a category which you’d

rather go second and Player 2 can force a win for Player 2 or

a loss for Player 1? Which is tic-tac-toe?

Let’s have a show of hands here. Who thinks tic-tac-toe is a

game in which Player 1 can force a win?

Who thinks tic-tac-toe is a game in which Player 1 can only

force a tie? Who thinks Player 2’s going to

win? Most of you are right.

It’s a game in which if people play correctly then it’ll turn

out to be a tie. So tic-tac-toe is a game that

leads to a tie. Player 1 can still make a

mistake, in which case they can lose.

Player 2 can make a mistake in which case they would lose,

but there is a way of playing that forces a tie.

So these are fairly simple games, let’s talk about more

complicated games. So what about the game of

checkers? So the game of checkers meets

these conditions. It’s a two player game.

You always know all the moves prior to your move.

It’s finite: there’s some rules in checkers

that prevent it going on forever.

And there are two or three outcomes: I guess there’s a

third outcome if you get into a cycle you could tie.

So checkers fits all these descriptions and what this

theorem tells us is that checkers has a solution.

I’m not sure I know what that solution is, or I think actually

somebody did compute it quite recently,

even in the last few months, I just forgot to Google it this

morning to remind myself. But what this theorem tells us

even before those people that computed it: checkers has a

solution. Let’s be a bit more ambitious.

What about chess? So chess meets this description.

Chess is a two player game, everybody knows all the moves

before them, it’s sequential, it has finite number of moves,

it’s a very large number but it is finite, and it has three

possible outcomes, a win, a loss, or a tie.

So let’s be careful, the reason it’s finite is that

if you cycle–I forget what it is–three times then the game is

declared a draw, declared a tie.

So what’s this theorem telling us?

It’s telling us that there is a way to solve chess.

Chess has a solution. We don’t know what that

solution is. It could be that solution is

that Player 1, who’s the player with the white

pieces can force a win. It could be that Player 1 can

only force a tie, and it could even be that

Player 2 can force a win. We don’t know which it is,

but there is a solution. There’s a catch to this theorem.

What’s the catch? The catch is it doesn’t

actually tell us–this theorem is not going to tell us what

that solution is. It doesn’t tell us how to play.

This theorem, in and of itself,

doesn’t tell us how to play chess.

It just says there is a way to play chess.

So we’re going to try and prove this.

We don’t often do proofs in class, but the reason I want to

prove this particular one is because I think the proof is

instructive as part of sort of QR at Yale.

So here’s another example here, and some other examples.

You could think of chess as being the most dramatic example. So the reason I want to spend

actually some time proving this today is because we’re going to

prove it by induction and I’m going to sketch the proof.

I’m not going to go through every possible step but I want

to give people here a feeling for what a proof by induction

looks like. The reason for this is,

my guess is, well let’s find out,

how many of you have seen a proof by induction before?

How many have not? So for those of you who haven’t

I think it’s a good thing in life, at one point in your life

to see a proof by induction, and for those who have,

my guess is you saw it in some awful math class in high school

and it just went over–it didn’t necessarily go over your head

but, the excitement of it doesn’t

catch on. This is a context where it

might appeal. So proof by induction.

We’re going to prove this by induction on the maximum length

of the game and we’ll call that N.

We’ll call N the maximum length of the game.

What do I mean by this? If I write down a tree I can

always look at all the paths from the beginning of the tree

all the way through to the end of the tree.

And I’m going to look at the path in that particular tree

that has the largest length, and I’ll call that the length

of the game, the maximum length of the game.

So we’re going to do induction on the maximum length of the

game. So how do we start a proof by

induction? Let’s just remind ourselves,

those people who have seen them before.

We’re going to prove that this theorem this true,

the claim in the theorem is true for the easy case when the

game is only 1 move long. That’s the first step,

and then we’re going to try and show that if it’s true for all

games of length