ICCA Journal, Volume 18:  Number 2  (June 1995)




TABLE OF CONTENTS
Editorial:                                                                                          
    Mood Indigo (I.S. Herschberg and H.J. van den Herik) .......................................  69
Contributions:                                                                                      
    ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm (M. Buro) ............  71
    An Integrated-Bounds-and-Values (IBV) Numeric Scale for Minimax Search (D.F. Beal) .........  77
Note:                                                                                               
    A Null-Move Technique Impervious to Zugzwang (S. Plenkner) .................................  82
Review:                                                                                             
    Gasser: Harnessing Computational Resources for Efficient Exhaustive Search (I. Althoefer) ..  85
Literature Received:                                                                                
    Exploiting Symmetry on Parallel Architectures (L.B. Stiller) ...............................  87
    Temporal Difference Learning and TD-Gammon (G. Tesauro) ....................................  88
Reports:                                                                                            
    Mikhail Moiseivich Botvinnik: An Obituary (H.J. van den Herik and I.S. Herschberg) .........  90
    A Eulogy for Mikhail Moiseivich Botvinnik (M. Newborn) .....................................  91
    Marion Tinsley: An Obituary (J. Schaeffer, M. Bryant, R. Lake, P. Lu and N. Treloar) .......  93
    The 8th World Computer-Chess Championship ..................................................  93
        Report on the Tournament: A Global View (H.K. Tsang) ...................................  93
        Report on the Tournament: Round-by-Round (D.F. Beal) ...................................  94
        The Contestants' Programs Described ....................................................  97
        Results and Games (H.K. Tsang) ......................................................... 102
        The Saitek Challenge: Human-Computer Match (H.K. Tsang) ................................ 110
        Tournament Rules - Two Amendments ...................................................... 111
    Minutes of the ICCA Triennial Meeting (D.F. Beal) .......................................... 112
    The ICCA Treasurer's Report for 1994 (continued) (D.F. Beal) ............................... 113
    Report on the Computer Strategy-Game Programming Workshop (I. King) ........................ 113
    The 10th AEGON Man-Machine Tournament (B. Verbaan) ......................................... 116
    *Socrates 2.0 Beats Grandmaster Sagalchik (B.C. Kuszmaul and A.T. Sherman) ................. 124
    A Vengeful Return (O. Weiner) .............................................................. 125
    Calendar of Computer-Games Events 1995/1996 ................................................ 126
    1995 World Microcomputer-Chess Championship ................................................ 126
    Report on `Board Games in Academia' (A. de Voogt) .......................................... 127
    The Novag Award (D. Levy) .................................................................. 128
    The 1994 ICCA Journal Award (The Board of ICCA) ............................................ 129
        Christian Donninger: A Scientific Biography ............................................ 129
    The ACM Chess Challenge: World Champion Kasparov to Play IBM's Deep Blue ................... 130
    The Swedish Rating List (T. Karlsson and G. Grottling) ..................................... 131




ABSTRACTS OF SCIENTIFIC ARTICLES


ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm
Michael Buro

[18(2):71-76]   This article presents a new, game-independent selective extension of the alpha-beta algorithm. Based on the strong correlation between evaluations obtained from searches at different depths, it is shown how the result of a shallow search can be used to decide with a prescribed likelihood whether a deep search would yield a value outside the current search window. In its application to Othello, the technique is shown to be effective in investigating the relevant variations more deeply. It significantly increases the playing strength of an already strong brute-force Othello program.


An Integrated-Bounds-and-Values (IBV) Numeric Scale for Minimax Search
Don F. Beal

[18(2):77-81]   Search procedures generally discover bounds as partial results before a final value is obtained. In particular, chess programs typically store such bounds in a hash table, along with any exact results, for every position processed. These values save computing time if the position is encountered again. For chess programs, upper bounds, lower bounds or exact values may occur. This paper shows how upper bounds, lower bounds and exact values can conveniently be represented using a single numeric scale, which enables program code to be slightly simpler, and avoids the necessity of a separate data item to distinguish bounds from exact values.


A Null-Move Technique Impervious to Zugzwang
Stefan Plenkner

[18(2):82-84]   In chess programs based on the alpha-beta algorithm, various techniques exist to interrupt and modify the blind working of brute-force searches. These can be classified as search extensions (e.g., check extensions, singular extensions and others) or as forward pruning. One very popular heuristic for forward pruning consists in the idea of making a null move (Beal, 1989). The idea of a null move has been adequately set out by Goetsch and Campbell (1990) and by Donninger (1993). Null moves assume that we are given a position with COLOUR to move while COLOUR is not in check. COLOUR's opponent now makes one more move, which will attempt to let the position, as seen by COLOUR, deteriorate. If the value returned should be greater or equal to beta (as seen by COLOUR), an action is called for: beta can be raised or a beta-cutoff can be applied.

The above rests on the assumption that COLOUR has a move available with a value at least equal to that of the null move. This assumption always holds except in Zugzwang positions, i.e., those in which COLOUR only has moves worsening his position. While these Zugzwang positions are rare in an absolute sense, they are relatively frequent in endgame positions. Since one's opponent gains an advantage in null moves by COLOUR yielding a tempo and, in effect, transferring his tempo to his opponent, it follows that depth-of-search in a null-move search is reduced by some amount, say TEMPO. Should the null-move search lead to pruning, the pruning of the search tree is immense; should it fail to prune, the additional effort is limited due to TEMPO reducing the depth of search. The above argument, it is often claimed, tends to exclude null moves from endgame positions, since the risk of finding oneself in a Zugzwang position and the consequent false evaluation would be unacceptably large.




EDITORIAL


Mood Indigo
I. Samuel Herschberg and H. Jaap van den Herik

[18(2):69-70]   Between the deepest of blues, indigo if ever there was, and the reddest of human blood, with all its connotations, the gap of stochastics hovers. Against all odds, as calculated by at least one of the contestants, contemplative DEEP BLUE - the obvious favourite - missed a match which it seemed predestined to win. In simple terms, it is legitimate to ask how this could happen. In our view - but we apologize for 20/20 hindsight - the reason is based on two misreckonings: too little knowledge in the chess programs and too little chess knowledge in the programmers.

To take the last point first: it is fatal, as we see it, to ignore the vast experience and the deep (though unquantifiable) expertise of grandmasters. In chess, such deliberate ignorance leads one into peril; therefore, it does so in computer chess. In our opinion, an expert chess-player, now necessarily at grandmaster level, should be incorporated into any programming team if their program is to be competitive. The pursuit of that elusive knowledge is essential now, and will become more essential as time goes by. Capturing its volatile essence is crucial if computer chess is to progress to its ultimate aim.

To tackle the first point raised, we think that there is an even greater obstacle in the programmers' being almost exclusively inclined to search. In itself, this tendency has proved to be laudable: all the world marvels when a program, rightly or wrongly, announces an edge after searching 19 ply or so. Yet this is a triumph of brute force, clobbering its adversary. Still, the ever-open question remains: could not a little chess intelligence have prevented the useless deployment of so many processes vainly investigating so many nodes to no good purpose?

The Hong Kong tournament seems to yield a ready answer: a little brain will easily match a great deal of brawn. All so-called experts, not excluding your Editors, assuming a knowledge they did not possess, were unanimous in predicting a victory for DEEP BLUE as a prototype, with some pundits even stating that it was nine to one: long odds indeed for DEEP BLUE. Their favourite sadly gave them the blues, transposing their hopeful blue mood into a sad Mood Indigo.

As happens all too often when true pundits are elevated to the false rank of gurus, their predictions came apart. It was not the mighty speed of DEEP BLUE that gained the palm. Rather, FRITZ, a professional programmer's labour of love supported by adequate though modest means, gained a victory in this contest. This must have been disappointing to DEEP BLUE's authors, who did no better than a meager third. To add to their humiliation, DEEP BLUE was also outdone by a university, often snortingly discredited by self-styled practitioners and by commercially-motivated winners.

FRITZ3, who defeated Kasparov in 1994 at speed chess, decided that henceforth the 3 would be silent. FRITZ, achieving the title of World Champion and victorious over STARSOCRATES and DEEP BLUE PROTOTYPE, can well stand as paradigmatic for the incorporation of chess knowledge, in which his opponents notoriously failed. Commendations also are due to STARSOCRATES, rooted in MIT, a notable hotbed of computer programming. In spite of the alleged weakness of universities at propagating their brainchildren, MIT gave a splendid account of its capabilities by the quaintly-named *SOCRATES.

The contestants sliding into the first three slots could not have been of more diverse origins. Inspired academics were pitched against commercially-endowed amateurs and those competed with sky-is-the-limit industrial developers. As it turned out, the contest, however fascinating to all of us, failed to give unique, universal results. A little knowledge seems essential, otherwise the winner with modest hardware at his disposal could never have obtained his badge of honour.

Yet there still is a tendency, we believe, for search to be overemphasized in the race between knowledge and search. Or is it not? We hardly dare predict how the balance will shift when DEEP BLUE, contending as a cripple in Hong Kong, will gather up its feet at three million nodes a second when playing Kasparov. One conclusion seems as secure as any can be in a stochastic field where all parameters change rapidly: as an individual achievement, Frans Morsch's program stands out for a proper balance, it would appear, between brawn and brain, as befits an emissary from a small and low country, The Netherlands.



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