ICCA Journal, Volume 21:  Number 3  (September 1998)

TABLE OF CONTENTS

Editorial:                                                                                          
    Magic Games and Chess (H.J. van den Herik) ................................................. 145
Contributions:                                                                                      
    Games: The Next Challenge (J. Pitrat) ...................................................... 147
    Efficient Interior-Node Recognition (E.A. Heinz) ........................................... 157
    Synthesis of Chess and Chess-like Endgames by Recursive Optimisation (K.P. Coplan) ......... 169
Note:                                                                                               
    Planning a Strategy in Chess (J. van Reek, J.W.H.M. Uiterwijk, and H.J. van den Herik) ..... 183
Literature Received:                                                                                
    Benefits of Using Multivalued Functions for Minimaxing (A. Scheucher and H. Kaindl) ........ 193
    Pruning Algorithms for Multi-Model Adversary Search (D. Carmel and S. Markovitch) .......... 193
    Searching in Games with Incomplete Information: A Case Study Using Bridge Card Play             
        (I. Frank and D. Basin) ................................................................ 194
    Pragmatic Navigation: Reactivity, Heuristics, and Search (S.L. Epstein) .................... 194
Reports:                                                                                            
    Anand versus Rebel 10 exp. (J. Noomen and E. Schroeder) .................................... 196
    A Report on the 4th FOST-Cup World-Open Computer-Go Championships (A. Yoshikawa                 
        and H. Iida) ........................................................................... 202
    Calendar of Computer-Games Events 1998 ..................................................... 206
    The Swedish Rating List (T. Karlsson) ...................................................... 207

ABSTRACTS OF SCIENTIFIC ARTICLES

Games: The Next Challenge

Jaques Pitrat

[21(3):147-156]   After the successes of many chess-playing programs, one may wonder whether it is necessary to keep on developing chess programs. Perhaps it would be better to realize programs for games such as Go, where the best programs are still weak. In this contribution, we suggest that it is time to shift focus on general game-playing systems and to realize them. Such systems will receive the specification of a new game. Subsequently they will analyze the specifications so that they will be able to play the game reasonably well. We will see how one can define such a specification and how a system may study it in order to extract useful knowledge. The problem is ultra difficult, but also highly challenging for AI. Obviously, as long as we call a system intelligent when it solves only one problem we must face the critique that most of the intelligence is in the brain of the author and little in the program itself.

Efficient Interior-Node Recognition

Ernst A. Heinz

[21(3):157-168]   This article re-examines the implications of interior-node recognition when focussing on its efficient yet seamless integration into modern chess programs. After a thorough discussion of the fundamental principles, we reveal various problems related to the practical application of interior-node recognition. Subsequently, we present an implementation framework for recognizers that solves all known problems and has already proven its practical viability in our high-speed chess program DARKTHOUGHT.

Among others we introduce the new concept of material signatures which allow for the quick and easy classification of chess positions into different categories of material distribution. By including material signatures in the internal representation of the chess-board, they can be updated incrementally during the execution of moves. This makes the computation of material signatures very cheap in practice.

Synthesis of Chess and Chess-like Endgames by Recursive Optimisation

Kevin P. Coplan

[21(3):169-182]   A new algorithm is presented for synthesising correct and optimal game-playing programs directly from the specifications. The programs deal with chess-like endgames. The algorithm is based on the principle of self-optimisation allowing the program-construction process to be time-feasible. A LISP implementation of the synthesising algorithm has generated a program for playing optimally a three-piece endgame on a specialised board. The program established the general KB/RK configuration as a win for White, and constructed a maximin of 39 moves; moreover it provided an analysis of the maximin position. The experimental results are presented. Finally, the relationship to other game-playing work is discussed, and the applicability of the algorithm to more general domains is considered.

Planning a Strategy in Chess

Jan van Reek, Jos W.H.M. Uiterwijk, and H. Jaap van den Herik

[21(3):183-192]   Planning plays a major role in chess. The range of planning may be short, medium, or long. Short-term planning is dominated by tactics; medium-range planning is usually identified with positional play, and long-term planning is assumed to require human interpretation for the recognition of strategic patterns. In this note we investigate the differences among the three types of planning. We have tested three programs ( CRAFTY, M-CHESS 6, and M-CHESS 7) on a set of 24 positions. M-CHESS 7 scores faultlessly for tactics and positional play, and 73 percent for strategy. If the hardware and software are further improved, the computer analysis will become sovereign in long-term planning too.

EDITORIAL

Magic Games and Chess

H. Jaap van den Herik

[21(3):145-146]   Magic has been a dominating factor for centuries. Some have used it for their health, others as a source of inspiration. The arrival of the digital computer, a magic phenomenon in itself, has caused a diverging of opinions on its capabilities, in particular after Shannon's (1950) article ``Programming a Computer for Playing Chess''. For some it was unbelievable that a computer could play chess at all, let alone at an acceptable level, and certainly not at Grandmaster level or, even stronger, above the level of World Champion.

Chess was a magic game, full of intricacies, with its own world. Many authors of chess studies or composers of chess problems have tried to sublimate the practical findings of Grandmasters. Frequently they succeeded in glorifying compositions, which excelled in beauty and simplicity. A superb instance is Réti's (1921) KPKP study.

Currently computer programs are surpassing the world-top chess players. Instances of this process are Kasparov's (1997) defeat against DEEP BLUE, and Anand's (1998) mixed contest against REBEL, reported in this issue. Does this mean that the magic of chess has been unravelled? No, since solving the game is beyond our reach, the magic remains and the investigations will continue.

Nevertheless, we see that researchers are widening their scope of examination. Three distinct amplifications of research are worth mentioning: (1) thorough investigation into the fundamentals of the concept strategy, (2) further development of chess-like games, and (3) profound study of metagames.

This issue of the ICCA Journal illustrates all three lines of research. First, the program REBEL showed in its 8th game against Anand that it definitely needs some strategic guidelines in order to understand an unbalanced position. Moreover, Van Reek et al. argue that strategy can be calculated by a planning machine when containing the appropriate determinants of tactics and positional play, provided that the machine can reach a sufficiently deep level of search.

Second, the development of chess-like games is extensively discussed by Coplan, using a special board and a special concept of promotion: a Bishop may promote to a Rook, and a Rook to a Bishop. In addition, the gap between strategy and chess-like games is bridged by a report on the 4th FOST-Cup World Computer-Go Championships.

Third, the next challenge of computer-chess research is closely linked up with the understanding of the secrets of an arbitrarily-specified game. Playing these so-called metagames at an acceptable level requires a kind of interpretation which is at a par of adequate language understanding. Hence, we welcome Jacques Pitrat's contribution as an encouragement to deepen research in this direction.

Considering the development of our research in the 20th century we see the following evolution: from mathematics to computer science to games to chess. Having reached a position of equal footing with human performances in chess we are now retracing the evolutionary footpath, with magic transformed into bits and bytes. In the end we will arrive at mathematics and will have revealed its own magic.

Recently, a first sign of solving complex computer puzzles in that area has been published, viz. on most-perfect pandiagonal magic squares. The construction is to be regarded as a metagame in mathematics. The authors are worth being introduced. Dame Kathleen Ollerenshaw, born in 1912, has been a great admirer of H.G. Hardy all throughout her life. David Brée was a Ph.D. student of H.A. Simon. So, the idea of a General Problem Solver has come to life again. The future will reassess its value.

Reference: Ollerenshaw, K.D. and Brée, D. (1998). Most-Perfect Pandiagonal Magic Squares: Their Construction and Enumeration. The Institute of Mathematics and Its Applications, Southend-on-Sea, Essex, SS1 1EF, UK. ISBN 0-905091-06X.