---------- | 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 -