Re: How long would it take a computer to completely "solve" chess?

From: KRamsay (kramsay_at_aol.com)
Date: 09/14/04 

Date: 14 Sep 2004 09:46:42 GMT

In article <10kd0h4obtand2e@news.supernews.com>, Guy Macon
<http://www.guymacon.com> writes:
[...]
|Try calculating how many qubits it would take instead of calculating
|how many atoms it would take.

The problem is that we don't have much more reason to expect a
big speed-up from using a quantum computer, than we have to expect
a big speed-up from using some clever algorithm on a classical
computer. The kind of tree search one needs to do generally requires
solving a PSPACE-complete problem, which is expected to require
exponential time whether the computer is quantum or classical.

|>What´s your "likely between a few minutes and a few days" based on?
|
|It is based on the work of Lov Grover of AT&T’s Bell Laboratories,
|who proved that if a conventional computer can do a search of N
|items in T time, a quantum computer can search N2 items in T time.

Indeed, but we're talking about two different kinds of "search" here.
The accelerated search for quantum computers is for a "search" in
the sense of locating some one identifiable element in a table. The
"search" for evaluating a game position isn't just for finding some
one path through the tree that you can recognize. It's for doing a
minimax evaluation.

|I am conjecturing that a quantum computer that can solve chess will
|be created sometime before the end of the universe.
|
|I am conjecturing that an algorithm will be created sometime between
|now and the end of the universe that will allow a search of the chess
|game tree to be done using something as fast as Grover's method.

Because you think there are sub-exponential quantum algorithms
for PSPACE-complete problems, or because you think the 8 by 8
board is small enough to make it tractible, or...?

|A Quantum Computers (if a practical one is ever invented) will be
|able to perform 2^N operations in N time.

An N qubit quantum computer can, in a certain sense, be
"doing 2^N things at once". But there's no reason to think
that it can do everything that one could do on a classical
machine using 2^N operations. The algorithms which let it
do things classical computers can't do as quickly, work by
interference effects, with the amplitudes for the undesired
(incorrect) answers cancelling out, and the amplitudes for
the desired answer reinforcing.

|A quantum computer that can evaluate 1 position in one
|millisecond (the equivalent of a $30 handheld toy that
|evaluates a thousand positions per second) can:
|
|Evaluate 1 position in 1 millisecond
[...]
|Evaluate (10^93) positions in 500 milliseconds
|
|Even if you start with quantum computer that can
|only evaluate 1 position per second, it can still
|evaluate the entire tree in less than a day.
|
|Searching 2^N chess positions in N time: It's an
|idea who's time has come!

This all appears to be based on a misconception of
the way in which quantum computers can (in theory)
do more.

Keith Ramsay

Relevant Pages