ICCA Journal, Volume 19:  Number 1  (March 1996)




TABLE OF CONTENTS
Editorial:                                                                                          
    Matchless (I.S. Herschberg and H.J. van den Herik) .........................................   1
Contributions:                                                                                      
    The ABDADA Distributed Minimax-Search Algorithm (J.-C. Weill) ..............................   3
    Hybrid Heuristic Search (A.N. Walker) ......................................................  17
Note:                                                                                               
    An Examination of the Endgame KBBKN (S.J. Edwards) .........................................  24
Literature Received:                                                                                
    Statistical Feature Combination for the Evaluation of Game Positions (M. Buro) .............  32
Reports:                                                                                            
    Konrad Zuse: An Obituary (I.S. Herschberg and H.J. van den Herik) ..........................  34
    The Future of Computer Chess (T.A. Marsland) ...............................................  36
    The Kasparov - Deep Blue Match (J.W.H.M. Uiterwijk) ........................................  38
    The Kasparov - Deep Blue Games (Y. Seirawan) ...............................................  41
    Report on the Sixth Harvard Cup Human versus Computer-Chess Challenge (C. Chabris) .........  58
    The 1994-95 Novag Award (T.A. Marsland) ....................................................  65
    The 1995 ICCA Journal Award (The Board of ICCA) ............................................  66
        Bradley C. Kuszmaul: A Scientific Biography ............................................  66
    Call for Participation: Advances in Computer Chess 8 (Maastricht, The Netherlands) .........  67
    Calendar of Computer-Games Events 1996 .....................................................  69
    The 11th AEGON Computer-Chess Tournament (C. de Gorter) ....................................  69
    The Swedish Rating List (T. Karlsson and G. Grottling) .....................................  71




ABSTRACTS OF SCIENTIFIC ARTICLES


The ABDADA Distributed Minimax-Search Algorithm
Jean-Christophe Weill

[19(1):3-16]   This paper presents a new method to parallelize the minimax tree-search algorithm. This method is then compared to the Young-Brothers-Wait-Concept algorithm in two implementations: Othello and Chess. Results of tests on a 32-node CM5 are given.


Hybrid Heuristic Search
Andrew N. Walker

[19(1):17-23]   We report on some experiments in combining a shallow tree-search with a set of heuristics, implemented as filters, specifically in the KQKR ending. It proves difficult to make progress against a computer database (assumed to have knowledge about the heuristics being used), but the combined filters compare well with strong human play.


An Examination of the Endgame KBBKN
Steven J. Edwards

[19(1):24-31]   This note presents the results of the computer generation of the complete KBBKN distance-to-mate/loss database by the program SPECTOR. It is a sequel to an earlier note in this Journal (Edwards and the Editorial Board, 1995). Comments concerning prior computer-assisted investigation of KBBKN can be found in ``Retrograde Analysis of Certain Endgames'' by Ken Thompson (1986). Thompson's results are for WTM (White to move) and indicate a maximum of 66 moves for White to achieve a won position. Also, about 91.8 percent of KBBKN positions are won for White. The definition of `won position' is one where White has either achieved a checkmate or has captured the black Knight while obtaining a won position in the successor configuration KBBK. Position verdicts (win/non-win) given by Thompson's KBBKN database as referenced in numerous articles have been confirmed by SPECTOR's results.

A related note by the Editors (1992) of this Journal, ``Thompson: All About Five Men'', provides some more results about KBBKN and other five-man endgames. A comprehensive analysis of Thompson's KBBKN distance-to-win results can be found in ``Ideas on Knowledge Synthesis Stemming from the KBBKN Endgame'' (Michie and Bratko, 1987). Of particular interest is a graph which presents a histogram of the distribution of the number of white wins versus the distance-to-win. There is a definite ``pinch'' or nodal point in the distribution that occurs in the region of 54 moves to win. The same general shape of the distance-to-conversion distribution is also present in SPECTOR's distance-to-mate and distance-to-loss distributions. For the WTM distance-to-mate distribution, this nodal point occurs at mate-in-66. For the BTM distance-to-lose distribution, it occurs at loss-in-67.




EDITORIAL


Matchless
I. Samuel Herschberg and H. Jaap van den Herik

[19(1):1-2]   The theory, however implicit, underlying the World Championship has always been that the World Champion was without match among his peers. In principle at least, the successful candidate struggled his way up through tournaments and matches, comprising many tens of games against successive adversaries. Thus, the assessment ``World Champion'' is essentially a statistical judgement, being based on successive victories. Let us recall: ten matches at 6.5 to 5.5 each would suffice for the title. Though finding such a Champion matchless? - definitely not: rather the best among equals. In such a context, an outcome of 4 to 2 is hardly overwhelming.

It follows that the Kasparov- DEEP BLUE match is almost neutral, the more so as the sample size, six games, was extremely curtailed and there is no repetition in sight. If one reverts to the dry-as-bones view of the statistician, any conclusion from the match is as strictly invalid as concluding to the bias of a coin after only six flips.

The World Champion is still without match among his peers: he won the match. Those in the know were not greatly surprised. They had expected nothing spectacularly better. Still and all, the computer's straight win in the first game in 37 moves only was a breath-taking surprise as was the level pegging of 2-2 after four games.

What has changed far outweighs the invariance. The playing style, notably Kasparov's, has been adaptive and responsive as befits a World Champion. As the match progressed, Kasparov provided fewer and fewer leads for DEEP BLUE to follow. Conversely, DEEP BLUE was allowed his rein, at which the program proved rather helpless. In the fifth and sixth games, the program seemed to have lost its bearings.

Another change may well have been that in this match it was no longer an easy matter to distinguish between human and computer moves; it is not yet five years ago that several authors have castigated computer play as being over-acquisitive, naive, and visibly mechanical. No longer so: this match has contributed to establishing the near-equality of the program and the Champion.

The most radical upheaval, however, was in the sociology of computer chess. Twenty years ago, there was a majority of sceptics willing to deny that computers ever could play reasonable chess. In the run up to the Kasparov match, opinions had reversed. Very many were surprised that 256 processors failed to win the day. There is a most interesting implication here: in the popular view, a chess engine is now a fully-fledged chess-player, capable of holding its own against the best - if not quite with 256 processors then surely with a small multiple thereof, it will be the best.

To sum up, the match Kasparov- DEEP BLUE was matchless and Kasparov has remained without match. We offer two riders. First, DEEP BLUE was at a disadvantage for not having been able to train against Kasparov beforehand. Second, within one and the same match, the competitors diverged in their aims. It was stated that DEEP BLUE inflicted wounds on itself by refusing an offer for a draw which eventually led to its loss. Allegedly, this was in the interest of science. But was it science, other than engineering with the ultimate purpose of winning ever after?

Finally, we most recognize that the very top of the world chess-players has now unexpectedly been augmented by DEEP BLUE and its immediate successors. It is to be hoped and expected that with more top players in the game, chess, already matchless among games, will find itself even more elevated. It would be most surprising if this extension would not give rise to more research leading to more chess knowledge. In short, Kasparov- DEEP BLUE was a matchless occasion in the matchless course of the game.



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