Shannon's number is an estimate of the possible number of games of chess, arrived at by the mathematician and engineer Claude Shannon (1916-2001). Shannon postulated an average of 1000 possible moves for one move by White followed by one move for Black. Then he postulated a typical length of a chess game of 40 moves, and came up with his very famous number, his very famous estimate: there are at least 10 to the 120th power possible different chess games.
I think Shannon's number is complete garbage. I think it tells us little beyond the fact that Shannon and other mathematicians didn't know much about chess, and that few chess players know much about math. Otherwise, Shannon's number would never have become famous to begin with, and, chastened by so much derisive laughter, he would've headed back to the drawing board to try again.
In some positions on the chess board, there are many possible moves. For White's first move, there are 20 possible moves: 16 by the Pawns and 4 by the Knights. 20 choices also for Black's first move. There are other position in which a player would have far move than 20 possible moves. For example, if a player had 3 Queens, 2 Bishops, 2 pawns and a lot of space.
In other positions, a player has only 1 possible move: if his King is under attack and there is one 1 possible way to defend it. Or if there is only 1 possible move which would not expose his King to attack. And there are positions where only 2 moves could defend the King against attack. Or 3, or 4, and so forth.
Or, instead of threats to the King, the number of moves could be limited by his pieces being blocked by his opponent's pieces, or by his own pieces.
How would one get an average number of moves out of all of these different kinds of positions? How many different positions are there with just 1 possible move? How many positions yield 50 or more possible moves? I have no idea. Not the faintest idea. Furthermore, I have yet to see anyone even asking this very basic kind of question when trying to determine the number of possible chess games. I'm not saying I'm the only person who's asked these questions. I'm saying that not enough people have been asking them insistently enough for the evidence of their existence to have come to my attention.
Okay, now, the number of moves in a game. Average it out at 40, like Shannon? That's ridiculous. Checkmate can happen after 2 moves, or 4 moves. It's not unheard of for checkmate to happen after 10 or 15 moves, or 20 or 30. Conversely, some games have gone on for hundreds of moves. Has anyone even attempted to calculate the number of ways in which a game could last for over 100 moves? Or the number of different ways in which a game could go on, limited by the rule that one player can claim a draw if 50 moves go by during which neither player captures and piece or moves a Pawn? Did you notice that I said that a player CAN claim a draw under those conditions? We may have to make such draws mandatory and automatic if we wish to make the number of different games finite -- or perhaps not, I'm not competent to say.
These are just a few examples of the different numbers which would need to be calculated before one could attempt to combine them all and come up with any sort of reasonable estimate of the number of possible chess games.
I don't believe that AI is here. I haven't seen a product designed by AI which wasn't hideously ugly, haven't read a poem written by AI which wasn't ridiculous, haven't interacted with a search engine or automated call center which wasn't infuriatingly stupid.
And I haven't seen an impressive attempt yet to estimate the number of possible games of chess, let alone solve the game by coming up with the moves which will always win, or always draw against perfect moves by the opponent, the way that checkers has just recently been solved. And when those things finally do happen, which they will if we don't kill ourselves off first, it being ultimately just a matter of crunching very, very big numbers, actual human-like communication and creativity will still be far off, or, perhaps, ultimately inaccessible to mathematics.
i strongly encourage you to actually read the paper Shannon wrote bc it addresses all your misgivings — Shannon and many, many people before him asked the same questions you are. Stockfish, for instance, uses an advanced variant (with the incorporation of neural net searches) of the minimax strategy Shannon outlines, and Stockfish is astronomically better than any human player to ever exist simply because it has access to far more data *and* because it has been hand-tuned over the course of decades.
ReplyDeletethe most complex "solved" game is checkers, and that's only _weakly_ solved: they've enumerated the possible board states at the end of a game (~39 trillion) with no more than 10 pieces, and are able to work backwards from each board state *playing perfectly* to find openings leading to wins/draws/losses. (the only criterion required to show a game has been weakly solved is that there exists an algorithm which can determine the terminal position of an arbitrary opening, *not* that every arbitrary opening has a determined terminal state.) chess presents additional barriers by having different pieces with a wider variety of moves; enumerating terminal board states is extremely difficult and, as of right now, we've only computed these for up to seven pieces. you are nearly right that it's "just a matter of crunching really big numbers," but the problem is that we have to find out what numbers to crunch.
because there are so many possible terminal board states, there's no concentrated mathematical effort to estimate their number. in fact, this is central to Shannon's argument: we don't even need to know how many terminal board states there are to create a program that's really good at chess, we just need to be able to figure out how many possible moves (or 2-move combos, or n-move combos) we can make from a given board state and compare their relative values (based on captures/positions of pieces/etc.), then pick the move which either gives us the greatest advantage or gives our opponent the greatest disadvantage.
seriously though, go read Shannon's paper and the Science paper outlining the solution for checkers.
Thanks very much for your comment. I appreciate the effort -- it's almost as long as the post! I really should have read Shannon's paper first. Especially since I tend to get on people's cases for not knowing primary materials. I can't promise you when, but I will try to read the paper and then get back to you again.
DeleteWell! That took a while. First it took me several days to get around to reading Shannon's paper, and then for q quite a while I couldn't comment on my own blog for some mysterious reason. You were absolutely right: Shannon goes into a great deal of detail in his paper regarding the complexity of the calculation of the number of possible games of chess. His math is over my head.
Delete