ICCA Journal, Volume 20:  Number 1  (March 1997)

TABLE OF CONTENTS

Editorial:                                                                                          
    Augmented Ideas (H.J. van den Herik) .......................................................   1
Contributions:                                                                                      
    The Dynamic Tree-Splitting Parallel Search Algorithm (R. Hyatt) ............................   3
    The Legitimacy of Positions in Endgame Databases (D. Lippold) ..............................  20
    Searching with Uncertainty Cut-offs (Y. Bjoernsson, T.A. Marsland, J. Schaeffer,                
        and A. Junghanns) ......................................................................  29
Literature Received:                                                                                
    Kasparov versus Deep Blue: Computer Chess Comes of Age (M. Newborn) ........................  38
Reports:                                                                                            
    A Symbiosis of Man and Machine Beats Grandmaster Timoshchenko (I. Althoefer) ...............  40
    The 6th International Paderborn Computer-Chess Championship (U. Lorenz) ....................  48
    The Spanish Computer-Chess Championship (E. Castillo Jimenez) ..............................  51
    The AAAI-97 Workshop: Deep Blue vs. Kasparov ...............................................  53
    The IJCAI-97 Workshop on Computer Games ....................................................  54
    The First Mind Sports Olympiad (D. Levy) ...................................................  56
    The 12th AEGON Man-Machine Tournament (C. de Gorter) .......................................  57
    The International Colloquium Board Games in Academia (A. de Voogt) .........................  58
    The 1996 ICCA Journal Award (The Board of ICCA) ............................................  60
        Michael Buro: A Scientific Biography ...................................................  60
    Calendar of Computer-Games Events 1997 .....................................................  61
    Riding High - The ICCA Treasurer's Report for 1996 (D.F. Beal) .............................  62
    The ICCA Journal on Internet: An Investigation (P. Beck and A.E.M. van den Bosch) ..........  63
Correspondence:                                                                                     
    Computer Chess: A Unifying Theme (M. Levene) ...............................................  64
    ICCA Tournament Rules Revisited (E.A. Heinz) ...............................................  65
    The Swedish Rating List (T. Karlsson and G. Grottling) .....................................  67

ABSTRACTS OF SCIENTIFIC ARTICLES

The Dynamic Tree-Splitting Parallel Search Algorithm

Robert M. Hyatt

[20(1):3-19]   This paper describes a high-performance parallel tree-search algorithm that uses Dynamic Tree Splitting (DTS) for searching alpha-beta minimax game trees. The algorithm divides the search tree among several processors on a shared-memory parallel machine. The paper deals with the following topics: (1) the DTS algorithm, (2) analyzing alpha-beta to select split points, (3) performance results of the algorithm, and (4) analysis of the results to see where further improvements might occur.

The Legitimacy of Positions in Endgame Databases

Dietmar Lippold

[20(1):20-28]   Current endgame databases provide optimal sequences of moves from a given position to conversion or to mate. They do not investigate whether the given position is legitimate. This contribution considers the database as a model of the particular chess configuration under investigation and attempts to classify the positions in legitimate and illegitimate positions. Assuming a position to be legitimate if it can be reached from the starting position by legal moves only, the question is what means do we need to prove the legitimacy of a position.

For this purpose, we first define three new concepts: initially illegitimate, derivedly illegitimate and isolatedly illegitimate. Then we propose a constructive procedure which enables us to show that a position can be reached. Related to the new concepts we introduce a broad definition of illegitimacy (based on initially illegitimate only) and a narrow definition (taking into account also derivedly illegitimate). For both cases we have examined the 3- and 4-man databases of which results are given. Further research of 5- and 6-man databases is envisaged.

Searching with Uncertainty Cut-offs

Yngvi Björnsson, T. Anthony Marsland, Jonathan Schaeffer, and Andreas Junghanns

[20(1):29-37]   A new domain-independent pruning method is described that guarantees returning a correct game value. Even though alpha-beta-based chess programs are already searching close to the minimal tree, there is still scope for improvement. Our idea hinges on the recognition that the game tree has two types of node: those where cut-offs occur, and those that must be fully explored. In the latter case one of the moves is best and yields the subtree value; thus for the remaining alternatives it is enough to show their inferiority. This offers an opportunity for pruning, while introducing some potential for uncertainty in the search process. There are two cases of interest. One considers the immediate alternatives to the Principal Variation itself; here a new safe cut-off is presented. The other is a proposal for an unsafe generalization, one which offers substantial search reduction but with the potential for control of the error probability. Experiments with the new pruning method show some savings in the search.

EDITORIAL

Augmented Ideas

H. Jaap van den Herik

[20(1):1-2]   As every knowledgeable researcher understands, inspired ideas published in a Journal are meant for a wider dissemination. But how should we treat the dissemination and the reuse of algorithms and programs? And how should we cope with ideas that are traceable, that are well-known among practitioners, but that have not yet been published? Although these questions are still difficult to answer, it seems that there is a tendency to deal with them in a manner which is different from that of ten years ago.

Indeed, the question on publications is not so difficult. Obviously, when drawing on ideas from published articles appropriate references should be made to the source. Such behaviour should also be the case when the ideas are not published, but nevertheless traceable. Sometimes this is done by personal communication, sometimes by simply giving credit in the text, and nowadays we see references to home pages and Internet addresses. Of course, such reference behaviour presupposes a thorough knowledge of the research field and a tempered ambition. There is a grey area between what is permitted, and what is plagiarism. Sometimes, the problem of the grey area is resolved through the originator publishing his/her ideas.

The Editorial Board is therefore pleased with Bob Hyatt's contribution. So far, the ideas behind Dynamic Tree Splitting (DTS) have not been published in such a lucid way. The ideas have been around since Hyatt's Ph.D. thesis in 1988. Meanwhile, they have been augmented and are now presented forthrightly with new experiments, showing their merit and the power of shared-memory computers. This might solve a particular question on publications. It does not solve all the questions above and, in particular, it does not give any clue to the other problems. The best we can do is to make these problems explicit.

In the previous issue Chrilly Donninger embarked upon the algorithmic question by challenging the ICCA tournament rules. He referred to the discussion of entering a cloned program into the 1989 World Microcomputer Chess Championship. At that time, entering a cloned program was absolutely not permitted. However, today we have Donninger's contribution to the computer-chess community, called NIMZO-3, containing tools which allow the user to modify substantially NIMZO-3's search process, its opening book and its knowledge base (e.g., the heuristics used). So, can one buy NIMZO-3, change it at home, and enter any tournament? "Yes", Donninger said, - he even encouraged such behaviour - "as long as such a user does not deny the NIMZO roots."

The question posed above theoretically has been partially answered in recent practice. In the 14th WMCC (Jakarta, 1996), the Indonesian program GUNDA-1 participated, and in the 16th Open Dutch Computer-Chess Championship (Leiden, 1996) the program RAJAH was entered. Both programs were based on Hyatt's world-wide available code of the program CRAFTY. Since both teams gave due credit to CRAFTY as their original source, it is comparable to using ideas from articles while giving appropriate reference. Nevertheless, the question remains to what extent can we prolong the similarity of publications and programs. For articles, we do not allow plagiarism. For algorithms and programs I believe we are in a state of flux. Yet, the researcher who is the originator of the ideas should always be given pride of place.

In these particular cases it is peculiar that Bob Hyatt plays a role in both. However, there is no reason for him to complain. The ideas on EPVS and DTS are always credited to him and now they are in the open. His merits for CRAFTY are recognized by his end-users and by the ICCA through the Novag Award.

To conclude, we shift to a closely-related topic, viz. the considerable acceleration of the dissemination of information, algorithms and programs by Internet access. Technical, financial and scientific problems are encountered when an Association starts communicating with its members via Internet. The ICCA is currently investigating how to deal with these problems. There are many ideas, many solutions, but we are searching for a good solution in which the ICCA and its Journal will flourish.