Alan Turing is regarded as the founder of the field of modern computer science, and in fact the “Nobel prize of computing,” the Turing Award, is named after him. In fact, while Turing was busy decoding German messages during World War II at Bletchley Park in England using the new electronic programmable computers, he would often relax by playing chess and thinking about how a computing machine might play chess. Hugh Alexander, a fellow cryptanalyst and an English chess master who had just won the British championship in 1938, was often his playing partner. (Turing was actually quite bad at chess, ironically, so much so that Alexander would regularly beat him with queen odds!) Turing thought deeply about how to program a computer to play chess, which requires telling it how to look ahead for many moves and assess the positions. This lead to the first serious thinking about the total number of unique games of chess that are possible.
The problems in estimating the total possible chess games are manifold, including the most obvious one: the huge number of possible moves available for each player at every turn. Just the first full move (which consists of two ‘ply,’ or a move by white and a move by black), has 400 possibilities! This is easy to calculate, given that white has 20 moves (16 pawn moves and 4 possible knight moves), followed by any one of the same 20 type of moves by black. Any of 20 moves by white can be met by any of 20 moves by black, giving 20×20 total unique combinations of two moves
Moving on to the second move for white, we see things already get substantially more complicated. For white, we have roughly the same 20 moves still, but we have to account for new possibilities and restrictions given the first moves by white and black. For instance, if either rook pawn was moved just one square, then a rook could now make the second move. But, the knight on that side would now be restricted to one possible move. If the rook pawn was moved two squares, the rook could make one of two moves for white’s second move, and the knight is still free to make two moves. If the queen pawn is moved one square, the queen’s bishop could make one of five moves, the queen could move one square, or the king could move to Q2 on the second move, as well. Lastly, depending on what black did, it could be that we lose the ability to move a pawn again, e.g. if white’s first move was P-K4 and black’s was the same, then white can not move the king’s pawn again on the second move since it’s blocked. Taking all these various options into account, which is still not too difficult, we have 8902 possible ways of playing the first 3 ply (2 moves by white and 1 by black), and then 197,281 possibilities for 4 ply (or 2 full moves). To put this in perspective, if you took just 10 seconds for each possible set of the first two full moves, it would take more than 3 weeks going 24/7 to play out all the openings!
On the third ply is where we can begin to see one of the main reasons why the ultimate number of unique chess games is virtually impossible to calculate: the possibility of repeating moves with the same piece. If white moved a rook to R2 on the second move after moving the rook pawn, then on the third move white could just move it back where it started. Of course, the rules of chess say if the total chess board repeats the same position three times, the game ends in a draw, but if black is not repeating moves, white can repeat a move as long as they possibly can. There is also the 50-move rule, which states that if a pawn has not moved nor a piece captured in 50 moves, either side may claim a draw. While it is true that moves by either side could not be repeated indefinitely before a 50-move draw or repeated position could be claimed, even with intervening other moves or piece captures, it is virtually impossible to account for all the possible games when such ultimately silly variations are allowed. One can easily envision games where no pawns or pieces are taken for 49 moves (without the same position repeated 3 times), and then a pawn is moved and the whole things starts again for 49 more moves. A game could easily last legally for thousands of moves if before every pawn move and every capture there is a string of 49 other types of moves. (The longest possible game has been the topic of many threads, but seems to be 5898 moves!)
Another complication that calls into question the whole notion of estimating the total possible game variations (or ‘game tree size’ as theorists call it) is that the same position can be reached by different variations of moves. For instance, the well-known Ruy Lopez opening position shown below can be reached by many different variations–many more than are apparent at first glance. It is easy to see that instead of opening the game with the king pawn moves as is customary, the knights could come out first, then the pawns and bishop. Or white could move the king pawn, but then black plays the knight and then his pawn. White could also play the bishop out before the knight. Shuffling these moves gives six different variations to reach the position at right. However, there are actually thousands of variations that lead to this exact position! They are mostly nonsensical, but just consider the crazy, complex position shown below, a position which could unwind itself and
still lead back to the simple Ruy Lopez position shown above. Granted, many pieces should have been captured along the way to reach this position, and both kings have lost their right to castle, but it’s still a logically possible game variation. (One could argue that it isn’t the same position, since the castling right is not in play; well, then you can just leave the kings and king rooks where they are and still have enough different variations to prove my point). It’s a lot of nonsensical possible variations like these that compose a vast chunk of the Shannon Number, the 10120 possible games discussed in my first blog post on this topic.
What seems to be a more relevant question is this: How many reasonable games of chess are possible? ‘Reasonable’ is taken to be simply that each side is trying to win, i.e. is acquiring material advantages when given the opportunity, knows how to win basic endgames, etc. In my next post on this topic, I’ll consider this easier question and compare it to the number of possible reasonable games in popular games like checkers and Scrabble.