

Subject:
Maximum number of possible chess games
Category: Science > Math Asked by: delardga List Price: $50.00 
Posted:
19 Aug 2004 03:18 PDT
Expires: 18 Sep 2004 03:18 PDT Question ID: 389840 
Chess is a finite game  the 50 move rule and the 3 repeating positions rule mean that no game can go on forever (in fact the maximum game is something under 6000 moves I think?). Therefore there are a finite number of distinct possible games (a distinct game being characterised by a distinct sequence of moves). However this is clearly a very big number :). I want to find the smallest upper bound of this number. In a book by Hardy he claims in a footnote that this number is around 10^(10^50)  however I'm sure this is far too big! To answer the question please state the smallest upper bound you can find  and justify it sufficiently that others can verify it is correct. If this is answered, I may repost the question with the aim being to find a new lower number. Thanks  Delard  


There is no answer at this time. 

Subject:
Re: Maximum number of possible chess games
From: delardga on 19 Aug 2004 05:06 PDT 
I figured it was an interesting question  people may have a look more out of curiosity than money. Anyway  OK then  I'll up it a bit. 
Subject:
Re: Maximum number of possible chess games
From: delardga on 19 Aug 2004 05:07 PDT 
and its not that hard to come up with an upper bound  it doesn't have to be that complicated... 
Subject:
Re: Maximum number of possible chess games
From: pinkfreudga on 19 Aug 2004 09:48 PDT 
Here's a very interesting essay that discusses an algorithm for finding the number of possible games (scroll about halfway down the page to "THE SECOND WANT"): http://www.iw.net/~a_plutonium/File127.html 
Subject:
Re: Maximum number of possible chess games
From: racecarga on 19 Aug 2004 11:02 PDT 
First the maximum game length: I don't know what this number is, but an upper bound is easy. The 50 move rule states that a game is drawn after 50 moves (by each player) during which no capture is made and no pawn is moved. There are 16 pawns which can each be moved at most 6 times. There are 30 pieces which can be captured. Therefore a game cannot be longer than (6*16 + 30)*50, or 6300 moves for each player. That's 12600 moves total. Second, the maximum number of distinct moves possible at any given time: each player has 8 pawns which can each make a maximum of 4 possible moves (forward 1, forward 2, capture left, captured right). That's 32 possible pawn moves. Each knight commands at most 8 squares, for a total of 16 possible knight moves. Each bishop commands at most 13 squares, each rook at most 14, the queen at most 27, and the king at most 8. Then there are 2 possible castling moves. So the maximum number of moves which could ever be available is: 32 pawn moves 16 knight 26 bishop 28 rook 27 queen 8 king 2 castling  139 Therefore, a (not very low) upper bound on the total number of possible games is 139^12600, which is slightly less than 10^27002 So, my upper bound is 10^27002. 
Subject:
Re: Maximum number of possible chess games
From: racecarga on 19 Aug 2004 11:22 PDT 
Some slight improvements: The a and h pawns never have more than 3 moves available, so the maximum number of possible pawn moves available at any given time may be taken as 30 rather than 32. Each player can castle at most once, with 2 choices of how to do it. So we can get an upper bound for number of games without castling, and then multiply by the maximum number of moves, because that is the number of places we can 'insert' the castling move. We also multiply by 2, because of the 2 ways to castle. So an upper bound is: (upper bound w/o castling)*6300*2*6300*2. (multiply each factor twice, once for each player). Since we have taken away 4 moves (2 pawn moves and 2 castling) the maximum number of moves available is 135. So my new upper bound is 135^12600 * 12600^2, which is less than 10^26851. 
Subject:
Re: Maximum number of possible chess games
From: racecarga on 19 Aug 2004 11:49 PDT 
Also, the queen and bishops only command their maximum number of squares (27 and 13 respectively) from the central 4 squares of the board. The queen and both bishops cannot all simultaneously occupy these squares without blocking each other. From any other square, the queen commands at most 25, and bishops at most 11 squares. So we can drop the maximum number of available moves by 2. Actually by 4, if you check it out. So that's 131 moves total. But I just realized I forgot about pawn promotion. If you have more queens, say, you have more moves available. I'm sure this number can be improved upon, but with 9 queens, there are certainly never more than 317 moves available. (I just took out the pawn moves and added 27 for each queen). So now my answer is 317^12600*12600^2, which is less than 10^31522. 
Subject:
Re: Maximum number of possible chess games
From: delardga on 20 Aug 2004 01:45 PDT 
Great work so far! I've upped the money to encourage someone to take this a step further  ie improve on the smallest number so far. Please express results as 10^n for ease of comparison. 
Subject:
Re: Maximum number of possible chess games
From: racecarga on 22 Aug 2004 08:14 PDT 
The king never has more than 8 moves available even with castling, so we can take out the castling factors. At most one queen can cover 27 squares. The next one can cover at most 25, and the next one at most 24. So we can knock off 15 moves from the total. 302^12600 ~ 10^31248 
Subject:
Re: Maximum number of possible chess games
From: racecarga on 23 Aug 2004 16:41 PDT 
Found a reference that says the max game length is 5949 moves. If you believe this, then a better upper bound is 302^11898 ~ 10^29507 There are only 20 possible first moves (for white and black), which further drops the total to 10^29505. http://membres.lycos.fr/albillo/cboard01.htm has the maximum number of moves possible for a variety of combinations of pieces, but not for 9 queens. 
Subject:
Re: Maximum number of possible chess games
From: ben79ga on 06 Jan 2005 00:28 PST 
Furthermore, after 8 moves each pawns can promote to queens, rooks, bishops, or knights. For purposes of calculating an upper bound, the greatest number of permutations is most likely to result from promotion to queens. This leads to a maximum of 18 queens on the board assuming both sides promote all of their pawns to queens. However, they do tend to get in each others' way which reduces the number of possiblities quite a bit. Also you have to be careful not to checkmate (or stalemate) your opponent as this reduces the length of the game and thus the number of moves and permuatations. PS racecarOn a side note, the a and h pawns can move towards the center by capturing, where they can then potentially move to four squares like the other pawns. 
Subject:
Re: Maximum number of possible chess games
From: ben79ga on 06 Jan 2005 00:32 PST 
PPS and sometimes pawns can move to 5 possible squares, (once for the six middle ones of each color) 
Subject:
Re: Maximum number of possible chess games
From: racecarga on 09 Jan 2005 11:52 PST 
Seems to me, on a pawn's first move, it has at most 4 possible choices: forward one, forward 2, capture left, capture right. Any time after the first move, there are at most 3 possible moves for each pawn, if we don't count promotion to different pieces as different moves. Only three of the four starting moves are available to the a and h pawns. Yes they can move to a more central file by capturing, but then the forward two option will no longer be available, any they will still have only at most 3 moves available at any time, same as any other pawn. 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 