ICCA Journal

Vol. 22, No. 3 - September 1999

Table of Contents

Table of Contents 121
Many Changes (H.J. van den Herik) 121
Adaptive Null-Move Pruning (E.A. Heinz) 123
Efficient Approximation of Backgammon Race Equities (M. Buro) 133
Review: 143
A Transference of Bones (D. Hartmann) 143
Information for Contributors 145
News, Information, Tournaments, and Reports: 146
Thirteen Years On (D.N.L. Levy) 146
Millennium’s End (T.A. Marsland) 147
The 9th World Computer-Chess Championship: 149
The Tournament (M. Feist) 149
The Search-Engine Features of the Programs (D.F. Beal) 160
The Man-Machine Contest (M. Feist) 165
Report on the Advances in Computer Chess 9 Conference (Y. Björnsson) 167
Minutes of the ICCA Triennial Meeting (D.F. Beal) 171
The Advanced Chess Match between Anand and Karpov (F. Friedel) 172
Report on the Machine-Learning in Game-Playing Workshop (J. Fürnkranz and M. Kubat) 178
Report on the 9th CSA World Computer-Shogi Championship (M. Sakuta and H. Iida) 180
Report on The First International Shogi Forum (M. Sakuta and H. Iida) 183
The ChessBase Best-Publication Award (The Board of ICCA) 185
The ICCA Journal Award 1998 (The Board of ICCA) 186
Ernst Heinz: A Scientific Biography 186
Calendar of Computer-Games Events in 1999 and 2000 186
The Swedish Rating List (T. Karlsson) 187
Correspondence: 188
The “Brains of Earth” Challenge (J. Nunn and F. Friedel) 188
Correction on Dap Hartmann’s Review (I. Althöfer) 190
Reaction of the Reviewer (D. Hartmann) 191
How the Journal Reaches You 192

 

MANY CHANGES

This issue of the ICCA Journal is unable to record properly all the changes the computer-chess world faced in the summer months of 1999. Of course, we did our utmost, and so we are able to offer our readers a long list of changes adequately reported in the pages to follow. Below we briefly deal with them in an order which gives priority to human beings above scientific findings.

First, the Editors would like to congratulate Stefan Meyer-Kahlen on winning the title World Champion among computer-chess programs for the period 1999 – 2002. His program SHREDDER achieved a deserved first place at the WCCC’99 in Paderborn, after an exciting play-off against FERRET (Bruce Moreland). SHREDDER took over the title from FRITZ (Frans Morsch, Cock de Gorter, and Mathias Feist).

Second, after thirteen years of services our President Tony Marsland has stepped down. The overview of the activities and tournaments under his Presidentship is impressive. We thank him for his enthusiasm, his scientific contributions, and his guidance. Much wisdom was necessary to keep the ICCA going on the right track.

Third, the conference Advances in Computer Chess 9 was an overwhelming success. This series of conferences has attracted the attention of game-playing researchers from all over the world. The result is that those researchers submitted papers on many games different from chess. As a consequence the idea of changing the name from Advances in Computer Chess to Advances in Computer Games has been almost generally welcomed.

Fourth, the developments mentioned above had not escaped the attention of the new ICCA Board. Therefore, they suggested in the Triennial Meeting to broaden the scope of the ICCA Journal officially by encouraging the Editor to solicit contributions which are not chess-specific, but games-oriented. The result of this change in policy has already been incorporated in this issue. (See also below.)

Fifth, the ChessBase organisation has expressed the willingness to cooperate more closely with the ICCA. In addition to their articles (see the article by Frederic Friedel and also the Correspondence section), they have contributed a CD ROM for our readership containing opinions bridging the gap between human Grandmasters and top programs.

Sixth, the ChessBase organisation has offered to continue the Mephisto/Novag Award. For 1999 we will again have an Award, of course now called the ChessBase Best-Publication Award, which enables the ICCA to distinguish a researcher or a group of researchers for their excellence.

Seventh, the ICCA Board has been enlarged by the position of an "active programmers' representative". This position is now filled by Martin Zentner. The ICCA expects many ideas and activities from him, which will be communicated to our readers in the Journal.

Eighth, the subscription fee has been settled for international use as US $ 40 (as was) and Euro 40. (See the minutes of the Triennial Meeting.)

Ninth, the ICCA Board has decided (September 11, 1999) to combine ideas of the uniform-platform tournament and the annual World Microcomputer Chess Championship (WMCC), by organising a World PC Computer-Chess Championship 2000 in London on a uniform platform. For details, see the Presidential address.

Tenth, the Editorial Board is proud to have been able to report since 1983 a scientific breakthrough in each issue; sometimes a small one, at other times a larger one. The last two years we were fortunate to publish many outstanding contributions by Ernst Heinz. Again, his Adaptive Null-Move Pruning enhances our understanding of the intricacies of game-tree search. No change in his series, but an increase in our knowledge.

After the many changes mentioned above, your Editor feels he is still running to keep up with the many changes in the computer-games field. Let us hope that the 21st century will continue the current slope.

Jaap van den Herik


ADAPTIVE NULL-MOVE PRUNING

E.A. Heinz1

Karlsruhe, F.R. Germany

ABSTRACT


General wisdom deems strong computer-chess programs to be "brute-force searchers" that explore game trees as exhaustively as possible within the given time limits. We review the results of the latest World Computer-Chess Championships and show how grossly wrong this notion actually is. The typical brute-force searchers lost their dominance of the field around 1990 when the null move became popular in microcomputer practice. Today, nearly all world-class chess programs apply various selective forward-pruning schemes with overwhelming success.

To this end, we extend standard null-move pruning by a variable depth reduction and introduce what we call adaptive null-move pruning. Quantitative experiments with our chess program DARKTHOUGHT show that adaptive null-move pruning adds a new member to the collection of successful forward-pruning techniques in computer chess. It preserves the tactical strength of DARKTHOUGHT while reducing its search effort by 10 to 30 percent on average in comparison with standard null-move pruning at search depths of 8 to 12 plies. Moreover, adaptive null-move pruning is easy to implement and scales nicely with progressing search depth.


1 Institute for Program Structures and Data Organization (IPD), School of Computer Science, University of Karlsruhe, P.O. Box 6980, D-76128 Karlsruhe, F.R. Germany. Email: heinze@ira.uka.de.
WWW= http://wwwipd.ira.uka.de/~heinze/ http://wwwipd.ira.uka.de/Tichy/DarkThought/

 EFFICIENT APPROXIMATION
OF BACKGAMMON RACE EQUITIES

M. Buro1

Princeton, USA

ABSTRACT


This article presents efficient equity approximations for backgammon races based on statistical analyses. In conjunction with a 1-ply search the constructed evaluation functions allow a program to play short races almost perfectly with regard to checker-play as well as doubling cube handling. Moreover, the evaluation can naturally be extended to long races without losing much accuracy.


This is a revised version of the paper delivered under the same title on June 16, 1999 on the 9th Conference on Advances in Computer Chess, in Paderborn, Germany. It will be also published in the Proceedings of that Conference.

1 NEC Research Institute, 4 Independence Way, Princeton NJ 08540, USA. Email: mic@research.nj.nec.com


REVIEW

A TRANSFERENCE OF BONES

The Nature of Minimax Search
Ph.D. thesis Don Beal

SIKS Dissertation Series No. 99-3 1999,
150 pp., Dfl. 25,-, Euro 10,
ISBN 90 62 16 6348

Reviewed by Dap Hartmann1

"The average Ph.D. thesis is nothing but a transference of bones 
from one graveyard to another." 
J. Frank Dobie (1888–1964)


Over the past two decades, Don Beal has written more than a dozen papers on computer chess, which were published in Artificial Intelligence, the ICCA Journal, and in the Advances in Computer Chess Series. He edited three volumes of Advances in Computer Chess and has been secretary/treasurer of the ICCA for the past seven years. Between the late 1970s and mid 1980s, Beal’s Chess Program (BCP) played in a number of major computer-chess tournaments. Usually running on modest hardware, it generally finished somewhere in the middle of the pack. Since 1975, he is a lecturer at Queen Mary College (now Queen Mary and Westfield College) in London, where he got tenure in 1977, and became senior lecturer in 1983. His main research is in artificial intelligence, but he teaches courses ranging from neural networks to VLSI circuit design. Until a few months ago, Don Beal did not have a Ph.D.

"You have so many published papers and scientific credentials — you should make a Ph.D. from your results", Jaap van den Herik told Don Beal two years ago. A very appropriate invitation, I think, to put a crown on the great contributions he has made to computer-chess research over the years. Being appointed a university lectureship with just a Master degree, Beal probably never had the time or the incentive to work on a Ph.D. thesis — something that has become a standard requirement for such a position nowadays. Beal accepted the invitation and came to Maastricht to rework some of his best papers into a thesis. On June 11, he successfully defended his thesis titled The Nature of Minimax Search, and was awarded his long awaited doctorate, from the Universiteit Maastricht.

Let there be no misunderstanding: this is not an honorary doctorate, the likes of which are handed out all too frequently to world leaders or captains of industry. Personally, I think it is a disgrace to award titles of scientific merit to people such as Bill Clinton, Nelson Mandela or Bill Gates. What kind of message are we sending to aspiring young scientists when Bill Gates, who dropped out of Harvard but went on to become the richest man on the planet, receives his doctorate without even having achieved a Master degree? If Bill Clinton deserves a degree, it should come from Larry Flint, not from the dean of Princeton University. When the Universiteit Nyenrode awarded an honorary doctorate to Dutch grocery mogul Albert Heijn, two Utrecht professors (André Klukhuhn and the late Piet Vroon) returned their Ph.D. degrees in protest. Nyenrode has also awarded honorary doctorates to Bill Gates (for giving the world Windows and the General Protection Fault), and to Nelson Mandela (for being in prison for 30 years). Ph.D.s are intended to accolade scientific accomplishment, and should not be handed out like evaluation copies of Windows 2000 or OBEs.

The Nature of Minimax Search must be appreciated in the spirit in which it was conceived. The original material that Beal reworked into this thesis dates back quite a few years. The majority of this work was originally published between 1980 and 1986. Only Chapter 5, An Integrated-Bounds-and-Values (IBV) Numeric Scale for Minimax Search, is recent (1995), while Chapter 10, A Generalized Quiescence Search Algorithm, is from 1990. As a consequence, many of the chapters are somewhat dated. Chapter 8, Minimax and Retrograde Minimax Using Patterns, takes up almost a quarter of the entire thesis, and presents a case study for handling Minimax with patterns instead of individual positions. The case study is the KPK endgame, and in an Appendix there is even a FORTRAN program that determines for any given KPK position whether it is won or drawn. A very nice accomplishment in 1980, and the reader should keep that in mind instead of dismissing it as trivial. For me, the highlight of the thesis is Chapter 10, in which the concept of the null move is introduced. It is the fourth leg of the table where upon (re)lies game-tree searching: minimax, alpha-beta, transposition table, and null move.

Despite my true conviction that the material presented in this thesis fully deserves the Ph.D. degree, I do have a few points of criticism. Basically, the thesis consists of 9 slightly edited papers that were previously published, supplemented with a brief introduction and a chapter of conclusions, which is a rewritten version of the introduction. Of course, all material is now collected in a single volume, uniformly typeset and all. However, adding a brief introductory paragraph to each paper appears to be most of the editing involved in turning it into a chapter of this thesis. The thesis would certainly have benefited from more rigorous proofreading, as there are many typographical errors, an occasional sentence missing, and at least one incorrect chess diagram.

In a perfect world, I imagine that The Nature of Minimax Search would have been a monograph on the minimax algorithm and its refinements. Don Beal has contributed enough original material to the field to justify that such a monograph, together with a list of his original papers, passes for his Ph.D. thesis. It would undoubtedly have been a valuable addition to the computer-chess literature, and a pleasure to read, as Beal writes with great clarity. The major disadvantage of the present shape of his thesis, is that each of the chapters is an entity, and thus there is no logical transition from one chapter to the next. There are some attempts (especially in Chapter 9), to refer to other chapters in the thesis, rather than to the original papers. However, the work as a whole lacks continuity, a ‘leading thread’ if you will. But, at the end of the day, Beal’s 4th proposition explains it all: “We are limited not by what we can see, but by what we have time to see”. (In The Netherlands, a Ph.D. candidate must also provide a list of propositions that he/she is able to defend along with the thesis itself).

If the Mephisto Award had been instituted 20 years ago, I am convinced that Don Beal would have received it at least once. (He was, of course, also recipient of the 1988-1989 Mephisto Award for his Editorship of ACC5.) As it is, he has earned himself a well-deserved doctorate, and I am pleased to offer him my sincere congratulations!


1 Radioastronomisches Institut, Universität Bonn, Auf dem Hügel 71, 53121 Bonn, Germany. Email: dap@astro.uni-bonn.de