ICCA Journal, Volume 20:  Number 4  (December 1997)




TABLE OF CONTENTS
Editorial:                                                                                          
    Two Decades (H.J. van den Herik) ........................................................... 213
Contributions:                                                                                      
    Can Machines Think? Deep Blue and Beyond (D.C. Dennett) .................................... 215
    Evaluation Tuning for Computer Chess: Linear Discriminant Methods (T.S. Anantharaman) ...... 224
Notes:                                                                                              
    Does Deep Blue use Artificial Intelligence? (R.E. Korf) .................................... 243
    Secrets of Chess Endings (R. Cifuentes, M. de Zeeuw, and J. van Reek) ...................... 246
Review:                                                                                             
    Proceedings of Game Programming Workshop in Japan '97 (A. Yoshikawa and H. Iida) ........... 249
Reports:                                                                                            
    The 15th World Microcomputer-Chess Championship ............................................ 253
        Report on the 15th World Microcomputer-Chess Championship (J. Hamlen and M. Feist) ..... 254
        Results and Selected Games (M. Feist and F. Friedel) ................................... 256
        The Best Game in Paris (J. Speelman) ................................................... 267
    Report on the 17th Open Dutch Computer-Chess Championship (Th. van der Storm) .............. 271
    Report on the 5th French Computer-Chess Championship (M.-F. Baudot) ........................ 273
    Using Games as an Experimental Testbed for AI Research (J. Wiles) .......................... 274
    The Third Fost-Cup World-Open Computer-Go Championship (D. Fotland and A. Yoshikawa) ....... 276
    Times Past: Some Remembrances and Reflections (B. Mittman) ................................. 279
    The 1997 ICCA Journal Award (The Board of ICCA) ............................................ 281
    ICCA Journal Referees in 1997 (The Editorial Board) ........................................ 282
    AEGON Stops (C. de Gorter) ................................................................. 282
    Calendar of Computer-Games Events 1997/1998 ................................................ 282
    The Swedish Rating List (T. Karlsson and G. Grottling) ..................................... 283




ABSTRACTS OF SCIENTIFIC ARTICLES


Can Machines Think? Deep Blue and Beyond
Daniel C. Dennett

[20(4):215-223]   The question ``Can Machines Think?'' has always intrigued researchers and philosophers. Last year the question revived when DEEP BLUE played Kasparov, but Kasparov then held his ground. However, recently DEEP BLUE defeated the World Champion, and so the question became really acute.

This article attempts to define a suitable sword-in-the-stone test, equally valid for computers and humanity. The following tests are successively discussed: the Chess Test, the Turing Test, and the Gödel Test. The Chess Test is considered to be obsolete after Kasparov's defeat. The Turing Test is illustrated by providing background on the Loebner Prize Competitions. Its restricted version is a problematic sword-in-the-stone test; its unrestricted version is certainly not a test that any machine is going to pass any time in the foreseeable future. Finally, the Gödel Test is discussed.


Evaluation Tuning for Computer Chess: Linear Discriminant Methods
Thomas S. Anantharaman

[20(4):224-242]   The evaluation function of a software version of the DEEP THOUGHT chess program is tuned against a database of master-level games. The agreement between the move chosen by the program and by a human master is maximized. A set of algorithms solving the maximization problem is presented. The trade-off between computational speed and the chance of getting stuck in a local maximum is extensively investigated.

The performance of the chess program with the tuned evaluation function is experimentally measured. The program has played several matches of 500 games each with different settings against a fixed program. The results show that 98% of the performance of the evaluation function can be achieved in about a week by tuning the evaluation function from scratch against the database. If the evaluation tuning is started from the best evaluation used so far, the new evaluation function improves the playing strength by 34 rating points.


Does Deep Blue use Artificial Intelligence?
Richard E. Korf

[20(4):243-245]   When DEEP BLUE played Garry Kasparov in February 1996 and May 1997, the extensive IBM Web pages devoted to the site claimed that DEEP BLUE did not use artificial intelligence (AI). I argue that this claim is (1) inaccurate, (2) representative of a wide-spread phenomenon in the field, and (3) ultimately harmful to AI.




EDITORIAL


Two Decades
H. Jaap van den Herik

[20(4):213-214]   It is some two decades ago that we saw the first commercially available chess program. The files were numbered and the ranks were lettered. So the normal opening move e2-e4 had to be input as b5-d5. It was a first sign that talented chess programmers do not have to be strong chess-players; the world of computer chess was far from the world of chess. The chess-players were laughing, the computer play was horrible. Nevertheless, the 1977 chess computers were much stronger than their predecessor of two decades earlier (i.e., Bernstein's program), and even of one decade before (e.g., MAC HACK VI).

Let us take the commercial program as a starting point for our review of the increase in playing strength. This starting point coincides with the birth of the ICCA Newsletter. Owing to this medium and its successor, the ICCA Journal, we now have ample publications to see how stormy this development has been. Starting from a novice level, computer-chess programs have achieved Grandmaster level, and one of them, DEEP BLUE, even succeeded in defeating the World Champion in a six-game match. Many a human would be proud of such an improvement in performance over 20 years.

Having looked back over a period of two decades (and also of twice two decades), we might now wonder what will happen if we look forward the same amounts of time. To the layperson there is only one step: from being better than the World Champion to being perfect, i.e., solving the game. After the successes achieved in Qubic, Connect Four, Go Moku, Nine Men's Morris, and (recently) in 8x8 Domineering, people are waiting for the final verdict in games such as Awari, Checkers, and Chess.

However, the royal game of Chess seems to be pretty secure, and not only for the next four decades. In order to abandon the perenially-returning question about whether the game of chess can be solved, we offer a thumbnail calculation. Assume the number of reachable positions to be 1046, the outcome of Chinchalkar's calculation in the ICCA Journal (Vol. 19, No. 3). The alpha-beta algorithm with its enhancements reduces the number of positions in the tree to its square root, leaving 1023 positions. Moreover, assume that we have 1000 processors working in parallel, each searching 109 positions per second (instead of the current 106). This means that we assume that future processors will be one thousand times faster than the current ones. These assumptions result in a solution time of 1011 seconds. Let us further assume that a century contains 100x365x24x60x60 ~= 109 seconds. Then the time to solve the game of chess is in the order of 100 centuries, give or take a week.

So, the challenging question is: where do we go from here with computer-chess research? New goals should be formulated. According to David Levy (see also Daniel Dennett in this issue) the first such a goal is to produce $50 chess computers which are stronger than the World Champion. They could be used, when watching a human World Title match, for easy comment: "Hi, see the World Champion overlooked the move 42. Bb7." Will that be within a single decade? And what then will be the goal of the second decade? Maybe, the production of 7-piece endgame databases? And thereafter? Maybe, explaining the computer strategies in human-understandable concepts?

Having seen the big difference between good (very good) and perfect, we may ask ourselves whether we can measure the error rate of the human World Champion. Is one out of ten decisions a mistake in a game-theoretical sense? Is it more, or is it less?

Next to these rough estimations and calculations we still have to face the question about artificial-intelligence techniques used in strong computer-chess programs. In this issue Richard Korf provides a clear answer: Yes, DEEP BLUE used AI techniques. Some of Korf's opponents may argue that all the AI techniques used are so-called weak techniques, since they only deal with a few knowledge issues and learning is not used at all. This might be true, but it does not do away with Korf's arguments. Incorporation of machine-learning techniques in competitive chess programs must be considered as the next major challenge for computer-chess research.

Finally, this is the place to thank Professor Ben Mittman who, two decades ago, took up the challenge of starting a Newsletter for his beloved group of ICCA enthusiasts. He did a very good job and I am proud to have been given the opportunity to succeed him.

Two decades ago, one needed courage to start a serious Newsletter on computer-chess programs that produced laughable results. This is even more clear when we consider the number of soccer fans and the researchers' attempts to mimic the players' performances in the RoboCup. Despite the huge number of fans there is no Computer-Football Newsletter. Furthermore, an intriguing question is: will there be a Roboteam playing Real Madrid within two decades from now? If not, the reason might be that they failed to develop a Computer-Football Journal.



Created by Ernst A. Heinz and Heiner Marxen, Tue Aug 8 18:33:33 EDT 2000