ICCA Journal, Volume 19:  Number 3  (September 1996)

TABLE OF CONTENTS

Editorial:                                                                                          
    Paradigms Fork: All Must Join (I.S. Herschberg and H.J. van den Herik) ..................... 145
Contributions:                                                                                      
    Machine Learning in Computer Chess: The Next Generation (J. Fuernkranz) .................... 147
    A Taxonomy of Parallel Game-Tree Search Algorithms (M.G. Brockington) ...................... 162
Notes:                                                                                              
    Replacement Schemes and Two-Level Tables (D.M. Breuker, J.W.H.M. Uiterwijk,                     
        and H.J. van den Herik) ................................................................ 175
    An Upper Bound for the Number of Reachable Positions (S.S. Chinchalkar) .................... 181
Literature Received:                                                                                
    Perception and Memory in Chess (A.D. de Groot and F. Gobet) ................................ 183
    Research, Re: Search and Re-Search (A. Plaat) .............................................. 186
    Best-First Minimax Search (R.E. Korf and D.M. Chickering) .................................. 187
    Der Schachcomputerkatalog 1996 (P. Schreiner) .............................................. 187
Reports:                                                                                            
    Report on the Advances in Computer Chess 8 Conference (Y. Bjornsson, M.G. Brockington,          
        A. Junghanns, and A. Plaat) ............................................................ 189
    The Exhibition Games (D.M. Breuker and H.J. van den Herik) ................................. 192
    Two Interviews with Ken Thompson (H.J. van den Herik) ...................................... 193
    The 1996 World Microcomputer Chess Championship (D. Levy) .................................. 205
    Calendar of Computer-Games Events 1996 ..................................................... 208
    The Swedish Rating List (T. Karlsson and G. Grottling) ..................................... 209
Correspondence:                                                                                     
    Go Beyond Chess (M. Schreiber) ............................................................. 210
    Computer Chess and Beyond? (D. Rickett) .................................................... 210
    Stay with Chess (E.A. Heinz) ............................................................... 211

ABSTRACTS OF SCIENTIFIC ARTICLES

Machine Learning in Computer Chess: The Next Generation

Johannes Fürnkranz

[19(3):147-161]   Ten years ago the ICCA Journal published an overview of machine-learning approaches to computer chess (Skiena, 1986). The author's results were rather pessimistic. In particular he concluded that ``with the exception of rote learning in the opening book, few results have trickled into competitive programs'' and that ``there appear no research projects on the horizon offering reason for optimism.'' In this paper we will update Skiena's work with research that has been conducted in this area since the publication of his paper. By doing so we hope to show that at least Skiena's second conclusion is no longer valid.

A Taxonomy of Parallel Game-Tree Search Algorithms

Mark G. Brockington

[19(3):162-174]   In the last twenty years, a number of articles and theses have been written that contain innovative parallel game-tree search algorithms. The authors of the parallel algorithms have shown how their work is unique and interesting. In some cases, this has been shown by classifying other algorithms by listing implementation details (Bal and Van Renesse, 1986; Ciancarini, 1994). To the author's knowledge, no attempt has been made to classify the algorithms based solely on their algorithmic properties. A taxonomy would make it easy to ascertain what has and has not been accomplished in parallel game-tree search. The presentation of this type of taxonomy is the main contribution of this paper.

Replacement Schemes and Two-Level Tables

Dennis M. Breuker, Jos W.H.M. Uiterwijk, and H. Jaap van den Herik

[19(3):175-180]   This note completes the comparison of the performances of seven replacement schemes. The performances are presented as functions of the transposition-table size. Some 200 chess middle-game and endgame positions have been studied. It turns out that the number of nodes of a subtree is a better estimate for potential savings than the depth of a subtree. A two-level table, using the number of nodes in the subtree searched as the deciding criterion, performs best and is recommended. Previous results based on fewer experiments are confirmed.

An Upper Bound for the Number of Reachable Positions

Shirish S. Chinchalkar

[19(3):181-182]   (Text still missing ...)

EDITORIAL

Paradigms Fork: All Must Join

I. Samuel Herschberg and H. Jaap van den Herik

[19(3):145-146]   There is great danger in a furious rate of change. Anyone who has witnessed vorticity developing from apparently innocuous initial conditions will agree. Anyone who has watched the programs evolve over the past ten years will agree emphatically. Our world has changed to the point where a minor revolution occurs twice a decade and, in effect, significant evolution can be recorded within the year. Now this process is cumulative and destroys the continuity some would fondly cherish. Developments are so fast, so chaotic that one has every reason to be in fear of the flapping of a butterfly's wings, knowing that it can unleash a hurricane a few days hence and half a globe away.

The two major contributions in this issue provide testimony to a possibly chaotic rate of evolution in the programs that are the source and aim of this Journal. Reviewing ten full years, Fürnkranz has extremely pertinent considerations to offer on the eternal theme of learning. Do not be surprised at the persistence of this notion: by its nature, learning never ceases. What seems unchanged since Skiena (1986) is rote learning, say as in a stored opening book. The lack of change is only apparent: since the magnitude of the rote base has gone up by some critical factor, say from KBytes to MBytes in their hundreds and beyond, we have an amount of knowledge which is qualitatively different through sheer force of being quantitatively expanded. To stress the difference, we should note that the material is now indexed infinitely better. Who could have dreamed of NIC as an ongoing concern?

By happy coincidence, this issue offers a review of searching techniques by Brockington, also looking back to the mid-1980s. Taking again 1986, we see Marsland providing an overview of search algorithms applicable, of course, to a single processor. In the ten years intervening, there has been a shift to searching in parallel. None of the 1986 results have been invalidated; it is just that they have become largely irrelevant through the pressing necessity of exploiting a parallelism almost unheard of ten short years ago. What the articles have in common is that they exhibit such a radical departure from their predecessors that one is forced to postulate a change of paradigm. What was necessarily learned by rote can now be acquired by query, to offer but one example. What was explored on a single-engine track, may now be searched in a shunting-yard providing room for many parallel machines. We cannot and should not anticipate the results our authors present, but we do note the paradigmatical consequences. Even those who will oppose AI now find themselves naturally tending to use the universe of discourse that is typically that of Artificial Intelligence. It is hardly possible to avoid the use of terms, such as ``neural networks'' and ``genetic algorithms''; these objects merit serious applicative study. Nor can one avoid ``search overhead'' and ``communication overhead'' stemming from the realm of parallelism.

The combination of learning and parallelism is a heady mixture, with a potential still hardly touched upon. Due to this potential of the new paradigms we cannot even be sure we have not already entered the era in which, by any objective criterion, the World Champion will be a parallel computer, able and willing to learn. It is our considered opinion that this will not constitute a break in continuity, but that it will be a simple consequence of the new paradigm: many processors acting together, intelligently to all intents and purposes.

There is still an ultimate challenge: learning in parallel, requiring, we believe, yet another change of paradigm. It is fascinating but premature to speculate whether this paradigm is among those conceivable at all.