How many chess games are possible?


How many games of chess are there?
So, there is a popular fact that
the number of games of chess is greater
than the number of atoms there are in the observable universe.
This is the fact. Is it true?
Well, the number of games of chess is known as Shannon’s number
so let’s find out what is Shannon’s number, and how it was worked out.
Claude Shannon. He… in the 1950s he wrote a paper “How to program a computer to play chess”
…It was about how to program a computer to play chess.
And in that paper he came up with an estimate for how many games of chess there are
So it is only an estimate.
So he estimated that the number of games of chess would be
Ten to the power…round about ten to the power 120
Which is… well, just massive! It’s billions and trillions of googles
It’s so massive, that’s a huge number.
If we compare that with atoms in the observable universe
there’s about ten to the 80 atoms in the observable universe
so there are more games of chess
You could assign billions of games of chess for each atom in the universe.
How did he come up with this massive figure?
So what he decided was, well, he looked at some games of chess and he said
Well, on average, at any position, there are about thirty legal moves that you can make.
So, the first player would have thirty legal moves he could make
And if you do two moves, that’s the first player then the second player
Then that would be, for each move by the first player
the second player would have thirty.
so if was only two moves
It’d be thirty by thirty
So that would be NINE HUNDRED already, just with two moves
Some terminology here: when I’m saying *moves* I actually mean what is called a *ply*
That means that one player goes first, then the second player goes next, then the next player…
So in chess terminology a move is the white player then the black player
So another move would be the white player again, the black player again.
But we’re just going to say *moves* to be: each player takes a move
It’s actually called a ply in chess terminology.
So if the first player has 30 legal moves he can make
Then for each move the second player has another 30 legal moves he can make
So with just two moves there are nine hundred moves you can make altogether.
If it was three moves, it would be 30 by 30 by 30
If it was four moves, it would be 30 by 30 by 30 by 30.
Shannon said, Well, a game is about 40 moves.
Ah, that was in chess terminology, so he means 80 plays.
So…
This is all Shannon did, he said
A game is about 30 legal moves…
80 plays
and that is around about 10 to the 120.
BRADY: Well that is the most wishy-washy…
JAMES: Yeah. It was only in passing, it was only an estimate, it was only a paragraph of the paper
And he did this rough estimate, this rough number, to show that if you had a computer
and it was trying to work out then the future of the game, and trying to work out
all the legal moves and where this game was going to go
so that it could make decisions, sort of, how to play next…
Then, the computer would never make a move
If it was calculating one game per microsecond it would be until the end of the universe
it would never play. This was the point Shannon was trying to make with this rough estimate.
So we’re going to have a look at a sequence of games there are when each player takes their turn.
So the first move is by white.
So…let’s take the first move, and white has twenty legal moves.
So we’ve got…we’ve got one here for each pawn, so that’s eight.
We’ve got the double move there by each pawn, so we’ve got sixteen.
We’ve got two moves there for each knight…two moves on this side here and here…
And that’s twenty.
So, twenty moves for the first player. Now black takes the next turn
And for the next turn he can respond with the same twenty moves.
So for each move player 1 takes, black can take twenty moves, so you multiply, it’s 20 by 20…
There are now 400 games that could have happened, already.
With just two moves there are already 400 games that could have happened.
Let’s see what happens next. Then suddenly it becomes much more complicated.
When white plays next it becomes…8902 moves. Suddenly, phoof! 8000, well, nearly 9000 games that you can play, with just 3 plays.
BRADY: This sounds a lot more precise than what Shannon was doing, this is real numbers.
JAMES: Yeah, these are real numbers. With these small numbers we can work this out.
So far so good — it’s going to get harder with larger numbers.
So, let’s write out a few more.
The next move is black, and he’ll have 197,742.
So after black moves again we now have 197,742 possible games that could have been played.
All the possible games we could have done in those four moves is already 200,000.
BRADY: This is crazy.
JAMES: Huge numbers already, huge numbers.
BRADY: Although, you are able to know exactly what the number is, so it just seems like
if you spend enough time on this you’ll be able to…
JAMES: So OK, we can keep going can’t we? So we can keep going
and these numbers are going to get bigger and bigger
Now, in theory, the total number, the largest number, the longest chess game can be…
something around 11,800 of these plys.
11,800.
That’s invoking though, you have to invoke the 50 move rule, cause you could just go on forever,
if you just ended up with two kings, just going backwards and forths.
A game could last forever. So there is a rule that stops a game lasting forever that says:
Well, if you’ve played 50 moves with nothing being captured, and you’re just messing about–
BRADY: Or a pawn being moved, isn’t it.
JAMES: Yeah it’s a pawn hasn’t moved, something hasn’t been captured,
or you repeat the board three times. If that happens then you call it a draw.
So there’s a cut-off point. Now some people have worked out what the longest possible chess game is…
It’s something around 11,800. There’s some disagreement, not much disagreement though,
Within, a hundred or so of that.
So if you see how fast this sequence is growing, can you imagine how many games there are
altogether. Especially when you’re going all the way up to nearly 12,000 moves.
Some of those games would be nonsense games, where you can win,
you’ve only got one move left and you can win in one move, but you don’t,
you start moving other pieces and you start doing other things.
It becomes a massively complex tree of possibilities
and that’s why this number is, just, going off to a HUGE numbers.
Godfrey Hardy, a famous 20th century mathematician
He tried to estimate the number of chess games there were.
His estimate was ten to the power ten to the power fifty.
Let me say that again: it was 10^(10^50).
This is miniscule when you compare it with what Hardy’s estimate was.
What Shannon was doing was saying, “This is a forty move game, where the average number of moves is thirty.”
So he was saying that if there were 80 plays, that’s what he’s saying,
He’s saying this is about ten to the power 120.
That’s what Shannon is saying.
So he’s not even considering all these other games.
So it was Godfrey Hardy, the famous 20th century mathematician – worked at Cambridge, discovered Ramanujan,
He tried to estimate how many games of chess there were.
It was actually when he was writing about Ramanujan, cause Ramanujan had sent him a paper which had a large number in it
He said, “Just to understand how big this number is, if you compare it to the number of games of chess
I reckon that’s 10^(10^50).”
Was Hardy close? I don’t know. He didn’t give any working out for this, this was in passing
I did say a lot of these would be nonsense games; let’s try some sensible estimate.
If it was, let’s say if each player had an average of three sensible moves,
instead of thirty legal moves. Same sort of idea. If we did that…
So instead of 30^80 it would be, say, 3^80. Does that seem more reasonable? Yeah?
So that’s 3^80, I can tell you that’s around about 10^40. So now not as large as the number of atoms in the observable universe
Still, still very large though, 10^40.
If for example, everyone in the world paired off and they had to play a game of chess every day
and it had to be a different game every day, and they did that…
To play all possible games, this 10^40 sensible games
it would still take you trillions and trillions of years to play them all.
Or if you think about it another way
If we consider all games of chess that have ever been played in history,
then that is only a tiny fraction of all the possible games of chess there are to play.
BRADY: I can’t think of a better supporter for a video about chess than a company called squarespace.
Now if you want a presence on the web, whether it’s a blog, a business, or just a cool way to tell the world about what you’re doing,
then squarespace is a super resource.
I host my own blog on squarespace, and it’s so quick and hassle-free.
In a matter of minutes I can have anything up on the web, looking great —
and that’s looking great on both computers and mobile devices, which is often the hard bit.
Now whether you’re a bit of a novice, or you are a coding grandmaster
squarespace will give you as little or as much control as you like.
So whatever your endgame, you really should…check them out (see what I did there? “check them out”).
“endgame”, it’s pretty good that. Anyway.
They’ve got a great range of templates to get started. Then you can tweak them, play around until your heart’s content.
And I’m not just saying this because they’ve sponsored today’s episode
which they have, and thank you for that,
but I am a happy customer. Now you can have a 14 day free trial, give it a go before you commit, no credit card required,
and then if you do like them, you can get 10% off your first purchase.
Go to squarespace.com/numberphile
And thanks to squarespace for supporting this episode.
As they like to say, “Build it Beautiful”
BRADY: Do you play chess?
JAMES: I do play chess, I know chess, I’m no expert on chess, I’m no grandmaster.
I play chess for fun perhaps. I used to play chess with my dad.

100 Comments

Add a Comment

Your email address will not be published. Required fields are marked *