X-Message-Number: 223
From att!la.tis.com!fermat!r Wed Sep 12 21:12:01 1990
Return-Path: <att!la.tis.com!fermat!r>
Received: from att.UUCP by whscad1.att.uucp (4.1/SMI-3.2)
	id AA01834; Wed, 12 Sep 90 21:12:00 EDT
Received: by att.att.com; Wed Sep 12 18:52:25 1990
Received: by la.tis.com (4.1/SMI-DDN)
	id AA06345; Wed, 12 Sep 90 15:51:20 PDT
Received: by rhmr.com (3.2/SMI-3.2)
	id AA16072; Wed, 12 Sep 90 15:31:40 PDT
Date: Wed, 12 Sep 90 15:31:40 PDT
From: fermat! (Richard Schroeppel)
Message-Id: <>
To: 
Subject: re: cryonics #222, chess

You wrote
> To understand why that may be, recall that the
> game of chess theoretically can be solved
> completely, but the combinatorial explosion in
> the game tree renders a complete solution
> impractical (within the anticipated lifetime
> of this universe anyway).

The number of possible chess positions is only around 10^40.  The number
of possible games has been estimated at 10^120.  (Since there are many
different ways of going between the various positions.)  To actually solve
chess, and prove the solution, only requires knowing the value of about
10^20 critical positions.  (Most of the 10^40 possible positions are very
unbalanced, with one side or the other clearly winning.)  We routinely hear
of computations that take 10^16 instructions:  The recent factoring of F9 was
estimated at ~100 computer years (distributed over a few hundred workstations);
a 3Mips machine will execute 10^14 instructions/year.  A 1Gips Cray would
execute 10^16.5 ins/year.  There is enough computer power already existing to
solve chess in a decade or so.  (Assumptions: Current capacity is 10^22
ins/year; 1000 instructions to process a position.)  Of course, chess isn't
an important enough problem to absorb all our computer resources.  But our
computers continue to get better every year.  I suspect we will see chess
solved long before we see anyone revived; say in 25 years.  With any luck,
the current universe should last that long.  On the other hand, GO looks hard.
(Picky, picky, picky ...)

Rich Schroeppel


[ Rich, thanks for the enlightening figures.  The next time I need an example
  of an exceptionally combinatorially difficult problem, I will choose
  something other than chess.  By the way, how hard is GO? ... - KQB ]

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=223