ICCA Journal, Volume 21:  Number 1  (March 1998)




TABLE OF CONTENTS
Editorial:                                                                                          
    New Challenges (H.J. van den Herik) ........................................................   1
Contributions:                                                                                      
    A Hypothesis on the Divergence of AI Research (F.-G. Winkler and J. Fuernkranz) ............   3
    Are there Practical Alternatives to Alpha-Beta? (A. Junghanns) .............................  14
Note:                                                                                               
    The Significance of Kasparov vs. Deep Blue and the Future of Computer Chess (D. DeCoste) ...  33
Literature Received:                                                                                
    A Bayesian Approach to Relevance in Game Playing (E.B. Baum and W.D. Smith) ................  43
Reports:                                                                                            
    My 1997 Experience with Deep Blue (G. Kasparov) ............................................  45
    List-3-Hirn vs. Grandmaster Yusupov (I. Althoefer) .........................................  52
    The 7th International Paderborn Computer-Chess Championship (U. Lorenz and H. Matthias) ....  60
    The 1997 ICCA Journal Award (The Board of ICCA) ............................................  64
        Mark Brockington: A Scientific Biography ...............................................  64
    Fritz 5.0 Wins the 1997 Herschberg Best-Annotation Award (Y. Bjoernsson and T. Marsland) ...  65
    Calendar of Computer-Games Events 1998 .....................................................  66
    The First International Conference on Computers and Games '98 ..............................  67
    Drifting Down Slightly - ICCA Treasurer's Report for 1997 (D.F. Beal) ......................  68
    The Swedish Rating List (T. Karlsson and G. Grottling) .....................................  70
Correspondence:                                                                                     
    Letter to the Editor (S. Cracraft) .........................................................  71
    The FIRA Newsletter (D.N.L. Levy)  .........................................................  71




ABSTRACTS OF SCIENTIFIC ARTICLES


A Hypothesis on the Divergence of AI Research
Franz-Günther Winkler and Johannes Fürnkranz

[21(1):3-13]   Artificial Intelligence has been conceived as the science of both programming computers to perform intelligent tasks and devising computational models of human reasoning. Originally, both aspects were considered to go hand in hand, but it soon became apparent that AI research was determined to split into an engineering branch and a cognitive branch corresponding to the objectives mentioned. Research in computer chess is a prominent and successful example of this development. We conjecture that the reason for the divergence is a non-linear interaction between the strict algorithmic processing requirements of computational models on the one hand and the associative human knowledge structures on the other hand.


Are there Practical Alternatives to Alpha-Beta?
Andreas Junghanns

[21(1):14-32]   The success of the alpha-beta algorithm in game playing has shown its value for problem solving in artificial intelligence, especially in the domain of two-person zero-sum games with perfect information. Still, there are different algorithms for game-tree search which challenge the value of the alpha-beta algorithm. This paper describes and assesses the alternatives proposed according to how they try to overcome the limitations of alpha-beta. We conclude that for computer chess no practical alternative exists, but many promising ideas have potential to change that in the future.


The Significance of Kasparov versus Deep Blue and the Future of Computer Chess
Dennis DeCoste

[21(1):33-42]   In this paper we argue that the Garry Kasparov versus DEEP BLUE matches of 1996 and 1997, despite some shortcomings, have had a significant positive impact on computer-chess and artificial-intelligence research. Such matches can be viewed as valuable lessons in how (and how not) to use man-machine competitions to obtain a better focus on applied research and on the development efforts. One of the most important goals is to provide benchmarks (both in terms of development effort and match performance) that more knowledge-intensive (i.e., less brute-force) approaches must surpass to justify their extra complexity.

We will briefly summarize some of the latest developments in computer-chess research and highlight how our work on a program called CHESTER tries to build on them to provide such justifications. Using our CHESTER work as an example, we propose a possible shift in emphasis for the computer-chess community: away from tournament performances (nowadays a short-term goal) and more toward treating the chess domain as a valuable testbed for research on emerging large-scale data-mining and machine-learning techniques. The successes of DEEP BLUE, despite legitimate questions of validity and scope, have in some sense freed (and perhaps even compelled) us to refocus on such longer-term goals.




EDITORIAL


New Challenges
H. Jaap van den Herik

[21(1):1-2]   ``Looking back I should have played it differently'' is the inescapable thought of anyone losing a chess game. It sounds like a chorus for players - and indeed it is when considering CHESS as a musical - but it is a nightmare for champions in the post-mortem of a lost match. For such a champion the main questions are: how could I play that? and why did not I play the alternative?

In this issue, World Champion Kasparov provides some answers to these questions. Moreover he allows us some insights into his world of thinking, he even gives us a few clues as to why he behaved as he did. It is all contained in a lecture given at the prestigious Oxford University.

Of course, one could argue with him on the relevance of his thoughts, since his conceptions on the inside computer technologies are only rough conceptions and do not always match the "real" truth. Nevertheless, his emotions and compassions are presented with vigour and with persuasion. Having read the arguments, even dedicated computer-chess fans must admit that et audite alteram partem is a wise obiter dictum.

So far this Journal would seem to have painted the picture that Kasparov's world has been changed by a mere machine, i.e., by DEEP BLUE, since he lost the six-game match by 3.5 to 2.5. However, as Kasparov states: he did not lose to DEEP BLUE, he lost to IBM. The difference seems small, but reading the relevant part of his lecture will show that the World Champion has a point. And what is more: he publicly challenges the DEEP BLUE researchers in the name of science to publish their new findings and implemented technologies in scientific journals. As our readers know we fully concur with this invitation and have previously shown our willingness to include such publications in our pages.

Indeed, after his defeat the world has changed for Kasparov, but also for the computer-chess researchers. They are looking for new goals and new challenges. Ingo Althöfer believes that changes in the world should be followed by changes to concepts and changes of rules. First he developed his 3-Hirn idea further to perfection by introducing a LIST-3-Hirn, combining ideas on k-best moves with ideas on democratic decisions taken by three brains. Then he challenged Grandmaster Arthur Yusupov to a shuffle-chess match.

Still this is not the end of all changes, especially not since changes of behaviour have not been addressed so far. A few years ago this Journal reported on research into opponent modelling. It was a topic quickly picked up by the computer-chess world. The DEEP BLUE team modelled Kasparov sufficiently well to take advantage of their model in the 1997 match. An important part of it was the opening preparation, which everybody acknowledges as essential; it is especially recognisable as a characteristic of a World Champion. Nevertheless, opponent modelling is now a hot issue and even jeopardises the Swedish Rating List. As a spin-off of persistent research to automate all what is human, we nowadays have computer programs which can play games by auto-play. This is a clear advantage since the programs are not hampered by human intervention.

However, as a direct consequence of this technology, computer programs can play several hundred games against each other in a very short period of time. And is not AI the specific domain where such games are played intelligently, i.e., the programs learn from their experience? Hence, in a subsequent game they avoid the variations where they had lost before. So the concept of learning and of opponent modelling go hand in hand. The current technology enables us to prepare oneself against the opponent's preparation. Is this fair or not? It is clearly a question analogous to the questions of a human chess player as to whether a computer program is a fair opponent when it has much more opening knowledge directly at its disposal than a human can store in and retrieve from his/her mind. In this case we see that the discussion of fair play has been shifted from the question "do humans and computers play the same game?" to the question "what rules should be imposed to fair auto-play of computers?"

The performance of DEEP BLUE has left many traces. Chess players are trying to forget the results as soon as possible. To a large extent they are supported by DEEP BLUE's retirement. Computer-chess researchers are defining new goals. They aim their research at understanding what brute force has brought us, how we can justify the result scientifically, and how to improve tuning and learning.

In a few years, DEEP BLUE will be regarded as a phenomenon, and only those who were eye witnesses will be able to convince the laymen that at the end of the twentieth century there was a program that defeated the World Champion. The new challenge in computer-chess research is the fundamental issue of science in general, viz. the reproducibility of experiments. The computer-chess community is awaiting a repetition of such a match between the human World Champion and a program. Only if the program wins again, will the victory of DEEP BLUE be proven to be reproducible and will it be recognised as real science.

It is my sad duty to inform our readers that Bob Herschberg, our emeritus Editor, passed away quietly on March 19, 1998 at the age of 70. It was my privilege to be with him on the day before his death, when I was able to thank him for all his commitment to the ICCA. I am very grateful to him for all that he has taught me and for the warmth of his friendship. An extended obituary will be published in the next issue.



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