December 27, 1999
Special Report - David Fogel of Natural
Selection, Inc.Ò and Kumar
Chellapilla of U.C. San Diego Featured in the Journal Nature: Research on
Evolutionary Game-Playing Computer Programs Makes "News and Views"
La Jolla, CA – The current issue of the prestigious
journal Nature (Dec. 23, 1999) features an article on the
collaborative efforts of Dr. David B. Fogel, Executive Vice President
and Chief Scientist of Natural Selection, Inc., and Kumar Chellapilla, a
Ph.D. student in the Department of Electrical and Computer Engineering
at the University of California at San Diego, to design an evolutionary
computer program that taught itself to play checkers without relying on
human expertise. In September and November of this year, Fogel and
Chellapilla published their key results in two flagship publications1,2
from the IEEE, the world’s largest organization of engineers. They
showed that a computer can learn to play checkers at a level that is
competitive with human experts, even when starting with little more
information than the positions of the pieces on the board and the rules
of the game.
The essential means for achieving this machine
intelligence was a computer simulation of evolution. An evolutionary
program allowed the computer to play games of checkers against itself.
Over many generations of random variation and selection to the
strategies in its competing population, the program evolved an expert
strategy. Fogel and Chellapilla took the best-evolved strategy and
played it against people on the Internet at www.zone.com
without telling their opponents that they were using a computer program.
The evolved program rose to the top 1% of all registered players at the
Internet site.
"This research has been a great deal of
fun," remarked Dr. Fogel, "and more than a little
humbling." Fogel and Chellapilla’s evolutionary program was able
to defeat its creators by only its tenth generation. "Of course,
neither Kumar or I are very good at checkers. The game is actually quite
difficult to really master and the computer easily surpassed our own
abilities. But we never thought that we’d evolve a strategy that could
compete with human experts without preprogramming in the features that
humans use."
In fact, such an achievement was thought to be
impossible in the early days of artificial intelligence research.
National Medal of Science winner Professor Alan Newell was quoted in
1961 as saying that it would simply be hopeless to get machines to learn
how to play games like checkers or chess simply from the information
contained in the final outcome: win, lose, or draw. But much like the
computer in the classic movie War Games, Fogel and
Chellapilla’s computer has indeed taught itself to be a very tough
opponent. "Whatever the program knows, I can assure you that it
didn’t learn it from us!" remarked Dr. Fogel. The same technology that can be used to learn about tactics in a game like checkers can be applied in other domains, such as military combat. Natural Selection, Inc. is under contract to the United States Army on a Phase II STTR effort, in collaboration with U.C. San Diego and Professor Kenneth Kreutz-Delgado, to explore and develop evolutionary algorithms to assist tank commanders in training exercises on the computer. Other applications include developing strategies in business and financial markets. For a soft copy (pdf file) of the article please e-mail Dr. David B. Fogel at dfogel [at] natural-selection.com.
Natural Selection, Inc. was founded in 1993 to
address complex problems in industry, medicine, and defense. The company
possesses unique expertise in computational intelligence techniques,
including evolutionary computation, neural networks, and fuzzy logic.
The corporation's current research efforts support the discovery of new
pharmaceuticals, optimizing the routing and scheduling of national
transportation services, and a variety of military projects.
For more information, please contact:
Dr. David B. Fogel,
Executive Vice President & Chief Scientist,
Natural Selection, Inc.,
3333 N. Torrey Pines Ct.,
Suite 200,
La Jolla, CA, 92037
tel: (858) 455-6449
fax: (858) 455-1560
dfogel [at] natural-selection.com
References
- Kumar Chellapilla and David B. Fogel, Proceedings of the IEEE,
Vol. 87, Sept., 1999, pp. 1471-1496.
- Kumar Chellapilla and David B. Fogel, IEEE Transactions on
Neural Networks, Vol. 10, Nov. 1999, pp. 1382-1391.
Please visit our web site at www.natural-selection.com.