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

From: Keith Ramsay (kramsay_at_aol.com)
Date: 09/10/04 

Date: 9 Sep 2004 17:43:27 -0700

In article <10k076lqki79i2f@news.supernews.com>, Guy Macon
<http://www.guymacon.com> writes:
|>I'm curious to know how long it might take today's computers (or a
|>team of computers) to reach this goal of completely mapping out all
|>the possible branches of the game of chess.
|>
|>200 years? 2,000 years? 2 million years?
|
|A few minutes, assuming a superfast computer of the future.
|Go to http://www.qubit.org/ and click on the "Tutorials"
|link at the left to see what a superfast computer of the
|future will be able to do.

I think you may have an exaggerated view of the advantages of
quantum computers over "classical" ones. For certain problems
such as factoring integers into primes, there are known "quantum
algorithms" that solve them relatively fast, even though the
known ordinary algorithms are not so fast.

This is possible only because of the special nature of the problem,
however. The kind of tree search you need to do to determine the
winner
in a game of perfect information is generally a very hard type of
problem, and there is not a lot of reason to think that merely having
a quantum computer will turn it into an easy one. It's not as though
the quantum computer with N additional bits can act just like 2^N
copies of the classical computer running in parallel. The quantum
computation has to succeed by means of phase interference between the
various components of its state.

At one point in the 1990s, I read that all the problems that existed
to date that could in theory be solved faster on a quantum computer
than by any known algorithm on a classical computer, were ones where
an important part of the problem was to determine the period of a
periodic function with a long period. For instance with factoring, it
makes it much easier to factor a large number N if you can determine
the periodicity of the function a^k mod N for some value of a. If a is
relatively prime to N, then a^phi(N)=1 mod N, where phi is the number
of integers in 1,...,N that are relatively prime to N. So a^k mod N
is periodic with a period dividing phi(N). If N is a product of two
primes, N=pq, and we can determine phi(N)=(p-1)(q-1), then factoring
N becomes easy.

There is a class of types of problem known as PSPACE, consisting of
the types of problem for which there's an algorithm to solve it using
storage space bounded by a polynomial in the size of the description
of the problem. Some of the types are known as PSPACE-complete
problems
because each other type of problem in PSPACE can be reduced to it.
Certain game-related problems have been shown to be PSPACE-complete.
I believe a certain generalization of chess was shown to be PSPACE-
complete, for example.

Simulating a quantum algorithm running in time bounded by a polynomial
in the length of the input can be done in PSPACE. Such space bounds
are generous enough to permit a computer to evaluate the amplitudes
of all the paths the quantum computer takes and add them up. So PSPACE
is at least as strong as quantum polynomial time.

It's very hard to prove that efficient algorithms for problems *can't*
be found. It's still not known that there isn't an efficient classical
algorithm for each problem in PSPACE, although it's considered
unlikely. It's similarly unlikely that quantum computing can solve all
such problems. So the kind of tree searching you have to do appears
not to have any special features that would enable us to solve it
quickly on a quantum computer.

It's conceivable that an ideal algorithm for chess is still possible.
For one thing, asymptotics don't tell you how hard the problem is on
a fixed 8x8-sized board. You also start chess ordinarily in close to
an even position. Perhaps there is some clever way to demonstrate
that neither side has to allow the position to become very unbalanced
in the other side's favor, without too exhaustive a search.

Moore's law will surely break down before we get to the point where
it would say we could search all the possibilities in a few minutes.
One can fantasize about developing quantum computers where the number
of qubits is on the order of the number of atoms, but somewhat hard
to believe that we'll be going way beyond that point during this
century.

Keith Ramsay

Relevant Pages

  • Re: Symmetric Encryption attacked by quantum computers?
    ... > I have read that if you are using a symmetric cipher with a 256 bit ... it would take a quantum computer about 2^128 steps to break. ... Grover's algorithm: ... doesn't automatically get fast computation from superposition -- one needs ...
    (sci.crypt)
  • Serially Factoring large prime numbers --- Shors algorithm modification
    ... I believe Shor's algorithm uses a quantum computer to factor large prime numbers product. ... When the X qubits settle down, you have obtained the first X bits of the solution. ... Feed the problem into the "X" qubit quantum computer along with the first X bits of the solution. ...
    (sci.math)
  • Re: Quantum Computing and protein folding
    ... >> Would a quantum computer be able to efficiently, and accurately, solve ... a protein polypeptide itself is a quantum mechanical system that seems ... > problem any fatser using brute force as an algorithm. ... Maybe someone will someday figure out how to make such an algorithm ...
    (comp.theory)
  • Re: Quantum Computers breaking ciphers
    ... >> quantum computer and used itbto run Shor's Algorithm works and to ... >one qubit that can be chained with other qubits to do a computation. ... but not a quantum computer. ... >investigation of the spin states of some particular molecule. ...
    (sci.crypt)
  • Re: JSH: Easy math, easy solution
    ... > That depends on the speed of your quantum computer. ... > speed, and for some values to be factored, a Pollard-style algorithm ... A quantum computer can implement a polynomial-time algorithm ... the requirement of a classical computer in the algorithm is much ...
    (sci.math)