X-Message-Number: 224 From att!parc.xerox.com!merkle Thu Sep 13 21:34:06 1990 Return-Path: <att!parc.xerox.com!merkle> Received: from att.UUCP by whscad1.att.uucp (4.1/SMI-3.2) id AA08336; Thu, 13 Sep 90 21:34:05 EDT Received: by att.att.com; Thu Sep 13 20:46:21 1990 Received: from manarken.parc.xerox.com by arisia.Xerox.COM with SMTP (5.61+/IDA-1.2.8/gandalf) id AA27466; Thu, 13 Sep 90 17:51:26 -0700 Received: by manarken.parc.xerox.com (5.61+/IDA-1.2.8/gandalf) id AA02321; Thu, 13 Sep 90 17:48:43 PDT Message-Id: <> Date: Thu, 13 Sep 90 17:48:43 PDT From: Ralph Merkle <> To: Subject: Re: cryonics #223 - Re: Muscle Memory (Complexity of Chess) >By the way, how hard is GO? ... - KQB The last I heard, GO was polynomial space complete. This means it's possible to embed ANY two player game (such as chess) into a GO game. Of course, the proof used an NxN GO board, so this actually begs the question.... Roughly, a 19x19 GO board would have 3^(19*19) or about 174089650659031927907188238070564367946602724950263541194828118706801\ 0516761846498411627928898871493861209698881632078061375498718135509312\ 9514803369660572893075468180597603 possible positions (about 10^170). This is a lot more than the 10^40 chess positions! No doubt, a LOT of these positions are uninteresting. By comparison, the human brain has only 10^10 to 10^12 neurons, maybe 10^15 synapses, and about 10^26 atoms. Simple! We should have computers that make short work of this kind of problem within a century. [ Thanks for the numbers, Ralph. I'm beginning to see why the Extropians (Message #122) are getting so excited about the unfolding possibilities. Now back to cryonics ... - KQB ] Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=224