How Many Games of Chess?
This is tangentially related to crypto. I've been reading A.K. Dewdney's _The New Turning Omnibus_ recently to refresh my memory of all that stuff I learned in undergrad that I'm going to see again on the Comp Sci GRE shortly. :-) Anyway, I was glancing through the chapters on complexity, computabilty, and minimax trees, and I got to wondering something: how many possible games of chess are there? I know that it has to be a finite number, but I'm not sure how to go about finding this number. Any pointers would be appreciated.
First, I think there are a finite number of games only if all stale-mates are are required to terminate. Second, here's one way if `just walking the tree` is too boring for you: 0 - Start your computer on this while you hop in a starship and circle in local space at a significant fraction of C. 1 - Generate every legitimate board position (don't forget, pawns may be promoted to other pieces) without regard for playing games. A board position might be expressed as a 64 digit, base 13 number. More efficient representation is probable (and desirable). Plainly the number of board positions is something vastly smaller than 13^64 which is 1.96e71 or 196053476430761073330659 760423566015424403280004 115787589590963842248961 At this time, use two extra bits per state to note the mate condition. Additionally, the total number of games must be less than or equal to the total number of permutations of every possible board position. Thus the total number of possible chess games is something (again vastly) less than (13^64)! (i.e., factorial --- sorry, Mathematica found this a little too daunting to give me an estimate). 2 - Connect nodes with edges representing possible moves. For each position, there can be no more than 64 pieces that might move, and for each, no more than 63 possible results (including pawn promotion), so the maximum number of edges is (13^64)*64*63 or about 7.90e74. At this time, or slightly later, use the mate bits to indicate stale-mates. 3 - Remove all subgraphs unreachable from the distinguished node that represents the starting position. 4 - Count the number of distinct paths through the graph that end in a mate or a stale-mate. 5 - Land your spaceship, collect your answer and find out how much money accumulated in your hedge-fund while you were gone. Scott Collins | "That's not fair!" -- Sarah | "You say that so often. I wonder what your basis 408.862.0540 | for comparison is." -- Goblin King ................|.................................................... BUSINESS. fax:974.6094 R254(IL5-2N) collins@newton.apple.com Apple Computer, Inc. 5 Infinite Loop, MS 305-2D Cupertino, CA 95014 ..................................................................... PERSONAL. 408.257.1746 1024:669687 catalyst@netcom.com
This is tangentially related to crypto. I've been reading A.K. Dewdney's _The New Turning Omnibus_ recently to refresh my memory of all that stuff I learned in undergrad that I'm going to see again on the Comp Sci GRE shortly. :-) Anyway, I was glancing through the chapters on complexity, computabilty, and minimax trees, and I got to wondering something: how many possible games of chess are there? I know that it has to be a finite number, but I'm not sure how to go about finding this number. Any pointers would be appreciated.
First, I think there are a finite number of games only if all stale-mates are are required to terminate.
Second, here's one way if `just walking the tree` is too boring for you:
0 - Start your computer on this while you hop in a starship and circle in local space at a significant fraction of C.
1 - Generate every legitimate board position (don't forget, pawns may be promoted to other pieces) without regard for playing games. A board position might be expressed as a 64 digit, base 13 number. More efficient representation is probable (and desirable). Plainly the number of board positions is something vastly smaller than 13^64 which is 1.96e71 or
196053476430761073330659 760423566015424403280004 115787589590963842248961
At this time, use two extra bits per state to note the mate condition.
Additionally, the total number of games must be less than or equal to the total number of permutations of every possible board position. Thus the total number of possible chess games is something (again vastly) less than (13^64)! (i.e., factorial --- sorry, Mathematica found this a little too daunting to give me an estimate).
2 - Connect nodes with edges representing possible moves. For each position, there can be no more than 64 pieces that might move, and for each, no more than 63 possible results (including pawn promotion), so the maximum number of edges is (13^64)*64*63 or about 7.90e74.
At this time, or slightly later, use the mate bits to indicate stale-mates.
3 - Remove all subgraphs unreachable from the distinguished node that represents the starting position.
4 - Count the number of distinct paths through the graph that end in a mate or a stale-mate.
5 - Land your spaceship, collect your answer and find out how much money accumulated in your hedge-fund while you were gone.
Scott Collins | "That's not fair!" -- Sarah | "You say that so often. I wonder what your basis 408.862.0540 | for comparison is." -- Goblin King ................|.................................................... BUSINESS. fax:974.6094 R254(IL5-2N) collins@newton.apple.com Apple Computer, Inc. 5 Infinite Loop, MS 305-2D Cupertino, CA 95014 ..................................................................... PERSONAL. 408.257.1746 1024:669687 catalyst@netcom.com
Seems to me a simpler method would be to start at the end game and work backward. Start w/ a single piece and it has 64 positions. a game which ends w/ 2 pieces on the board has 64*63 possible positions, 3 pieces have 64*63*62 possible positions, and so on. The fact is that the end game is what defines a game of chess and not the infinitude of possible paths between the first and last move.
participants (2)
-
collins＠newton.apple.com -
Jim choate