Feng's (Deep Thought) article in Scientific American (long)
Jean Marc Alliot
In last issue of French magazine Pour la science (which is, mainly, a
translation of the American magazine Scientific American and is the
most important scientific magazine in France), the Deep
Thought team (Feng-Hsiung Hsu, T. Anantharam, M. Campbell, A.
Nowatzyk) makes a few statements about computer chess future, and
about Deep Thought.
In the first part of this submission, I will sumarize quickly this
article (if you want full information, buy the magazine), then I will
give a translation of commentaries made by a French computer chess
expert about it (well I don't think he is a expert, but french
magazines seem to think he is). In the last part, I'll give my own
comments and raise some questions I would like the net (or Feng
himself if he has time) to comment.
Part I : Quick Summary
In 1988, G. Kasparov thought that no computer could beat a GMI before
2000. Ten months later, Deep Thought defeated GMI Bent Larsen to tie
for first place in Long Beach chess tournament. In the 1990 summer,
Deep Thought won 5 of 10 games against GMI and 12 of 14 games against
MI. Deep Thought is now 2552 ELO. Deep Thought analyzes currently
750000 moves/sec. In 1992, next version will be 1000 times faster and
will analyze one billion positions / sec. Could it be enough to beat
the chess World Champion?
Computer chess has now quite a long history behind him, but real
improvements were mainly due to Claude Shannon who used classical
games theory and minimax algorithm. The computer generated all moves
possible from the root of the search tree, then gave a value to each
leaf of the tree and tried to reach the best leaf possible. Of course,
in chess, exhaustive search (from the beginning of the game to a
checkmate position) is impossible: the branching factor is
around 30 and even with a good alpha beta algorithm you can't get much
better than 7 or 10: doing a ten plies exhaustive search requires to
generate and evaluate 10^10 positions.
There were two possibilities:
On one hand some people thought that brute force must only be used
(tactical approach); ont the other hand others experts
thought that a computer should be
program to play like a human being (strategic approach). In the 1970,
it was discovered that strength of program was proportionnal to the
depth of analysis: one half move more in the search tree = +200 ELO.
But people realized also the necessity to use other technics
(only evaluating in quiescent positions for example) to
minimize some drawbacks of brute force approach.
Deep Thought story started with ChipTest. In June 1985, Feng Hsu
discovered that some VLSI chips could be used to develop fast moves
generator for chess. With three others students they developped a
Computer machine, ChipTest. Their first results were not excellent,
but, according to the time they had to develop the system, very
promising. Participations in tournaments were also really instructive
and Feng Hsu realized the necessity to use specific algorithm like
secondary search to check out unclear positions. In 1987, ChipTest won
the 1987 championship defeating World computer chess champion, Hitech.
ChipTest performance were greatly improved by an intelligent
programmation and better search. The project was called Deep Thought.
One interesting feature of Deep Thought is its evaluation function. It
has 120 parameters, and the computer auto-programs itself: it uses 900
MI games and tries to make an autocorreleation in each position of
theses games. It compares the moves he would choose according to its
current evaluation function and the move that the Masters playing the
game choosed. It then slightly increases (or decreases) one parameter
of its evaluation function and
compares again: if the correlation is better, then the modification
was a good one and this parameter is increased (or decreased again)
until stabilization. This mecanism is slow and only used in difficult
positions. An other mecanism was developped by A. Nowatzyk: it uses
the evaluation function itself (by doing deeper search) to improve
parameters.
Deep Thought evaluation function is not better nor worst than Hitech
or Cray Blitz function, but is not as good as commercial programs
functions. It should be improved by a better algorithm for
auto-programming the function.
Deep Thought does not mimic human thinking. It uses other ways fitting
its capacities.
Deep Thought was clearly defeated by Gary Kasparov (October 1989),
but Anatoly Karpov had a lot of problems to defeat him in February
1990 (Note: these games were posted to the net). The computer had a
position he could easily draw and finaly screw it up by making a
mistake that could have been avoided by a faster version of the
machine.
If search depth is the main factor for strength, next Deep Thought
machine (1,000,000,000positions/sec) should be around 3400 ELO,
500 higher than Kasparov himself. Kasparov concedes that such a
machine could defeat an average GMI but not himself or Karpov.
Part II : Translation of Mr Pierre Nolot comments
(I have nothing to do with Mr Nolot and I don't share his opinions. I
just translate the commentary he wrote for Feng article in Pour la
Science (when an article in Pour la Science is a translation of an
american article, the magazine asks a french ``expert'' to give his
opinion). I try to stick as possible to the french text the ``I'' I
use in the next few lines is NOT me).
Chess players are frightened by Deep Thought development. In the 1990
issue of the New in Chess magazine (Netherlands), GMI Hans Ree
develops in three pages his fury about chess computers invading chess.
Hans Ree gives, as an exemple of incorrect and partial commentary of a
chess game, Michael Valvo's (Traductor's note: sorry Mike,
this one is for you) commentary
of the Karpov-Deep Thought match. He correctly points out that Karpov
only gets two (!) and the computer 6 (!), one (!!) and one (?). How
then did the computer manage to loose?
For myself, I will just point out two things:
The article contains a logic mistake that all readers can easily find:
according to the Deep Thought team, their machine will examine one
billion positions/sec and have a search depth or 14 or 15 half moves.
According to the formula 1 half-move = +200 pts, they state that their
machine will get in 1992 an ELO of 3400. This means that in a 25 games
match against Kasparov (2800 ELO) would be (24-0-1) or (23-2-0). Why
do they write then that ``Deep Thought will be strong enough to
threaten the World champion''. They should write that Deep Thought
will destroy him!
Chess cannot be reduced to mere tactic. If tactic is really important
for games played by low-level players, strategy is much more important
for high level players. And from a strategic point of view, Deep
Thought is a naught, and will probably be still a naught in 1992.
Kasparov should fear Ivantchouk and Guelfand much more than Deep
Thought.
Part III: My own questions and opinions
I would first like to question some technical statements made by Feng
in his article.
1) About algorithms, I don't see in Feng's article something really
new. Secondary search was developped a long time ago (I even wonder if
the allusion to the trapped bishop in Feng article is not a reference
to a classical example that appears in Hans Berliner's PhD thesis).
I don't find in the article references to classical improvements
like the ``killing move'' notion, nor some
classical notions about selectively cutting branches in an alpha-beta
search (in french we call them ``elagage de futilite'', I can't find
the English term). So, is Deep Thought using really new algorithms, is
it using all classical improvements known until now? (I don't question
at all the improvements made by the Deep Thought team in
implementation: Deep Thought is a wonderful project, and its VLSI
chips are really amazing and new things). I really missed a clear
positionning of Deep Thought algorithms in the (quite large) world of
tree search when I read the article.
2) Feng writes that with Deep Thought, the time of brute force ended.
I don't see really why. Deep Thought is a good example of weak AI
technics, not cognitive technics. There have been some programs which
tried to use different technics (ROBIN is a good example of a chess
program using planning technics), but I don't think that
Deep Thought is doing something else than deep search with algorithm
improvements.
3) The technic used to improve the evaluation function is mainly based
on Samuel's technic, with some differences. But there I have an other
question: is a good HUMAN evaluation function a good COMPUTER
evaluation function. I'm not that sure of it. Human players usually try to
avoid unextricable tactical positions. For Deep Thought, such
positions should be actively looked for: is that parameter included in
the evaluation function and if it is, how do you manage to make it
work with the ``look alike learning'' mechanism the computer uses with
MI games? There are other reasons that (I think) makes a human evaluation
function not that good for a computer using depth search algorithms.
4) An other technical point I would have loved to read about was the
implementation of parallelism. Is it a distributed alpha-beta search?
Which is the granularity? What are the drawbacks of changing
granularity? (i.e.: will increasing the number of processors improve
speed in a linear or a logarithmic way? Won't the increasing number of
messages exchanged by processors slow down the system?: these are
classical problems we have to deal with when implementing parallelism
for PROLOG-like interpreters: I would really like to know how it goes
in chess programming.)
Finally, I think that there are
two different questions for computer chess:
1) Can a computer beat a human World champion by using only tactical
means in a few years?
2) Can chess be reduced to tactic?
I think (but I can't prove) that the answer to the first question is
YES and the answer to the second is NO.
I really think that Feng is right when he says that in a few years
Deep Thought will be able to beat a World champion. To beat Deep
Thought in 2 or 3 years, human players will have to play a good
strategical game and make NO tactical mistakes: if they only make one,
the computer will find it out on the spot and crush its opponent. Now
how many games, even in a World championship are tactically perfect?
Not a lot I think, and even if we can't prove it today, I think
computer will prove it tomorrow.
On the opposite, I don't think that chess can be reduced to tactic.
The complexity of the search makes it impossible (well it is still
an open mathematical problem but we really think we can't) to write
efficient enough algorithms to suppress completely the strategic part
of the game. Even if Deep Thought succeeds in defeating a World
Champion, we will still have to try to find means to implement
strategic concepts in a computer: a computer with good strategy and
very good tactic would be stronger than a computer with weak strategy
and very good tactic.
But, then, can we be sure that it is possible to
implement, using algorithms or even rules-based systems, human mechanism
of thinking? It seems to rely mainly on connectionism and classical
computers (which are only fast Turing machines after all) are not very
good at that. Some people even state
that it's impossible (there is a good article by Herbert Dreyfus
about this problem in ``Artificial Intelligence, the case against'',
published by Rainer Born , Croom Helm editions). But this part of the
talk belongs to comp.ai.
I use this opportunity to thank all the people writing articles in
this group: Feng Hsu, Mike Valvo, Mark Kernighan, Louis Blair,
Elliot Winslow, Stuart Cracraft, Hans Berliner, Peter Jansen and all the others.
I have been reading net news for five years now, and the rec.games.chess
group really appear to be one of the less noisy and the most interesting
groups of the newsgroups distribution. I hope all this persons will keep on
writing articles here.
Sorry for my English, but, as you have probably guessed, I'm French.
Feng-Hsiung Hsu
are perhaps a result of the inadequate translation.
First, an answer to Nolot's (sp?) question. The 3400 figure is just
calculated from simple minded extrapolation, and in the English version, it
should be fairly obvious that we have our reservations about the number.
I would like to defend Valvo's annotations: Karpov making the right move
is natural, but computers making the right moves are not...
The division of the two camps was described as the Engineering and the
Emulation camps, not as the tactical and the strategical camp. It seems
the translation completely missed the flavor of the original text, as there
was no real division along the tactical and the strategical line.
The former World Computer Chess Champion defeated by ChipTest was Cray Blitz,
not Hitech; Hitech lost the bid on tiebreak to Cray Blitz. Most people,
me included, believe that Hitech was actually stronger than Cray Blitz. A
rule change ensued in the next World Computer Chess Championship partially
because of this.
ChipTest did have something similar to the secondary search used by
Greenblatt's program. But the main search extensions algorithm used, singular
extensions, is a completely different beast. The translator might have
misinterpreted the whole idea.
We did not say the era of brute force is ended, but rather the era of PURE
brute force is ended.
--Hsu
Mark Brader
> ... In the first part of this submission, I will sumarize quickly this
> article (if you want full information, buy the magazine) ...
For the benefit of English-speaking readers who don't subscribe to
Scientific American, I'll point out that the article's appearance
in English was in the October 1990 issue, so it should still be
available at some newsstands.
--
Mark Brader "Inventions reached their limit long ago,
SoftQuad Inc., Toronto and I see no hope for further development."
utzoo!sq!msb, m...@sq.com -- Julius Frontinus, 1st century A.D.
This article is in the public domain.
Louis Blair
by Seirawan and Silman, there is a picture with
the caption, "Grandmaster Tony Miles (left) plays
against the monster chess program Deep Thought.
Note the portable computer, which is connected via
modem to the supercomputers at Bell Laboratories."
This is a mistake, isn't it?