From: sloan@cis.uab.edu (Kenneth Sloan)
Subject: Re: When Deep Thought Beats Kasparov...
Organization: CIS, University of Alabama at Birmingham
Date: Thu, 8 Oct 1992 21:16:47 GMT

In article <1992Oct8.170109.16988@bnr.ca> Peter Marko <pmarko@bnr.ca> writes:

[a very cogent presentation of the trends in computer chess strength -
with which I entirely agree]

Except:

The plot of data points giving rating vs. time has data points separated
by an average of 6 years apart.  If development can be characterized by
"punctuated equilibrium", it is dangerous to then produce a set of
predictions at 1-year intervals.  I would be more comfortable with
extrapolations separated at least 12 years apart.

And...can everyone say "sigmoid"?  If there is a maximum rating, how
does the computer-strength curve approach that maximum?  At a sharp
angle?  Asymptotically?  Where is the knee, if any, in the curve?  We
can't begin to know that until the observations enter that region.

Extrapolation (while attractive, and often correct) is a tricky
business.  For example, what strength does the linear fit predict for
the year 1960 (answer: approx. 1100) How about 1954 (answer: 700).  How
about 1948 (answer: 400).  OK - now go and find the 400-strength computer
chess program extant in 1948.  

Hmmm - actually, that works out fairly well.

Now, let's try extrapolating ply-searched against strength...

At 200 points (or is it 199) per ply, we find that DeepThought can play 

          2600 10
          2400  9
          2200  8
          2000  7
          1800  6
          1600  5
          1400  4
          1200  3
          1000  2
           800  1

Actually - this correlates well with the claim that "just knowing the
rules" corresponds to a rating of about 900.

but then..

           600  0
           400 -1

So, Deep Thought can play 400-level chess without knowing what the
opponent has done, and simply randomly choosing moves (not even
restricted to legal moves!)  Again - this is actually surprisingly
accurate, based on my recent observations of 400-strength chess.
But, it's hard to figure out what is left of "Deep Thought" given these
restrictions. 

>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? 

Yes (theoretically) - as long as you can construct a series of players
(machine or otherwise) such that player A plays at, say, the 3000 level
but always loses to player B, who always loses to player C, who...

As long as winning a game guarantees that you gain rating points - a
player who wins all games will (eventually...) achieve any finite rating
- which is as good an operational definition of "infinity" as we need
here.

One might as well ask: how long is the tail of the Normal (pick your
favorite alternative here) distribution?

One flaw in your estimate is the assumption that the average game lasts
about 40 moves.  These are games played by 2600 class players.  3000
class players may well play much longer (or much shorter - the question
is open) games.  Perhaps the middle-game (the part between the opening
book and the endgame database) will stay constant, or become larger.
Or, perhaps it will shrink until they meet in the middle.

The question really is: how close is a 3000 player to perfection? 
On the one hand, a 3000 player may have solved the game, but
nevertheless draws occasionally with 2800 players.  This would connect
"perfection" to the current rating scale, and prevent the construction
of my infinite series of players.

If, on the other hand, it turns out that the value of chess is 1/2 - but
no 2800 player could ever draw against perfect play - then we have the
possibility of an infinite top rating.

I've kept this discussion tied to human performance because I think
there are too many loopholes and artificial situations which can arise
from a large pool of computer players.  I think that my arguments above
can be made to fit in this world - but they become unnecessarily
complicated.  There is, however, the danger that Elo ratings simply do
not apply in such an artificially constructed rating pool.




-- 
Kenneth Sloan                   Computer and Information Sciences
sloan@cis.uab.edu               University of Alabama at Birmingham
(205) 934-2213                  115A Campbell Hall, UAB Station 
(205) 934-5473 FAX              Birmingham, AL 35294-1170
Newsgroups: rec.games.chess