Home 
Search 
Today's Posts 
#1




How many games of chess are there?
The only estimate I know of is Littlewood's. He deduced an upper bound
of 10^10^70.5.Has anyone produced a reasonable lower bound? 
#2




"Ray Johnstone" wrote in message ... The only estimate I know of is Littlewood's. He deduced an upper bound of 10^10^70.5.Has anyone produced a reasonable lower bound? Why is there an upper bound? There are a limited number of pieces and a limited number of squares, surely someone could work out every possible permutation from there and then just strike off all the illegal positions? 
#3




Ray Johnstone wrote: The only estimate I know of is Littlewood's. He deduced an upper bound of 10^10^70.5. In _Programming a Computer for Playing Chess_ (found in Levy's _Computer Chess Compendium_) Shannon estimates 64!/(32!*8!^2*2!^6), or roughly 10^43. Also see: http://mathworld.wolfram.com/Chess.html http://www.cs.berkeley.edu/~flab/che...positions.html http://www.research.att.com/cgibin/...i?Anum=A006494 http://www.research.att.com/cgibin/...i?Anum=A007545 http://www.research.att.com/cgibin/...i?Anum=A019319 http://www.combinatorics.org/Volume_...s/v11i2a4.html http://anduin.eldar.org/~problemi/papers.html http://ite.pubs.informs.org/Vol2No2/ChlondToase/ In my opinion, all of the above calculations are wrong. Because a game of chess can be infinitely long, there are an infinite number of possible games.  LONGEST POSSIBLE CHESS GAME CALCULATION: By Guy Macon http://www.guymacon.com/ Here is my calculation for the longest possible chess game before one of the players can claim a draw under FIDE rules. (If nobody claims a draw the players can continue to push pieces back and forth forever and the game is infinitely long  and boring to calculate.) See http://www.fide.com/official/handbook.asp?level=EE101 Note to the nonchessplayer: a "ply" is a black piece changing position or a white piece changing position. Chessplayers call ten black piece moving and ten white pieces moving "ten moves"/"twenty plies." Nonchessplayers often call the same sequence "twenty moves." To calculate the longest possible chess game before one of the players can claim a draw under FIDE rules: Start with 32 chess pieces. Move 100 plies, avoiding repeating positions. On ply 100, move a pawn or make a capture. Repeat N times until you make the last capture that leaves 2 kings. So how big is N? There are 30 100ply sequences ending with a capture. There are 96 100ply sequences ending with a pawn move. 8 of these sequences end with a pawn move that is also a capture. 1 of those sequences is only 98 plies long so that black can start taking his turn moving pawns and making captures. Assuming FIDE rules, that comes to a total of ((100*(30+968))1)=11799 plies until the game is over.                Here is one way of reaching the maximum number of moves in a chess game (see calculation above). Assume that each ply described has 99 or (in one case) 98 "wasted" plies between the plies described.. White advances his A,C,E,G pawns as far as they will go. Black advances his B,D,F,H pawns as far as they will go. White captures every black piece except 8 pawns, 2 knights, 1 bishop, one rook, and a King. The white pawns on A,C,E,G capture the knights, bishops and rook, passing and freeing the black pawns blocking them. The nowunblocked black pawns move forward, promote, and move into position to be taken by the white pawns on B,D,F,H, unblocking the black pawns on B,D,F,H. The nowunblocked black pawns move forward, promote, and are taken. Black now only has a king. (Here is the lone 98 ply sequence) The black king captures something, and the game continues a capture by black on every 100th ply. When black captures the last white piece, there are only the two kings left and the game is a draw after exactly (and no more than) 11799 plies. Comments/corrections are welcome. Guy Macon a href="http://www.guymacon.com/" http://www.guymacon.com/ /a  BTW, here is how to generate an infinite number of games: Push pieces back and forth 1,000 times, then checkmate. Push pieces back and forth 1,001 times, then checkmate. Push pieces back and forth 1,002 times, then checkmate. Push pieces back and forth 1,003 times, then checkmate. Push pieces back and forth 1,004 times, then checkmate. .... 
#4




On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon
http://www.guymacon.com wrote: Ray Johnstone wrote: The only estimate I know of is Littlewood's. He deduced an upper bound of 10^10^70.5. In _Programming a Computer for Playing Chess_ (found in Levy's _Computer Chess Compendium_) Shannon estimates 64!/(32!*8!^2*2!^6), or roughly 10^43. Also see: http://mathworld.wolfram.com/Chess.html http://www.cs.berkeley.edu/~flab/che...positions.html http://www.research.att.com/cgibin/...i?Anum=A006494 http://www.research.att.com/cgibin/...i?Anum=A007545 http://www.research.att.com/cgibin/...i?Anum=A019319 http://www.combinatorics.org/Volume_...s/v11i2a4.html http://anduin.eldar.org/~problemi/papers.html, http://ite.pubs.informs.org/Vol2No2/ChlondToase/ In my opinion, all of the above calculations are wrong. Because a game of chess can be infinitely long, there are an infinite number of possible games. Thanks for the advice, very helpful. But I think you are wrong about chess being infinite.The fiftymove rule declares a game drawn if there have been 50 moves without a capture or a pawn move. The tree stops branching. 
#5




In article ,
Ray Johnstone wrote: On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon http://www.guymacon.com wrote: In my opinion, all of the above calculations are wrong. Because a game of chess can be infinitely long, there are an infinite number of possible games. Thanks for the advice, very helpful. But I think you are wrong about chess being infinite.The fiftymove rule declares a game drawn if there have been 50 moves without a capture or a pawn move. The tree stops branching. You may have missed the part where he wrote, If nobody claims a draw the players can continue to push pieces back and forth forever and the game is infinitely long The point being one player or the other must *claim* the draw, it is not enforced automatically by anyone.  Gerry Myerson ) (i  u for email) 
#6




Gerry Myerson a écrit :
In article , Ray Johnstone wrote: On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon http://www.guymacon.com wrote: In my opinion, all of the above calculations are wrong. Because a game of chess can be infinitely long, there are an infinite number of possible games. Thanks for the advice, very helpful. But I think you are wrong about chess being infinite.The fiftymove rule declares a game drawn if there have been 50 moves without a capture or a pawn move. The tree stops branching. You may have missed the part where he wrote, If nobody claims a draw the players can continue to push pieces back and forth forever and the game is infinitely long The point being one player or the other must *claim* the draw, it is not enforced automatically by anyone. You hve never participated in a real tournament, have you? Referees do intervene, you know... If only to be able to draw the next round... 
#7




Ray Johnstone wrote:
Thanks for the advice, very helpful. But I think you are wrong about chess being infinite.The fiftymove rule declares a game drawn if there have been 50 moves without a capture or a pawn move. The tree stops branching. I read somewhere that there are certain rare position, where the analysis has revealed that one side can force a win, but not within the constraints of the 50 move rule. This book also said that consequently the 50 move rule is replaced by 100 move rule in these circumstances. I would welcome it, if any expert cares to shed more light on this ?? Cheers, Jyrki Lahtonen, Turku, Finland 
#8




Lee Harris wrote: Why is there an upper bound? There are a limited number of pieces and a limited number of squares, surely someone could work out every possible permutation from there and then just strike off all the illegal positions? Number of positions and number of games are two different questions. They do have one thing in common; many smart people making many calculations and coming up with many different answers. 
#9




Lee Harris wrote:
Ray Johnstone wrote: The only estimate I know of is Littlewood's. He deduced an upper bound of 10^10^70.5.Has anyone produced a reasonable lower bound? Why is there an upper bound? To say that something is an upper bound for a quantity just means that the quantity can't possibly be bigger than that. There are a limited number of pieces and a limited number of squares, surely someone could work out every possible permutation from there and then just strike off all the illegal positions? In theory, yes. In practise, this requires an infeasible amount of computation so we have to estimate. Dave.  David Richerby CyberGhost (TM): it's like a www.chiark.greenend.org.uk/~davidr/ haunting spirit that exists only in your computer! 
#10




Guy Macon http://www.guymacon.com wrote:
Ray Johnstone wrote: The only estimate I know of is Littlewood's. He deduced an upper bound of 10^10^70.5. In _Programming a Computer for Playing Chess_ (found in Levy's _Computer Chess Compendium_) Shannon estimates 64!/(32!*8!^2*2!^6), or roughly 10^43. I don't have a copy of the book to hand but that looks like an estimate of the number of positions, not games. Dave.  David Richerby Natural Flammable Monk (TM): it's www.chiark.greenend.org.uk/~davidr/ like a man of God but it burns really easily and it's completely natural! 
Reply 
Thread Tools  
Display Modes  


Similar Threads  
Thread  Forum  
rec.games.chess.misc FAQ [2/4]  rec.games.chess.misc (Chess General)  
rec.games.chess.misc FAQ [2/4]  rec.games.chess.misc (Chess General)  
USCF Catalogue Remainers  rec.games.chess.politics (Chess Politics)  
Lev Khariton: With Love and Bitterness  rec.games.chess.misc (Chess General)  
rec.games.chess.misc FAQ [2/4]  rec.games.chess.misc (Chess General) 