ICCA Journal, Volume 22:  Number 1  (March 1999)

TABLE OF CONTENTS

Editorial:                                                                                          
    Finding New Blood (H.J. van den Herik) .....................................................   1
Contributions:                                                                                      
    Book Learning - A Methodology to Tune an Opening Book Automatically (R.M. Hyatt) ...........   3
    A Pattern-Oriented Approach to Move Ordering: The Chessmaps Heuristic (K.R.C. Greer,            
        P.C. Ojha, and D.A. Bell) ..............................................................  13
Note:                                                                                               
    Endgame Databases and Efficient Index Schemes for Chess (E.A. Heinz) .......................  22
Review:                                                                                             
    Ingo Althoefer's 13 Years of 3-Hirn (D. Hartmann) ..........................................  33
Literature Received:                                                                                
    A New Depth-First Search Algorithm for AND/OR Trees (A. Nagai) .............................  35
    Computers and Games (eds. H.J. van den Herik and H. Iida) ..................................  36
Reports:                                                                                            
    The 8th International Paderborn Computer-Chess Championship (U. Lorenz) ....................  38
    Report on the First Open Computer-Amazon Championship (N. Sasaki and H. Iida) ..............  41
    The ICCA Triennial Meeting (The Board of ICCA) .............................................  44
        A Change to the ICCA By-Laws (The Board of ICCA) .......................................  44
        Proposition for a New Board of ICCA (The Board of ICCA) ................................  45
        The ICCA Treasurer's Report for 1998 (D.F. Beal) .......................................  45
    More Information on the 9th World Computer-Chess Championship (B. Monien, R. Feldmann,          
        and H.J. van den Herik) ................................................................  47
    Call for Participation: Advances in Computer Chess 9 (H.J. van den Herik and B. Monien) ....  54
    The 1998 ICCA Journal Award (The Board of ICCA) ............................................  55
        Andreas Junghanns: A Scientific Biography ..............................................  55
    The Scherzer Memorial Prize (T.A. Marsland) ................................................  55
    The National Medal of Technology for Dennis Ritchie and Ken Thompson (D. Cunningham) .......  56
    Machine Learning in Game Playing (Bled, 1999) ..............................................  57
    Calendar of Computer-Games Events in 1999 ..................................................  58
    Tablebase of Contents (J.W.H.M. Uiterwijk) .................................................  59
    The Swedish Rating List (T. Karlsson) ......................................................  61
    Don Beal's Collected Work (The Editor) .....................................................  62
Correspondence:                                                                                     
    The KPPKN Endgame (B. Moreland) ............................................................  63

ABSTRACTS OF SCIENTIFIC ARTICLES

Book Learning - A Methodology to Tune an Opening Book Automatically

Robert M. Hyatt

[22(1):3-12]   The paper describes some experiments in book learning by the program CRAFTY, a computer-chess program developed by the author. CRAFTY plays on various Internet chess servers, and as a result, typically plays over 20,000 games per year. A favourite tactic of many human chess players is to find a weak book line that the program follows repeatedly. They play that opening over and ove until they find a way to win the game. Thereafter they replay this game many times. Previously the author would simply edit the book by hand when such cooks were found, to prevent the program from playing these openings time after time. Recently the author has developed an approach that automates this book editing or book tuning by letting CRAFTY determine which openings are good and which are bad, and adjusting its book selections accordingly.

A Pattern-Oriented Approach to Move Ordering: The Chessmaps Heuristic

Kieran R.C. Greer, Piyush C. Ojha, and David A. Bell

[22(1):13-21]   A move-ordering method is presented that orders most moves by using a neural network in the form of the chessmaps heuristic. The neural network is trained to order sectors, or areas of the chessboard, depending on the territorial control of each side. Moves are then ordered depending on which sectors they influence. The complete move-ordering method takes account of immediate tactical threats, in the form of forced or capture moves, before the positional evaluation of the chessmaps heuristic is used.

The chessmaps heuristic has extracted some intelligent chess information from the examples it has been trained on. In particular, it has learnt a very basic strategy. When White controls the whole chessboard, the chessmaps heuristic suggests attacking sectors for White. When Black controls the whole chessboard, the chessmaps heuristic suggests defensive sectors for White. When the amount of control is equal, the chessmaps heuristic suggests attacking sectors where defensive factors play a part. So, it looks like the program knows something about when to attack or defend. The heuristic has also learnt some notions of centralisation.

Because this AI approach is relatively simple, it is suitable when supported by a substantive brute-force search. Preliminary test runs comparing this move-ordering method with other heuristic combinations involving the killer and history heuristics are encouraging, since our move-ordering method searched fewer nodes.

Endgame Databases and Efficient Index Schemes for Chess

Ernst A. Heinz

[22(1):22-32]   Endgame databases have become an integral part of modern chess programs during the past few years. Since the early 1990s two different kinds of endgame databases are publicly available, namely Edwards' so-called tablebases and Thompson's collection of 5-piece databases. Although Thompson's databases enjoy much wider international fame, most current chess programs use tablebases because they integrate far better with the rest of the search. For the benefit of all those enthusiasts who intend to incorporate endgame databases into their own chess programs, this note describes the index schemes of Edwards' tablebases and Thompson's databases in detail, explains their differences, and provides a comparative evaluation of both.

In addition we introduce new indexing methods that improve on the published state of the art and shrink the respective index ranges even further (especially for large databases and endgames with Pawns). This reduces the overall space requirements of the resulting databases substantially. We also propose several solutions for the problem of potential en-passant captures in endgame databases with at least one Pawn per side. Shortly after the initial submission of our original text for this note, Nalimov independently applied similar techniques as ours and even more advanced index schemes to his new tablebases which are now publicly available on the Internet, too. We briefly put his work into perspective as well.

EDITORIAL

Finding New Blood

H. Jaap van den Herik

[22(1):1-2]   At the 1999 Triennial Meeting, the ICCA members will vote for a new Board, but in this very issue the current Board has complained that new blood was hard to find. Is there not a parallel here to the world of chess where until recently Kasparov reigned in splendid isolation and without any successors in sight, even not on the distant horizon? Where would a successor come from? Presumably we would look for someone capable of beating Kasparov. The only serious candidate is DEEP BLUE, not a person but a program that forced him to attend the fact that new blood had arrived in the form of bits and bytes.

We do not know whether the ICCA officers considered nominating a computer program as one of its new officers. What we do know is that the by-laws will be changed and that soon a programmers' representative will be an official Board member. The question still remains whether further changes are advisable. If a computer program cannot be elected as an officer, will the Triennial Meeting allow programs to be a member? Maybe, the Treasurer will support this idea, but your Editor believes that the time is not yet ripe for such a proposal. Unfortunately, as matters stand now, this implies that the new blood stream only comes from Martin Zentner, since all other candidates are members who have deserved their credits over the last two decades.

In contrast with the suggestive reasoning above, we would like to defend the following statement: the older a man, the wiser he is. Now we touch upon the question: to what extent will this line of reasoning be valid? It is well known that mathematicians usually reach their top before they have turned twenty five, whereas psychologists typically are over fifty before reaching their zenith. In his farewell speech (1978) at the University of Amsterdam, Professor Adrian de Groot dealt with the topic that every researcher has his/her ceiling and that for persistent researchers their life task is clear: reaching their personal peak. After the peak, i.e., when growing older, the distance to one's own ceiling usually becomes larger. However, there may be exceptions and exceptional persons.

One of these exceptional persons is also recognised in this issue of the Journal: Ken Thompson. Together with Dennis Ritchie, he has been awarded the U.S. National Medal of Technology for his contribution to UNIX and the C language. For the computer-chess community it is regrettable that the U.S. President, who announced the Award, did not mention his formidable achievements in our research domain, namely the chess machine BELLE and his well-known CD-ROMs with the three-, four-, and five-piece databases. The latter results are still a landmark for young researchers, as is evident from Ernst Heinz's note in this issue. Only gradually has some progress been made in this field of research in the last ten years. Here too we are waiting on new blood and a new breakthrough.

Apparently, the old ones are doing well in research as well as in administration. How will this be in the competition in Paderborn? There we expect a change from an old-timer to a newcomer. So far, only CRAY BLITZ has successfully defended its World Champion title, namely as far back as in Cologne 1986. It is up to FRITZ, the 1995 World Champion, to try and repeat this performance, but the competition will be tough. Some thirty participants will be competing, ten of them will be vying seriously for the title. Some of them are old contenders, but many are brand new. Moreover, it has been communicated to us that some old names are identifiers for completely fresh ideas embodied in modern program code.

For the first time the World Championship Tournament will coincide with the Advances in Computer-Chess Conference, both being in their ninth edition. Computer chess has matured, the playing strength is at Grandmaster level, and computer-chess research has been inspirational for other games in such a way that the Advances in Computer-Chess Conference has grown up to a proud Advances in Computer-Games Conference. This issue already forbodes such a development, by reporting on a recent Computer-Amazon tournament.

Clearly, here we see ringing out the old games, ringing in the new ones, shuffle chess and advanced chess among them. So, what is our editorial position with respect to the idea of having three generations meeting (the old ones, the new ones, and the computers)? The answer is that a fully-fledged community favours a well-balanced mix of old and new, since that is best for the community's life expectations. Therefore, your Editor believes that with the new Board and the current group of researchers, the ICCA is well alive and strongly kicking to come to the top.