ICCA Journal, Volume 18:  Number 1  (March 1995)

TABLE OF CONTENTS

Editorial:                                                                                          
    Ply the Random (I.S. Herschberg and H.J. van den Herik) ....................................   1
Contributions:                                                                                      
    The StarTech Massively-Parallel Chess Program (B.C. Kuszmaul) ..............................   3
    A Partial Analysis of Minimaxing Game Trees with Random Leaf Values (M. Levene                  
        and T. Fenner) .........................................................................  20
Review:                                                                                             
    M. Buro: Techniques for the Evaluation of Game Positions Using Examples (I. Althoefer) .....  34
Literature Received:                                                                                
    Game-Programming Workshop in Japan '94 (H. Matsubara) ......................................  35
    Time-Efficient State-Space Search (A. Reinefeld and P. Ridinger) ...........................  35
Reports:                                                                                            
    Tributes to Tony Scherzer (K. Thompson, J. Schaeffer) ......................................  37
    The 1994 ICCA Best-Annotation Award (D. Levy) ..............................................  38
    Fritz 3 and the Grandmasters: Report on the 3rd Godesberg GM Tournament (A. Schulz) ........  45
    The 2nd Spanish Computer-Chess Championship (T. Canela and J. Pares) .......................  49
    Tournament Rules of the 8th World Computer-Chess Championship (D. Levy) ....................  52
    The Participants of the 8th World Computer-Chess Championship (D. Levy, T. Marsland,            
        and M. Newborn) ........................................................................  53
    Computer Strategy-Game Programming Workshop (I. King) ......................................  55
    The 10th AEGON Computer-Chess Tournament (C. de Gorter) ....................................  57
    Calendar of Computer-Games Events 1995 .....................................................  59
    The Swedish Rating List (T. Karlsson and G. Grottling) .....................................  60
    ICCA: The Treasurer's Report (D. Beal) .....................................................  61
    ICCA Board Nominations (T. Marsland) .......................................................  63
    ICCA Constitution and By-laws (The Board of the ICCA) ......................................  64

ABSTRACTS OF SCIENTIFIC ARTICLES

The StarTech Massively-Parallel Chess Program

Bradley C. Kuszmaul

[18(1):3-19]   The STARTECH massively-parallel chess program, running on a 512-processor Connection Machine CM-5 supercomputer, tied for third place at the 1993 ACM International Computer-Chess Championship. Testing the program informally, its rating was over 2400 USCF points. STARTECH employs the Jamboree search algorithm, a natural extension of Pearl's Scout search algorithm, to find parallelism in game-tree searches. STARTECH's work-stealing scheduler distributes the work specified by the search algorithm across the processors of the CM-5. The program uses one global transposition table shared among the processors.

Two performance measures help in understanding the program's performance: the work performed, W, and the critical-path length, C. The Jamboree search algorithm seems to perform some 2 to 3 times more work than the best serial version. The critical-path length, under tournament conditions, is less than 0.1 percent of the work, yielding an average parallelism of over 1000. The STARTECH scheduler achieves actual performance of approximately T = 1.02*W/P + 1.5*C on P processors. The critical-path length and work performed can thus be used to tune performance.

A Partial Analysis of Minimaxing Game Trees with Random Leaf Values

Mark Levene and Trevor Fenner

[18(1):20-33]   Random minimaxing, introduced by Beal and Smith, is the process of using a random static evaluation function for scoring the leaf nodes of a full-width game tree and then computing the best move using the standard minimax procedure. Their experiments using random minimaxing in chess showed that the strength of play increases with the depth of the lookahead. We investigate random minimaxing combinatorially in order to obtain a theoretical justification for Beal and Smith's experiments. In particular, we show that, with respect to chess, random minimaxing with the depth of lookahead equal to two is ``stronger'' than the same with its depth equal to unity, under the assumption that a move by the first player is better the more it restricts the second player's choice of moves (i.e., his mobility). We conjecture that these results can be generalized for depths of lookahead greater than two.

EDITORIAL

Ply the Random

I. Samuel Herschberg and H. Jaap van den Herik

[18(1):1-2]   The diversity of computer chess is amazing, even to its practitioners. So is the breakneck speed of its evolution. The hot pursuits of yesterday are now questioned, challenged, denied or even derided. Take the value of value, in plainer speech: the evaluation function. In all our yesterdays, it reigned supreme. The late lamented Tony Scherzer devoted a large part of his energies to building hardware computing it efficiently, as did Hans Berliner. Was not our world united in believing that its speed, its quality, its universality, even its auto-adaptability were essential as the game developed from early to middle to end? Were not we all convinced that evaluation was central to the game?

Hardware constructors concurred in this belief no less than mind-over-matter purists, such as Botvinnik, who maintained that only a Botvinnik-like evaluation function would be the magic key letting those computers enter the human haven.

The perusal of one issue of this Journal is enough to upset this long-cherished belief. The diversity of our discipline has shown yet another facet, perhaps a random facet on a 20-sided die. Not quite two years ago, Don Beal threw a stone into the quiet pond in which the true believers hid their highly secret proprietary functions. He proposed that one would play better than random moves by solemnly minimaxing over nonsense, over nodes which had a random-number generator for their setter of values!

Even more shockingly, he argued that the moves chosen became progressively superior as one searched more deeply over these random values. He suggested that one more ply of unreason gave just a little bit of edge over one fewer ply of nonsense. In short, deeper searches on random trees held an improvement, as shown by experiment.

When these heretical ideas were first aired, unbelief must have been universal and everybody's intuition told them to shrug off this idea as one more academic extravaganza. We should not have rejected his ideas out of hand, remembering such maxims as ``any plan is better than no plan at all''. Perhaps we should also have looked back in wonder at twenty years or more spent in refining evaluation functions without spectacular, convincing progress, which should have given us food for thought.

In this issue, Beal and Smith's notion is being given substance by a formula-ridden, symbol-strewn essay by Levene and Fenner, who use a sophisticated mathematical apparatus to prove that Beal was right: two ply of random is better than one! With the caution inborn to mathematicians, they venture to conjecture that more plies are always better, even when the node values are literally dicey. Heavy maths in this issue, but you have been warned: there would be when occasion warranted.

Perhaps this finding should temper the admiration we must feel for Kuszmaul, who has gone a long way towards solving one besetting problem in computer chess: how do I distribute the work over many machines? When many is 512, the name of the engine is Connection and the name of the game is Chess, Kuszmaul succeeds in persuading a large fraction of them to work simultaneously on ... computing the evaluating function. Hats off for achieving the feat, though wrinkles of doubt whether all those machines, pushing away on a 1024-pedalled giant tandem bicycle, were spending their energy wisely and well when they were just computing evaluations. Would a parallel random generator have done as well in a road test? We doubt it, but Beal is just disturbing enough to make us ponder.

More conventionally, an ICCA communication in this issue reminds us, not without humour, that FIDE is as it ever was: no human blood, no FIDE titles, and that seems as final as anything in our diverse world. Still, as we report in this issue, Godesberg was the venue of yet another evaluation function, an important meeting attempting to assess FRITZ 3. That machine was tolerated there, a mere Pentium among more Grandmasters than ever before in a regular tournament. FRITZ 3, as though relieved of the shackles of competition, companionably played chess for chess' sake, pleasing itself and mostly pleasing its opponents. They were even somewhat respectful of his 90 million instructions per second and would have agreed with what FRITZ 3 himself, had he been human and given to self-evaluation, would have thought: ``MegaHertz are not Megahurts''.