Author: Walter Faxon
Date: 17:07:18 04/13/05
A brief article in "New Scientist" about 5 years ago suggested that future
quantum computers will be able to attack chess by doing the quantum equivalent
of a full-width search 300 ply or more deep. I googled today to find the
following material:
----------
Quantum Games: Taking advantage of quantum effects to attain a winning edge, by
Ivars Peterson
From Science News, Vol. 156, No. 21, November 20, 1999, p. 334. Copyright 1999,
Science Service.
Article: http://www.sciencenews.org/pages/sn_arc99/11_20_99/bob2.htm
References: http://www.sciencenews.org/pages/sn_arc99/11_20_99/bob2ref.htm
((snip))
Until recently, however, the realm of games appeared far removed from the domain
of physics and quantum mechanics, which governs the interactions of atoms and
electrons. Now, theorists are poised to exploit peculiarities of quantum
behavior to work out novel strategies for winning games.
It's like having a quantum penny, says mathematician David A. Meyer of the
University of California, San Diego. An ordinary penny comes up either heads or
tails. A quantum penny has the additional property that it can be put into a
state that mixes both heads and tails.
The extra possibility of a mixed state permits quantum-game strategies that can
theoretically be more successful than conventional ones in various games, Meyer
contends.
In the light of quantum theory, coin tossing, chess, and perhaps even
international negotiations take on a startling, new dimension. In some cases,
using a hypothetical quantum computer in place of a conventional one should
speed up searches to identify a winning strategy. In other instances, quantum
logic changes the game itself.
Computers play a mean, brute-force style of chess. When chess computer Deep Blue
triumphed over world champion Garry Kasparov in 1997, it relied heavily on
extensive searches (SN: 5/17/97, p. 300). For a given arrangement of chess
pieces, the computer simply looked ahead a fixed number of moves, evaluated the
strength of each move, and selected the best one.
In principle, a chess computer can foresee a game's end by checking each
possible path to its outcome. It can then choose an appropriate sequence of
moves to ensure a win, maintain a draw, or delay a loss. In a game of 40 moves,
however, the number of different board positions that can develop exceeds
10^120. There's no way even the fastest conventional computer can check every
possibility to play a perfect game.
That's where quantum computers would help.
Ordinary computers rely on vast arrays of tiny transistors, arranged in logic
units called gates, to perform their calculations. They typically use the
presence or absence of certain amounts of electric charge to represent the 0s
and 1s of a computer's binary code.
The hypothetical quantum computer replaces the 0s and 1s with entities called
quantum bits, or qubits. Each qubit is encoded as a quantum state a particular
energy level of an atom, for instance. One energy level would correspond to the
0 state and another, to the 1 state. Unlike an ordinary bit, however, a qubit
can also exist as a combination, or superposition, of those two states.
Computer scientists can, in principle, take advantage of superposition and the
wavelike nature of quantum particles. They would set up calculations so that
computational paths yielding undesirable results cancel each other out, while
computational paths leading to the answer reinforce each other (SN: 1/14/95, p.
30). In effect, quantum interference allows them to zero in quickly on the
relevant result.
In 1996, Lov K. Grover of Lucent Technologies' Bell Labs in Murray Hill, N.J.,
invented a quantum-based procedure that would significantly speed up searches of
an unsorted list to find a desired item (SN: 8/31/96, p. 143).
Grover's search algorithm can itself be thought of as a kind of game, Meyer
remarks. As in the game of 20 questions, which calls for "yes" or "no" answers
to specific requests for information, Grover's procedure queries a database to
learn whether one is on the right track to the answer.
David Deutsch and Artur Ekert of the University of Oxford in England have
considered how a chess-playing quantum computer would use Grover's procedure. It
could investigate a trillion possible continuations from a given position in the
same number of steps as a conventional computer would need to check out a
million. Quantum superposition allows the computer to cancel out a lot of
unpromising possibilities that a conventional computer must look into one by
one.
((WF: This square-root figure suggests that for a given computational effort we
might be able to search a min-max tree twice as deeply, the same speedup as
given today by vanilla alpha-beta. If we could combine the two methods we could
search four times as deeply. In neither case to 300 ply. Still, there might be
less "effort" involved in a quantum computation.))
Several researchers, including Grover and Scott Aaronson of Cornell University,
have investigated such potential improvements in performance. They discovered
that the search speed-up in a game in which two players take turns looks
especially promising if there is, at most, just one winning choice per move.
Since then, Grover has generalized his quantum-search method to cover situations
where there may be multiple solutions.
So, if Deep Blue comes out of retirement someday, it might face a newfangled
quantum computer and quite possibly a crushing defeat.
((snip))
Theorists studying quantum computation offer new perspectives on coin tossing,
chess, and game theory:
Eisert, J., M. Wilkens, and M. Lewenstein. 1999. Quantum games and quantum
strategies. Physical Review Letters 83(Oct. 11):3077.
Meyer, D.A. 1999. Quantum strategies. Physical Review Letters 82(Feb. 1):1052.
((WF: See online links to pdf versions of these papers below.))
----------
Missing Correlations in Strategic Economics, Artificial Intelligence, and
Multi-Agent Optimization Theory, by Michael J. Gagen and Kae Nemoto (July 8,
2004 -- still in preparation)
http://research.imb.uq.edu.au/~m.gagen/research/econ/missing_correlations.pdf
Abstract: Many existing approaches to strategic economics, to artificial
intelligence, and to general multi-agent optimization theory are presently
missing correlations. Including these correlations promises to radically alter
these fields. The document, still in preparation, canvasses some of these
changes. This presentation is primarily designed as a discursive and
educational web page. See home pages at http://research.imb.uq.edu.au/m.gagen/
and http://research.nii.ac.jp/nemoto/.
((snip))
((WF: Following is an amazing quote:))
We argue that human players (and human cognition in general) is partially
accessing the full infinite space of all possible correlated probability
distributions to analyze a strategic situation such as chess. The ability to
impose correlations on a game tree can radically reduce the size and complexity
of that game tree to manageable proportions. If a player adopts a small range
of general strategies, such as "Attack on the left", "Hold the Cente", or
"Defend on the right", then the adoption of such a strategy imposes significant
correlations on all the pieces of that player. The need to "Attack on the left"
means that all the pieces work together as a single correlated unit, a "chunk".
In this viewpoint, a strategy is not a move of a single piece, but rather the
choice of which set of correlations to impose on all the pieces. It is likely
that players have only a repertoire of a small set of strategies, and will
search the strategy space for an optimal way to play the game taking into
account their opponent's strategies.
((snip some math))
Evaluating these expected payoff functions using game trees requires the drawing
of an infinite number of trees, and, to the extent possible, the searching of
this infinite space for the optimal play strategy. It is absolutely impossible
to properly account for correlation strategies using independent game trees. We
expect that incorporating the infinite search spaces available to human
cognitive processes will substantially close the gap between human cognition and
artificial intelligence algorithms.
((snip))
Ref. [8] demonstrated that quantum games are more efficient than classical
games, but did this by assuming that classical expected payoff functions are
multi-linear in probability numbers defined over compact and convex spaces
indicates that the full correlation space has not been taken into account.
Hence, whether quantum games are always more efficient than classical games is
an open question.
((snip))
[8] C. F. Lee and N. F. Johnson. Quantum game theory. Eprint
Archive:quant-phys/0207012 (See http://arxiv.org/abs/quant-ph/0207012), 2002.
----------
Quantum Computers and Quantum Coherence, by David P. DiVincenzo and Daniel Loss
(July 10, 2004)
http://arxiv.org/pdf/cond-mat/9901137
((snip))
10. Games: This is a rather ill-defined area at the moment, but one with
apparent promise. Meyer and Eisert et al. [27] have shown that if the players
in a game can perform quantum mechanical manipulations in the game (e.g., moving
a chess piece into a superposition of positions by a unitary operation), they
can gain some advantages. It seems that some changes will have to take place in
our society before some of these game results become applicable -- can we have a
quantum stock market? A quantum economy?
((snip))
[27] D. A. Meyer, "Quantum strategies," http://arxiv.org/pdf/quant-ph/9804010;
J. Eisert, M. Wilkens, and M. Lewenstein, "Quantum games and quantum
strategies", http://arxiv.org/pdf/quant-ph/9806088;
L. Goldenberg, L. Vaidman, and S. Wiesner, "Quantum gambling,"
http://arxiv.org/pdf/quant-ph/9808001.
((WF: The first two of the [27] references are what we want to look at, but
I've run out of time!
Abstracts with links for these two papers:
http://arxiv.org/abs/quant-ph/9804010 mirrored at
http://xxx.lanl.gov/abs/quant-ph/9804010
http://arxiv.org/abs/quant-ph/9806088 mirrored at
http://xxx.lanl.gov/abs/quant-ph/9806088
The abstracts confuse me: How can any alternative strategy, quantum or
whatever, beat an optimal classical strategy if the actual moves can only be
classical? I guess I'll have to read the papers!))
----------
If you are googling our subject, beware of:
Quantum Noise and Information, by H. J. Bremermann (University of California,
Berkeley)
http://www.aeiveos.com/~bradbury/Authors/Computing/Bremermann-HJ/QNaI.html
"It is the contention of this paper that speed, memory, and processing capacity
of any possible future computer equipment are limited by certain physical
barriers: the light barrier, the quantum barrier, and the thermodynamical
barrier. These limitations imply, for example, that no computer, however
constructed, will ever be able to examine the entire tree of possible move
sequences of the game of chess."
This very old (pre-1970?) paper is not about quantum computing, rather it is
about the quantum limits on classical computing.
----------
If you are interested in the subject of quantum computation in general, you
might start with an article in the wikipedia:
http://en.wikipedia.org/wiki/Quantum_computation
Then maybe try the Centre for Quantum Computation: http://www.qubit.org/
-- Walter
P.S. Due to copyrighted material, please limit quoting in follow-up posts.
Thanks.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.