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
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.
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.