From: tcmay@netcom.com (Timothy C. May)
Date: Fri, 1 Apr 94 11:30:47 PST
To: cypherpunks@toad.com
Subject: Number of Legal Chess Games
Message-ID: <199404011931.LAA18398@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



On the question someone asked about the number of chess games...

My recollection is that a fairly careful calculation of the number of
legal games between good players (see Note below) is about 10^140.

The number of legal Go games is vastly larger, around 10^700. (Each
board position has far more branch positions, the Go board being 19 x
19.)

I have a bunch of Go books, and some computer chess books (Levy), but
I can't find the calculation referenced. It's not a "plug in"
calculation, either, as a lot of empirical cruft (good moves, winning
configurations, etc.) gets taken into account. But I think the basic
estimate of around 10^140 is well-accepted. It might be as "low" as
10^120 or as "high" as 10^160, for example, but that's the right
ballpark, from what I've seen.

As a reminder, it is estimated that there are about 10^72 particles in
the entire universe. Thus, about 10^60 games of chess for each and
every particle in the universe. The situation with Go is even more
extreme. Welcome to the strange and exciting world of combinatorial
explosion. 

(Note: If two infinitely powerful agents played, the number would
presumably drop, as each would see the implications--chess not being a
game of chance--of who made the first move and one side would resign.
Lesser agents would have more games, presumably. Even lesser agents,
novices, might eventually have _fewer_ games, as the games stumbled
into wins earlier on. A novice against a grandmaster should also have
far fewer games. as the grandmaster wins quickly. At what point of
expertise the "maiximum" number of games exists is an interesting
question.)

For further info, I'd recommend the many good books on computer
chess....I'm sure that some of them sketch out how these calculations
are done. I've recently seen several new books on computer Go and
computer chess, which technical bookstores and libraries should have.

Also, asking on rec.games.chess and rec.games.go might produce better
results than here on Cypherpunks. The question might well even be in a
FAQ for rec.games.chess...now I'm curious about this and will go
check.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."