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