🚀 go-pugleaf

In article <9e1g6o$4fs$1@oprah.cc.utexas.edu>,
Russell <rreagan@mail.utexas.edu> wrote:
>Chess is a game that is not going to be solved (i.e. the complete search
>from opening until ending) with current technology.  You can add a million
>processors, and it might help, but it would take billions of years to
>complete a search of this size even if you took every computer in the world
>and put them working on this one problem.

	Let me put some figures on this.  Currently, programs search
some 14, 15, 16 ply deep with luck [except when they get near the
endgames databases] plus extensions ... let's be generous and call
that seeing "everything" within 10 full moves [20 ply].  Let's speed
everything up by a million;  that gives 4 extra ply full search, 4 full
moves with alpha-beta and good move ordering, a bit more with selective
searches and good hash tables, blah, let's call it 6 full moves -- no,
we'll be generous and call it 8.  Add a million processors, and with
extreme generosity, that's another 8 full moves [that's over-generous,
as hash tables don't share that easily, you have comms problems with
so many computers working on a problem that's somewhat parallel but
also somewhat sequential].  Wait a year, a million half-minutes, and
you see another 8 full moves.  Wait a billion years, that's another
12 full moves.  You can "solve" chess that way *only* if the initial
position is a forced mate in 10+8+8+8+12 = 46, or without the extreme
generosity 8+4+4+4+6 = 26.  In a normal lifetime, you're several
moves short of that.  Give every family on earth such computing power
and a billion-year's worth of patience, and you're up to around 58
[or, more realistically, 32].  That's more like a plausible length
of a well-contested game, but bear in mind that strong players will
usually agree a draw or resign once the result is clear to them, which
is usually a *long* way before mate or a formally drawn position.  If
chess is actually mate in, say, 70, then with our extreme generosity
we will see it solved by every family on earth sitting round a computer
that is a thousand billion times as powerful as today's PCs and waiting
for a billion billion years.  {You gain a bit if the forced mate hits
the endgame databases -- relatively unlikely.]

	Summary:  if chess is to be solved, then realistically that
will happen if [implausibly] there is a forced mate in 30 or so from
the start that no-one has yet spotted, or [implausibly] there is a
complete theory [compare Nim -- but chess seems "chaotic"] which
no-one has yet spotted, or [only a little less implausibly] there is
some completely unforeseen technology that speeds our computations up
by factors of 10^30 and more.

>					    Not to mention the space required
>to store the information simply does not exist.

	Space, as such, isn't *that* much of a problem.  You only *need*
to store the current principal variation and the current line being
searched in each computer, and that's "trivial" even with a few million
computers and very long games [there are million-game databases!].  Of
course, the more space for hash tables and endgames datbases the better.
If the computer returns its first move in [say] a year, then you perhaps
won't mind waiting a mere month to compute its second move even from
absolute scratch and a few days for its third move, etc.

>I read some articles on new expiremental technology, that in "theory", will
>allow us to solve problems that would take our current technology billions
>of years to be solved in minutes.  [...]

	Quantum computation *could* be the answer.  After all, the
Universe manages to "compute" its own future, despite the limitations
of general relativity and the uncertainties of Heisenberg -- and does
it very precisely *and* in real time!  Amazing -- how does it do that?
Well, no-one knows, apart from the epistemological argument that says
that that's the definition of real time.  "Pass" on that one!  But it
seems very implausible *today* that we could create an environment
stable enough to allow a discrete quantum state to model the state of
the entire game tree of chess.  If we could, then we can do the search
genuinely in parallel and solve chess in time proportional to the depth
of the tree.  But it's a very big "if".

-- 
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
anw@maths.nott.ac.uk