ICCA Journal, Volume 17:  Number 4  (December 1994)




TABLE OF CONTENTS
Editorial:                                                                                          
    The Five Powers (I.S. Herschberg and H.J. van den Herik) ................................... 181
Contributions:                                                                                      
    Replacement Schemes for Transposition Tables (D.M. Breuker, J.W.H.M. Uiterwijk,                 
        and H.J. van den Herik) ................................................................ 183
    Distributed Searches: A Basis for Comparison (C.P. Ciancarini) ............................. 194
    Solution Trees as a Basis for Game-Tree Search (A. de Bruin, W. Pijls, and A. Plaat) ....... 207
Literature Received:                                                                                
    Heuristic Theories on Game-Tree Search (H. Iida) ........................................... 220
    Methods for the Improvement of Search Algorithms (A. Junghanns) ............................ 220
    Processing of Knowledge from Databases (G. Lachmann) ....................................... 221
    Transactions of the Japan Computer-Chess Association (T. Baba) ............................. 221
    Agent Searching in a Tree and the Optimality of Iterative Deepening (P. Dasgupta,               
        P.P. Chakrabarti, and S.C. DeSarkar) ................................................... 222
    A Bibliography on Minimax Trees (C.G. Diderich) ............................................ 222
    A Survey on Minimax Trees and Associated Algorithms (C.G. Diderich and M. Gengler) ......... 222
Reports:                                                                                            
    The 5th Harvard Cup Human-versus-Computer Intel Chess Challenge (C. Chabris and D. Kopec) .. 224
    The 4th International Paderborn Computer-Chess Championship (U. Lorenz and V. Rottmann) .... 233
    The 14th Dutch Computer-Chess Championship (P. Kouwenhoven) ................................ 237
    ICCA Board Elections ....................................................................... 239
    The Swedish Rating List (T. Karlsson and G. Grottling) ..................................... 240
    Calendar of Computer-Games Events 1995 ..................................................... 241
    International Colloquium: Board Games in Academia .......................................... 241
    The 8th ICCA World Computer-Chess Championship (D.N.L. Levy) ............................... 242
Correspondence:                                                                                     
    `Twixt Cup and Lip ...' (C. Chabris and D. Edelman) ........................................ 245
    ... Cape May Be a Slip (T.A. Marsland) ..................................................... 246
    Intuition - Is It there? (A.D de Groot) .................................................... 246
    In Tuition - Hi-Fi and High Fee? (H.J. van den Herik and I.S. Herschberg) .................. 247




ABSTRACTS OF SCIENTIFIC ARTICLES


Replacement Schemes for Transposition Tables
Dennis M. Breuker, Jos W.H.M. Uiterwijk, and H. Jaap van den Herik)

[17(4):183-193]   Almost every chess program makes use of a transposition table, typically implemented as a large hash table. Even though this table is usually made as large as possible, subject to memory constraints, collisions occur. Then a choice has to be made which position to retain or to replace in the table, using some replacement scheme. This article compares the performance of seven replacement schemes, as a function of transposition-table size, on some chess middle-game positions. A two-level table, using the number of nodes in the subtree searched as the deciding criterion, performed best and is provisionally recommended.


Distributed Searches: A Basis for Comparison
C. Paolo Ciancarini

[17(4):194-206]   This paper attempts to explore the impact of greatly enhanced computing power on the alpha-beta algorithm, notorious for its high processing requirements. On a limited set of test positions, it explores, under some limitations, the question of how best to distribute the power of multiple processes. The main matters probed in tendency are the vital questions of when to split the search among processes and, once splitting has been decided upon, to which process to split.

Stress is laid on the apparent limitation of speed-up, for which a severe law of diminishing returns soon sets in under any reasonable conditions, even when the best feasible splitting strategy is utilized. It is shown, again in tendency, that fertile further exploration essentially requires architectures with intrinsically low communication and context-switching overheads. A uniform hardware/software platform NETWORK C-LINDA, is presented as essentially free of distortion under carefully stated conditions.


Solution Trees as a Basis for Game-Tree Search
Arie de Bruin, Wim Pijls and Aske Plaat

[17(4):207-218]   A game-tree algorithm is an algorithm computing the minimax value of the root of a game tree. Two well-known game-tree-search algorithms are alpha-beta and SSS*. We show that there exists a relation between these algorithms, which are commonly regarded as quite different. Many algorithms use the notion of establishing proofs that the game value lies above or below some bound. We show that this is equivalent to the construction of a solution tree. We discuss the role of solution trees and critical trees in the following algorithms: alpha-beta, PVS, SSS-2 and Proof-Number Search. A general procedure for the construction of a solution tree, based on alpha-beta and Null-Window Search, is given.




EDITORIAL


The Five Powers
I. Samuel Herschberg and H. Jaap van den Herik

[17(4):181-182]   It is difficult not to grow smug: no more than about five powers separate computer chess from its ultimate goal. The powers, of course, are powers of two and are all that is needed, even on a conservative estimate, to make the best program consistently victorious over whichever human World Champion rises to defy it.

Consistently, meaning that Kasparov was in peril at five minutes' speed, then defeated at 25 minutes and will, given those five powers, bite the dust in a twenty-four round match or any reasonable variation. What is more, the additional powers seem to come free, just for the price of patience. Consider the chippiest of all human creations and come back the next year. You will find it is nearly twice as roomy, nearly twice as fast and, incidentally, nearly twice as cheap. So, by a very coarse but lively reckoning, in about five years from now, our machines will have achieved what it takes: the ultimate goal of computer chess. It is then a mere quibble who will have won the bets: those rooting for the year 2000, or those who, in caution, have tipped for the third millennium, giving them an extra year.

Paradoxically, the nearness of victory gives rise to some despondency. At least some researchers feel that an algorithmic improvement of ten percent or so is hardly a matter of great pride when forty percent or better per annum is automatic. Others, more fundamentally, believe that the victory is specious. They see two problems unsolved by the victory and not even addressed at their deserved depth. Crudely, they are the question of how it is possible for a human being to play masterly chess at all and, even more roughly phrased, what is the degree of sound mathematical structure inherent in the game?

As to the first problem, there has been no lack of effort in trying to let a program mimic human reasoning or, more modestly, to let it mimic the outcome of that reasoning. In our view, all such efforts fall short of their goal. Some seem specifically tailored to suit a very limited number of cases, some are algorithmically unclear, while for some others the mechanics are clear enough but seem to have been revealed rather than reasoned out.

As an instance of the second problem, let it suffice to cite the well-known databases for which Ken Thompson has earned enduring fame. In spite of considerable effort, they remain as mysterious as they are infallible. True enough, for some class of cases, rational rules may be derived for the endgame in question for many cases, which, however, have many exceptions, to which exceptions yet more exceptions will be found, and so on recursively.

Again, chess being a finite game and computers fortunately being finite machines, the recursion does not stretch to infinity, but the integers involved are large enough to force us to conclude that the full complexity of simple endgames is beyond human ken.

If our analysis is anywhere near right, the nature of computer-chess research is bound to change and so is its reporting in this Journal, which hopes to continue to be a faithful mirror of the computer-chess scene. The questions treated will perhaps be less exciting to some and more abstract to all. Your Editors are not disheartened: many of our readers will find more spice in their chess-playing sugar: more mathematics for some, more cognitive science for others. Who dares doubt they are appetizing?



Created by Ernst A. Heinz and Heiner Marxen, Tue Aug 8 18:33:33 EDT 2000