ICCA Journal, Volume 21:  Number 4  (December 1998)

TABLE OF CONTENTS

Editorial:                                                                                          
    A New Research Scope (H.J. van den Herik) .................................................. 209
Contributions:                                                                                      
    Chess Endgames and Neural Networks (G.McC. Haworth and M. Velliste) ........................ 211
    DarkThought Goes Deep (E.A. Heinz) ......................................................... 228
Review:                                                                                             
    Memory versus Search in Games (D. Hartmann) ................................................ 245
Literature Received:                                                                                
    Heuristic Search Methods in Parameter Space (A. van Tiggelen) .............................. 247
    13 Jahre 3-Hirn (I. Althoefer) ............................................................. 247
Reports:                                                                                            
    Report on the 5th Open Spanish Computer-Chess Championship (E. Jimenez) .................... 249
    Report on the 18th Open Dutch Computer-Chess Championship (Th. van der Storm) .............. 252
    Report on the Session Heuristic Search and Computer Game Playing (J. Uiterwijk) ............ 254
    Report on the First International Conference on Computers and Games (I. Frank                   
        and R. Grimbergen) ..................................................................... 256
    The 9th World Computer-Chess Championship (B. Monien and R. Feldmann) ...................... 266
    Tournament Rules for the 9th World Computer-Chess Championship (The Board of ICCA) ......... 267
    Entry Form for the 9th World Computer-Chess Championship (The Board of ICCA) ............... 269
    Call for Papers: Advances in Computer Chess 9 (H.J. van den Herik and B. Monien) ........... 271
    The International Colloquium Board Games in Academia 1999 (A. de Voogt) .................... 272
    The Swedish Rating List (T. Karlsson) ...................................................... 273
    ICCA Journal Referees in 1998 (The Editorial Board) ........................................ 274
    Calendar of Computer-Games Events 1999 ..................................................... 274
Correspondence:                                                                                     
    Technical Proposal on "Advanced Chess" (I. Althoefer) ...................................... 275

ABSTRACTS OF SCIENTIFIC ARTICLES

Chess Endgames and Neural Networks

Guy McC. Haworth and Meel Velliste

[21(4):211-227]   The existence of endgame databases challenges us to extract higher-grade information and knowledge from their basic data content. Chess players would like simple and usable endgame theories if such holy grail exists; endgame experts would like to provide such insights and be inspired by computers to do so. Here, we investigate the use of artificial neural networks (NNs) to mine these databases and we report on a first use of NNs on KPK. The results encourage us to suggest further work on chess applications of neural networks and other data-mining techniques.

DarkThought Goes Deep

Ernst A. Heinz

[21(4):228-244]   This contribution follows up on the work by Hyatt and Newborn (1997) who let the program CRAFTY ``go deep''. We repeated their experiment with our own chess program DARKTHOUGHT and obtained similar experimental results. Both experiments provide strong empirical evidence for the surprising observation that even at high search depths of 11 to 14 plies modern chess programs steadily discover new best moves in still 16 percent of all searches on average.

Moreover, the experiments do not reveal any conclusive trend towards fewer new best moves at search depths beyond 14 plies. Hence, the available experimental results do not really fuel the intuitive notion that such ``changes of mind'' taper off continuously with increasing search depths. If at all, only the behaviour of DARKTHOUGHT with a drop to 13.7 percent new best moves on average in iteration 14 hinted at decreasing ``changes of mind'' for search depths of 15 plies or more.

Additionally gathered data about the 14-ply searches of CRAFTY and DARKTHOUGHT allowed us to study the behaviour of both programs in greater detail. This led to the astonishing finding that regardless of the actual search depth a sizeable 30 to 50 percent of all new best moves on average represented ``fresh ideas'' which the programs never deemed best before. The finding adds support to Newborn's (1985) hypothesis about the playing strength of chess programs. Furthermore, the additional numbers educated us about continuing odd/even instabilities of modern chess programs. These instabilities decreased notably only at high search depths of 9 to 14 plies in positions with reduced material as they mostly occur in endgames and late middle games.

EDITORIAL

A New Research Scope

H. Jaap van den Herik

[21(4):209-210]   At the end of the 19th century there was a feeling that physics, seen as a complex puzzle of particles, had almost been solved. One hundred years later, we know that physics still has many riddles and that getting to the bottom of it is much more difficult than ever thought before, if not impossible. Time and again it appeared that under an assumed foundation there was a new set of basics. Quite often, mathematicians were called in to help understand the phenomena.

Analogous to what was stated in the world of physics, a few computer scientists specialized in databases opined some years ago that fundamental research in the field of databases would soon come to an end after the relational concept had been perfected. The emergence of data mining and data warehousing has undoubtedly proved them wrong. Instead of digging more deeply into their field of expertise the database researchers have widened their scope and started to collaborate closely with statisticians. Again mathematicians found themselves supporting researchers beyond their own preserve.

At the time DEEP BLUE defeated the human World Champion Garry Kasparov, many laymen thought that computer-chess research had collapsed: even though the game had not yet been solved and although that goal seemed beyond reach, it was of no interest, they felt, first to stop off somewhere between the strongest human chess player and perfection, and then attempt to move slowly further towards perfection. Even a few dedicated computer scientists have voiced opinions like these and are preparing to finish their research projects successfully.

Here too, mathematicians have proved them wrong. They did so during the First International Conference on Computers and Games. An extended report by Ian Frank and Reijer Grimbergen shows that the world of games is still thrilling and sparkling, and that the game of chess is considered as the main reference point for many scientific and organisational problems, such as how to perform research, how to improve a search technique, how to handle knowledge representations, how to deal with grandmaster notions (cognitive science), etc.

Chess is a partizan game of perfect information (partizan means that the options for the two players are not at all alike: White and Black have a different set of moves. Nim is an example of an impartial game, i.e., the options from any given position is the same for each player, regardless of whose move it is). The question now is: to what extent shall we broaden our theoretical scope, hoping to come across notions and techniques which also boost computer-chess research? Must we go all the way to imperfect games, such as bridge, or even to impartial games, such extended Wythoff's games before finding new ideas which can be incorporated into computer-chess programs? Nobody knows, and to your Editor this question embodies the very essence of a good research question.

Moreover, a generalisation to other games stresses only the chess side of computer-chess research. At the computer side we may also look for new ideas, e.g., new architectures which support our understanding of the intricacies of the game. A neural-network architecture may be such an aid comparable to Tesauro's backgammon program. In this issue Haworth and Velliste show how a neural network may increase our conceptual understanding of chess endgames. And how about using Internet? It turns out that the development of technology is much faster than that of conceptual ideas. Last year Hyatt and Newborn performed an experiment which took some three weeks and in which some 20 volunteers were involved on heterogeneous PC-class machines. They exchanged their results via Internet. In 1998 the whole experiment was repeated on one machine in fewer than five days. For details we refer to Ernst Heinz' contribution.

So far we have discussed games and computers in research environments; but how does it work in real practice? The answer is simple: the city of Paderborn will host the 9th World Computer Chess Championship (WCCC'99) and also the 9th Advances in Computer Chess Conference (ACC9). Details are given in this issue and available on WWW. This implies that competition and science will go hand in hand, from June 14 to June 20, 1999. The Heinz Nixdorf MuseumsForum (HNF) will be the venue of 32 programs competing for the World Championship title as well as the appropriate place for exchanging ideas on computers, games and chess. It is with great pleasure that I invite you all to Paderborn.