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