Subject: number of legal chess positions From the Encyclopedia of Integer Sequences: %I A007545 M5100 %S A007545 1,20,400,8902,197742,4897256,120921506,3284294545,88867026005 %N A007545 Number of chess games with $n$ moves. %R A007545 ken. thompson %K A007545 fini %O A007545 0,2 %A A007545 njas - - - - - - - - - - - - - - - - - - - - - - - The following game position estimates are well-known: Chess: 10^43 The estimate 64!/(32!*8!^2*2!^6) ~= 10^43 is given by Shannon in his seminal paper "Programming a Computer for Playing Chess", Phil. Mag. 41 (1950) 256-275 (also in D. Levy's "Computer Chess Compendium"). As most everyone knows, we are far from solving the game of chess. Checkers: 10^18 For checkers, Jon Schaeffer estimates 5*10^20 plausible positions with 10^18 reachable under the rules of the game. But solving may require only the square root of the number of positions in the search space i.e. 10^9. The trick is finding which 10^9 positions to use. His World champion program Chinook has access to all 8 piece databases (444 billion positions). [source: rec.games.chess.computer 7/17/95]. Thus there is hope that some day checkers may be solved. Merrils: 10^10 Merrils (Nine Men's Morris) has been solved, see the URL below. As might be expected, the number of positions (size of the state space) is thought to be a good measure of the complexity of these games. For further details see the following excellent survey on exhaustive search: ALL THE NEEDLES IN A HAYSTACK: CAN EXHAUSTIVE SEARCH OVERCOME COMBINATORIAL CHAOS? Location: http://nobi.ethz.ch/febi/ex_search_paper/paper.html Here's a relevant excerpt: Although a direct comparison of different enumeration problems is not easy, due to their state spaces of different structure and varying connectivity, it is striking that at present, the size of state spaces of various solved problems, including Merrils, is of the order of 10^10 positions. The empirical fact that the raw size of the state space is the dominant parameter that affects complexity might be explained by the observation that the structure of all these spaces shows no regularity - they appear to be random graphs. Without predictable regularity to exploit, all exhaustive searches look like random walks in a random graph. Thus, the most telling indicator of complexity is the size of the space, and its connectivity is second. Finally I'll leave you with this excerpt: Exhaustive search is truly a creation of the computer era. Although the history of mathematics records amazing feats of paper-and-pencil computation, as a human activity, exhaustive search is boring, error-prone, exhausting, and never gets very far anyway. As a cautionary note, if any is needed, Ludolph van Ceulen died of exhaustion in 1610 after using regular polygons of 2^62 sides to obtain 35 decimal digits of Pi - they are engraved on his tombstone. -Bill Dubuque, 15. Aug. 1996