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