but now the sun shines cold and all the sky is grey (the cure) the stars are dimmed by clouds and tears and all i wish is gone away -- all i wish is gone away On Fri, 1 Apr 1994, Mike Markley wrote:

---------- | From: Lefty <netmail!lefty@apple.com> | To: <cypherpunks@toad.com> | Subject: Re: How Many Games of Chess? | Date: Friday, April 01, 1994 9:31AM | | Received: from relay2.UU.NET by netmail.microsoft.com with SMTP (5.65/25-eef) | id AA25823; Fri, 1 Apr 94 09:50:19 -0800 | Received: from toad.com by relay2.UU.NET with SMTP | (5.61/UUNET-internet-primary) id AAwjtu01006; Fri, 1 Apr 94 12:44:37 -0500 | Received: by toad.com id AA11484; Fri, 1 Apr 94 09:33:09 PST | Received: from colossus.apple.com by toad.com id AA11477; Fri, 1 Apr 94 09:33:01 PST | Received: from [90.1.0.18] by colossus.apple.com with SMTP (5.65/8-Oct-1993-eef) | id AA17501; Fri, 1 Apr 94 09:31:21 -0800 | Received: from lefty.apple.com by gallant.apple.com with SMTP (5.64/27-Sep-1991-eef) | id AA18102; Fri, 1 Apr 94 09:31:18 PST | for cypherpunks@toad.com | Message-Id: <9404011731.AA18102@internal.apple.com> | Mime-Version: 1.0 | Content-Type: text/plain; charset="us-ascii" | Sender: netmail!owner-cypherpunks@toad.com | Precedence: bulk | | >This is tangentially related to crypto. I've been reading A.K. Dewdney's | >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. | | It doesn't seem to me that this _can_ be readily calculated in any | reasonable amount of time. It's not a simple (realtively) combinatorial | problem: the configuration of the board at any given point limits the legal | moves in an extremely nontrivial way. | | I believe I can get you as far as the second move, though: I make it to be | twenty-one possible openings and twenty-one responses. | | -- | Lefty (lefty@apple.com) | C:.M:.C:., D:.O:.D:. | | |

I seem to remember from way back in high school that the number of potential moves by the third set of moves is on the order of billions of legal moves. I am also pretty sure that it is not exponential but a factoral growth. I don't think that it is possible to determine every possible game.

Mike -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Mike Markley || The opinions here do not represent the mmarkley@microsoft.com || opinions of my employer. Attempts to || associate the two are pointless.

"I want to look at life, In the available light" - Neil Peart -

Not to mention all of the repeating- non-ending games Shadow p.s. i wonder if there is a "irrational" game....one that goes on to infinity but never repeats itself.....I would imagine not as there are only a finite number of possibilities for peices to exist on the board it was an interesting thought whie it lasted....

mmarkley@microsoft.com writes: I seem to remember from way back in high school that the number of potential moves by the third set of moves is on the order of billions of legal moves. The number of moves in a given chess position is less than 64 (number of starting squares) times 64 (number of destination squares) x 4 [number of ways a pawn can promote]. Thus we get the bound 16, 384 [which can be easily improved] which is way less than "billions of possible moves". The same computation shows that the number of possible games of length n grows at worst expoentially pace mr markley. The right way to think about this is to get sharp upper bounds rather than attempt a precise calculation. A crude upper bound would be longerst possible game is about 6000 moves [using the 50 move rule]. At most 2**16 mves per position so at most 10**[192 * 10**6] games. I'm sure that sharper estimates are readily available.