How many chess games are possible? - Numberphile

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments
Captions
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.
Info
Channel: Numberphile
Views: 3,018,696
Rating: undefined out of 5
Keywords: numberphile, Chess (Game), shannon, Claude Shannon (Computer Scientist)
Id: Km024eldY1A
Channel Id: undefined
Length: 12min 11sec (731 seconds)
Published: Fri Jul 24 2015
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.