View Question
Q: Maximum number of possible chess games ( No Answer,   12 Comments )
 Question
 Subject: Maximum number of possible chess games Category: Science > Math Asked by: delard-ga 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``` Request for Question Clarification by techtor-ga on 22 Aug 2004 09:20 PDT ```Hello Delard, I wonder if you've seen this website already. Someone seemed to have tried calculating the maximum number of moves. I'm not sure if the number stated here is definite for you already: Sensei's Library: Number Of Possible Outcomes of a Game: http://senseis.xmp.net/?path=Speculation&page=NumberOfPossibleOutcomesOfAGame http://senseis.xmp.net/?diff=NumberOfPossibleOutcomesOfAGame```
 Answer
 There is no answer at this time.

 Comments
 Subject: Re: Maximum number of possible chess games From: delard-ga 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: delard-ga 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: pinkfreud-ga 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: racecar-ga 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: racecar-ga 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: racecar-ga 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: delard-ga 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: racecar-ga 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: racecar-ga 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: ben79-ga 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 racecar-On 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: ben79-ga 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: racecar-ga 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.```
 Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service. If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for

 Google Home - Answers FAQ - Terms of Service - Privacy Policy