ICGA Journal

Vol. 23, No. 1 - March 2000

Table of Contents

Table of Contents1
A Breakthrough (H.J. van den Herik)1
Thoughts on RoShamBo (D. Billings) abstract 3
Strategies for Constrained Optimisation (G. McC. Haworth) abstract 9
AEL Pruning (E.A. Heinz)21
Notes:33
IOCAINE POWDER (D. Egnor) intro 33
The Longest: KRNKNN in 262 (K. Thompson) 35

Review:

37
The Importance of Being Scalable (D. Hartmann) 37
Literature Published Elsewhere39
Information for Contributors41
News, Information, Tournaments, and Reports:42
The First International RoShamBo Programming Competition (D. Billings) 42
Report on The Second Open Computer-Amazons Championship (H. Iida and M. Müller) 51
Report on the Sixth Open Spanish Computer-Chess Championship (E. Jimenez) 55
A Special Session on Heuristic Search and Computer Game Playing (K. Chen) 56
The 1999 Herschberg Best-Annotation Award (The Board of ICCA) 56
Calendar of Computer-Games Events in 2000-2002 57
Call for Papers: The Second International Conference on Computers and Games 2000 (Hamamatsu) 58
The Computer Olympiad 2000 (London) 59
The PC-based World Chess Championship 2000 (London) 59
Tablebase of Contents, Continued (J. Uiterwijk) 60
The Swedish Rating List (T. Karlsson) 61
The ICCA Treasurer’s Report for 1999 (D.F. Beal) 62
Correspondence:63
No Vilification (G.D. Petty)63
Make Sure the ICGA Journal Reaches You64

 

A BREAKTHROUGH


This is the first issue of the new ICGA Journal, which can be seen as the immediate successor of the ICCA Journal. Although the ISSN number has changed into 1389–6911, we are continuing to count Volumes as we did in 1983 when the ICCA Journal succeeded the ICCA Newsletter. This is therefore Volume 23, with a focus on games and no longer on chess only. The contents of the current issue clearly indicate the new publication policy by giving ample attention to the game of RoShamBo (better known as Rock Paper Scissors) as well as looking at Amazons. The main emphasis is still on chess, but we do have submissions and promises of submissions on Bridge, Hex, Mancala, Renju, Shogi, Sokoban, and Solving Crosswords. So we see a bright future. Besides, chess could be considered as the Drosophila of Artificial Intelligence? No wonder then, that it still plays an important role in the world of games and its surrounding society.

As a case in point we only need to look at how the Royal Dutch Chess Federation (KNSB) has taken the lead in the digitized world of human players and artificial agents. Recently (March 2000), the Board of the KNSB has decided to invite a computer participant to the National Dutch Chess Championship 2000.

A wild card became available after Grandmaster Timman withdrew in favour of a tournament in Bali. Grandmaster Sosonko who was invited to replace Timman also declined, but he suggested the Board give the wild card to a computer program. After much internal deliberation the Board decided to investigate this advice more seriously. They took soundings and started negotiations with the players, the selection committee, the rules committee, the computer-chess world and their sponsors of that point in time.

Fortunately, the main sponsor of the tournament was the Computer Training Institute "The Broekhuis Group". They applauded the KNSB decision as did the other sponsor "The Rotterdam Top Sport Foundation". However, there were many obstacles, ranging from the rules, via the players' attitude towards computer participation, to their willingness to play. The final hurdle in the players' camp disappeared after the KNSB promised to raise the prize money by Dfl 70,000 (almost double) and to prohibit the computer participant winning any money – although it may win the tournament. Thus it was announced simultaneously that the winner of the tournament (man or machine) should become the Chess Champion of the Netherlands for the year 2000.

The program FRITZ, brainchild of the Dutchman, Frans Morsch, was a logical choice for participation in the tournament. The additional prize money was raised by several sponsors1, all of them convinced by the fact that the role of computers in society will increase. They all believed that computer participation in a tournament with a (human) title to win is only a first step towards a world where human beings and computer agents will act on equal footing. As a tribute to Stockman (1979)2 and to the first three sponsors, FRITZ will play under the name FRITZ-SSS*.

The tournament starts on May 6, but the month of April will be used by opinion leaders voicing their pros and cons. In their chess columns the International Masters, Hans Ree and Gert Ligterink, have declared the Chess Federation as unwise. In contrast, the IGMs, Piket, Van Wely and Van der Wiel, have stated that they will play. The only opposition so far comes from IGM Paul van der Sterren, who is not against computers playing in tournaments (remember the WOCIT in the 1980s), but does feel that a computer should not be eligible for a national title.

Going through the pages of this Journal, i.e., its predecessor the ICCA Journal, I recall that we have often challenged World Champion Garry Kasparov editorially to play a computer match with his title at stake. So far, Kasparov has avoided such a contest but he has never argued that the proposed match should be an intrusion on the highly relevant question: who is the strongest player on earth?

When questioned whether a computer program in the future should be allowed to play in national team championships, Grandmaster Sosonko replied as far back as in 1980: "No, no, no, Van der Sterren, Donner and Ligterink have no chances at all; the beast played very well this year. He has earned the sixth position. 'The beast on the sixth board' – should be the decision of the selection committee. I believe that will happen. But then, in my opinion, computers have to be a member of the selection committee too. These times will also come".

Obviously, the world of chess is in a transition period. The relationship between humans and computers will be resolved in the near future, but the problems mentioned above only prognosticate what will happen in this century in other areas of our digitized world.

Finally, I would like to stress that the ICGA Journal too is in a transition period. The name of the Journal has been changed but its founding organisation is still the ICCA. Changing this name – as is intended – requires the approval of a Triennial Meeting. Such a meeting will take place in 2002. Until then we will continue to distinguish between the ICCA and the ICGA Journal, two names, one ambition: to strengthen ties and promote cooperation between computer-games researchers.

Jaap van den Herik


1 The additional sponsors are: SGI, SARA, STORAGE TEK, ChessBase, Lost Boys, International Institute of Infonomics, and Bolesian.
2 Stockman G.C. (1979). [SSS*:] A minimax algorithm better than alpha-beta? Artificial Intelligence, Vol.12, No. 2, pp.179-196.


THOUGHTS ON ROSHAMBO

Darse Billings1

Edmonton, Alberta

ABSTRACT


This article features observations and technical details from the First International RoShamBo Programming Competition. In this contest, the participating programs competed against each other and a standard set of “dummy bots” in the game of RoShamBo (also known as Rock-Paper-Scissors). The discussion covers certain aspects of game strategy, some of the general techniques used for pattern detection, and the specific algorithms used for the exploitable dummy bots.

Using perceived patterns and tendencies to gain an advantage is an easily understood form of opponent modelling. For some games, like poker and RoShamBo, this is an ability which will probably be essential for computer programs to play at a world-class level.


1 Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2H1, Canada. Email: darse@cs.ualberta.ca.

STRATEGIES FOR CONSTRAINED OPTIMISATION

G. McC. Haworth1

Reading, England

ABSTRACT

The latest 6-man endgame results confirm that there are many deep forced mates beyond the 50-move rule. Players with potential wins near this limit naturally want to avoid a claim for a draw: optimal play to current metrics does not guarantee feasible wins or maximise the chances of winning against fallible opposition. A new metric and further strategies are defined which support players’ aspirations and improve their prospects of securing wins in the context of a k-move rule.


1 ICL, Sutton’s Park Avenue, Sutton’s Park, Reading, Berkshire, RG6 1AZ, UK: guy.haworth@icl.com.

NOTES

IOCAINE POWDER

Dan Egnor1

Seattle, USA


IOCAINE POWDER is a program that plays RoShamBo. It is a heuristically designed compilation of strategies and meta-strategies. The program won the First International RoShamBo Programming Competition (see Billings, 2000). I attempt here to explain how it works. You may use its source code freely; you are only asked to give me credit for any derived works.


1 2461 E. Madison St., Seattle, WA 98112, USA. Email: egnor-137.120.180.243@ofb.net. www: http://ofb.net/~egnor/iocaine.html.

REVIEW

THE IMPORTANCE OF BEING SCALABLE

Scalable Search in Computer Chess
Algorithmic Enhancements and Experiments at High Search Depths

by Ernst A. Heinz
Vieweg Verlag
ISBN 3-528-05732-7
US$ 50.95; DM 98; öS 714; sFR 89

Reviewed by Dap Hartmann1 


"One of the nice things about computer chess is the fact that the to-do list of interesting
ideas seems to grow steadily despite all the improvements made since the last time you checked."

Appendix A.6: Future Work

Ernst Heinz is one of the most productive computer-chess researchers of the past several years. After earning his Ph.D. (summa cumma laude) from the University of Karlsruhe in July 1999, he joined the MIT Laboratory for Computer Science as a Postdoctoral Fellow. The results of his extensive experiments on the scalability and performance of game-tree searching have been laid down in this excellent book. Most of the material has already been published in the ICCA Journal, or presented at the ACC 9 conference. But the text has been expanded, and two chapters and several appendices have been added. Heinz's master-strength chess program DARKTHOUGHT (shared 2nd place in the 1999 WMCC) served as the guinea pig for the implementation and testing of a wide variety of ideas, yielding empirical evidence for the practical usefulness of the various techniques.

The book consists of three parts, preceded by a 'Computer-Chess Primer' (Chapter 0), and supplemented by four appendices. Part I 'Forward Pruning without Tears' describes various techniques to (forwardly) prune the game tree with no concessions to the tactical strength of the program. In Chapter 1 (Adaptive Null-Move Pruning), the depth reduction used in the application of the null-move algorithm is made variable instead of fixed, combining the safety of the more traditional 2-ply depth reduction with the advantages of the reduced search effort resulting from a 3-ply depth reduction. Extensive experiments using a large suite (2180 positions) of widely-used test positions yielded a reduction in the search effort of 10 to 30%, while remaining tactically sound. Chapter 2 (Extended Futility Pruning) describes a (static) domain-dependent forward-pruning technique which (in combination with limited razoring) reduces DARKTHOUGHT’s search trees by 10 to 30% as compared with normal futility pruning, while maintaining the tactical strength of the program. Again, the aforementioned test suite provided the empirical evidence for this conclusion. One of the strong points of the book, is the emphasis on the scalability of the various techniques. The results of experiments carried out at increasing search depths provide the basis for the analysis of the behaviour of each technique with search depth (or size of the game tree). It is found that Extended Futility Pruning scales almost linearly with search depth. The combination of Adaptive Null-Move Pruning, Extended Futility Pruning, and Limited Razoring (referred to as AEL Pruning) is the subject of Chapter 3. The superiority of this combined pruning technique is empirically verified by the test suite experiment, as well as by 580 self-play games and games played under tournament time-control conditions against strong commercial chess programs. The results indicate a 20% (at depth 8 ply) to 50% (at 12 ply) overall reduction of the search effort while maintaining the tactical strength of the program.

Part II (Integration of Perfect Knowledge) deals with game-tree nodes in which the exact game-theoretical value is known. Chapter 4 (Efficient Interior-Node Recognition) addresses the all-important issue of how such nodes can be recognized and evaluated. Using an efficient so-called Material Signature, the program is able to quickly classify positions and recognize material distributions for which the game-theoretical value is known. Not only is the program capable of evaluating drawn and won/lost interior nodes, it can also deal with ‘at least/most drawn’ positions. In Chapter 5 (Index Schemes of Endgame Databases) and Chapter 6 (Knowledgeable Endgame Databases), an efficient endgame database encoding is developed to enable the recognition of game-theoretical values in real-time. Using this encoding, all endgames up to 4 pieces can be squeezed into less than 15 Mb of memory space, allowing DARKTHOUGHT to utilize this knowledge in the game tree without any loss of speed.

Part III (Search Behaviour at Increasing Depths), focuses on the scalability of the techniques developed and discussed earlier in the book. Chapter 7 (DARKTHOUGHT Goes Deep) repeats an experiment by Hyatt and Newborn in which 347 positions from real games are searched to fixed depths. Heinz reaches the same surprising observation that the aforementioned authors made, namely that even at high search depths (11 to 14 ply), new best moves occur in one out of every six searches. Even more astonishingly, it was found that up to half of all new best moves had never been deemed 'best move' earlier in the iterative search. Chapter 8 (Modeling the "Go Deep" Behaviour) elaborates on the results of the previous chapter, and develops a model to predict the behaviour at even higher search depths. One final data point is added by the results from 16-ply searches in the test suite positions. It confirms the earlier conclusion (based on searches up to 14 ply deep) that the ‘Best Change Rate’ at high search depths remains fairly constant (at about 15%). Chapter 9 (Self-Play Experiments Revisited) explores the treacherous territory of self-play experiments for various computer games (Chess, Checkers, Othello). Heinz carefully analyzed past self-play experiments, including the famous fixed-depth-searching Belle experiments. His conclusion is that there is no empirical evidence that increased search depth (in computer self-play) leads to diminishing returns. He conjectures that at least 1000 games per program version are necessary to quantify this widely expected, although yet unproven phenomenon. The appendices contain information on Heinz’s chess program DARKTHOUGHT: How DARKTHOUGHT Plays Chess; Tournament History of DARKTHOUGHT; DARKTHOUGHT and Test Suites; DARKTHOUGHT at Test Games.

I warmly recommend this book to any serious computer-chess enthusiast. The style of writing is very clear, and hardly any programming experience is required to enjoy most of this work. Reminiscent of Jonathan Schaeffer's seminal Ph.D. thesis, this book is one of the very few thorough in-depth accounts of quantifying the effectiveness of new ideas and innovations in game-tree searching in computer chess. Even a casual reading will convince anyone of the tremendous amount of work that Heinz put into the experiments described in this monograph. I applaud Heinz’s initiative to rework his ICCA articles and ACC conference contributions into this highly enjoyable book, which turned out to be much more than the sum of the individual components. There is absolutely no need for the 'apology' he offers on his homepage (http://supertech.lcs.mit.edu/~heinz/): "I know that this [book] is not cheap. :-( But although I sincerely intended the book to cost much less, there was no chance to hit a lower price point for a printed volume in a specialty area such as computer chess (even if I renounced all royalties)". Heinz absolutely deserves the little money he earns in royalties from this excellent book. Even though I can think of two places where he might have cut the size of the manuscript (‘Figure 0.1: Empty Chess Board’, which occupies half a page, and, more notably, ‘Appendix D.1 Test Games vs. Strong PC Chess Programs’, which takes up 40 pages of this 268-page book). I doubt whether this would have brought the price down. As it is, the book offers good value for the money. Had the field not been so frightfully small, my closing remark would have carried a wee bit more weight: Scalable Search in Computer Chess is one of the three best computer-chess books of the decade!


1 Leiden Observatory, P.O. Box 9513, 2300 RA Leiden, The Netherlands. Email: dap@strw.leidenuniv.nl.