From: pmarko@bnr.ca (Peter Marko)
Newsgroups: rec.games.chess
Subject: When Deep Thought Beats Kasparov...
Date: 8 Oct 92 17:01:09 GMT
Organization: Northern Telecom Canada Ltd.
X-Useragent: Nuntius v1.1

I've just read the much-cited Scientific American article about chess
computers ("A Grandmaster Chess Machine", by Feng-hsiung Hsu, Thomas
Anantharaman, Murray Campbell and Andreas Nowatzyk, published in the
October 1990 issue).  A very interesting reading.

There are two things in the article that I wanted to reflect on. 
Firstly, regarding the timeframe when chess computers will outperform all
humans, and secondly, regarding the prediction of the strength of the
next-generation Deep Thought.

To answer the first question, please consider the following data
regarding the development of chess computers (derived from the article):

                       Rating
  Year   Computer      (USCF)

  1966   MacHack-6      1500
  1979   Chess 4        2000
  1983   Belle          2200
  1986   Hitech         2400
  1989   Deep Thought   2600

The above data is limited (only five samples); nevertheless, it does
demonstrate the development of chess computers over time.

If we apply straight-line approximation (linear regression) to the above,
the following results (the fact that these ratings were achieved by
different programs running on different platforms can be ignored as they
all represented the strongest machine available at the time, hence were
riding the general technology trend, which also follows a logarithmic
curve - the rating scale is logarithmic as well):

         Rating
  Year   (USCF)

  1992    2672
  1993    2718
  1994    2765
  1995    2812
  1996    2858
  1997    2905   
  1998    2951
  1999    2998
  2000    3045

The correlation (coefficient of determination) is 0.981, so straight line
is a good fit.

This would seem to point to the year 1997, when the best machines will
surpass all humans (assuming that the difference between USCF and FIDE
ratings is 100 points, and that the playing strength of the top people
will remain essentially the same - about 2800 FIDE points).  The authors
of the article believed then that this time may even come by 1992, which
I strongly doubt.

Now, to answer the second question, let me quote more numbers from the
article.  The authors, correlating search depth with playing strength,
say that each extra ply (half-move) in general search depth is equivalent
to a gain of about 200 points in playing strength.  This is based on the
following:

                Depth    Rating
  Computer     (Plies)   (USCF)

  Belle           5       1560
  Belle           6       1860
  Belle           7       2090
  Belle           8       2200
  Hitech          9       2400
  Deep Thought   10       2600

They further argue that, since the next-generation Deep Thought will do
general searches to 14-15 plies, its rating will be about 3400.  Doing
straight-line fit again on the above, we get:

   Depth    Rating
  (Plies)   (USCF)

    14       3405

Correlation is 0.984, also very good.  The slope of the line is 198
points per 1 ply.  So, it turns out that the authors were pretty close on
this.  Again, the same general statements would apply to this set of data
as to the previous one.  More specifically, going one ply further does
not just mean searching deeper; it also implies that more sophisticated
algorithms and more efficient hardware have been developed at the same
time which enhance the machine's strength.

Finally (sorry that this turned out to be such a long article), another
interesting question is whether there is an absolute maximum theoretical
playing strength, and if so, what it is.  A quick estimate may be made as
follows (I am not advocating this, just giving an example for discussion
purposes):

The average game lasts about 40 moves.  Out of this, opening book is
about 10 moves.  This leaves us with 30 moves (60 plies) to calculate (on
the average) before we can declare a position won or drawn.  Given the
above linear approximation, we get:

   Depth    Rating
  (Plies)   (USCF)

    60       12513

Would the absolute maximum be about 12500?  Is it significantly lower,
higher?  Why?  Is it infinite?  I would be interested to see some serious
estimates.  Feng-hsiung, Thomas, Murray, Andreas: are you reading this?

   ...Peter

---------------------------------------------------------------
Peter Marko    .....    (613)763-5344    .....    pmarko@bnr.ca
Northern Telecom Canada Ltd.   .....    Ottawa, Ontario, Canada