ICGA Journal

Vol. 24, No. 4 - December 2001

Table of Contents

Table of Contents 201
Science, Competition and Business (H.J. van den Herik) 201
Computer Go: Knowledge, Search, and Move Decision (K-H. Chen) abstract 203
Online Interpretation of Chess Columns (S. Paramasamy) abstract 216
Notes:
3-5-Man Chess: Maximals and Mzugs (G.McC. Haworth, P. Karrer, J.A. Tamplin, and C. Wirth) 225
AND/OR-tree Search Algorithms in Shogi Mating Search (M. Sakuta and H. Iida) abstract 231
Review: 236
Advances in Computer Games 9 (D. Hartmann) 236
Articles Published Elsewhere 238
Information for Contributors 241
News, Information, Tournaments, and Reports: 242
Report on the 5th ACBL World Computer-Bridge Championship (A. Levy) 242
Grandmaster Chess with One-Sided Computer Help (I. Althöfer) 246
Report on the 21st Open Dutch Computer-Chess Championship (Th. van der Storm) 253
Computer Shogi vs. Lady-Professional Player at 2001 MSO Japan (T. Takizawa) 256
Report on the Game-On 2001 Conference (P. Spronck) 257
The 2000 Chess-Base Best-Publication Award (The Board of ICCA) 258
The ICCA Journal Award for 2000 and 2001 (The Board of ICCA) 259
Calendar of Computer-Games Events in 2001-2003 259
The ICGA Journal Referees in 2001 260
The CMG Seventh Computer Olympiad (Maastricht, The Netherlands) 261
The Swedish Rating List (T. Karlsson) 262
Correspondence 263
The Bell Captain (H. Nefkens) 263
Invader's Performances (R. Lorentz) 263
Buggy's Team-mate (N. Guibert) 263
Make Sure the ICGA Journal Reaches You 264

 

SCIENCE, COMPETITION AND BUSINESS

There is an intricate relationship between science, competition and business. Of these three entities competition plays a special part, since it is closely involved in all research activities and well known to the farthest corners of commerce. In itself, competition is pure and a logical consequence of the existence of games as is manifest in the Olympic Games. However, in connection with one of the two other entities, we see a clear difference between science and business.

In science the competition can be tough, very tough, but the focus typically is on honour, whereas in business the focus is on money and the competition mostly searches for the boundaries of what is legally allowed. Obviously, university professors and businessmen live in different worlds. Now and then they meet; for instance, during conferences with product demonstrations (especially in the medical domain), or at the Computer Olympiad, where amateurs play for fun and honour, and professionals for position and money.

In the past, in computer competitions, this discrepancy has led to amateur titles and professional titles. Since the machines perform the actual work instead of the brains behind the machines, we recently (2001) distinguished between a single-processor World Champion and a multiple-processor World Champion. So, four titles were theoretically possible. Of course, winning one such a title diminishes the honour compared to the situation in which only one title is at stake. The latter statement applies equally well to money instead of honour. Therefore it comes as no surprise that the future participants of the Computer Olympiad, professionals as well as amateurs, wish to change this assortment of titles. One program should be the best, honoured as such by the title World Champion, and thus receive the appropriate revenues.

This is not the end of the story since a competition is needed to establish the best program, and for such a contest the rules should be spelled out. It is not an easy task to achieve that professionals and amateurs are univocal on the rules to be followed. There are many obstacles and although everybody wishes to arrive at a solution, the opinions diverge considerably. The ICCA is aware of these difficulties and in the autumn of 2001 a rule-discussion group was formed. The moderator is Bruce Moreland.

The ICCA was invited to take part in the discussion, but is certainly not leading. Now and then our President David Levy makes a statement. Following the pros and cons of every item it must be admitted that several different positions are acceptable. To mention a few items, we see discussion on the opening book (should the author be a team-mate?), multiple entrants (can a human being simultaneously be a member of two or more teams?), cloned programs (when is a program a cloned copy of an existing program?) and the professional interfaces (who is allowed to use ChessBase's dedicated user interface functions?).

Here science and business meet again. There is hardly any discussion on using Eugene Nalimov's endgame tablebases. No one suggests that Nalimov's name should appear in the authors' list of the programs using the tablebases. To make this point even more explicit, the alpha-beta algorithm is not credited in any form. Fortunately, the algorithm is not patented and all programmers may make free use of it. In addition to this observation the scientific question should still be: who is to be credited for alpha-beta? There are four candidates. Newell, Shaw and Simon were the first to publish on the algorithm, albeit without deep cut-offs. That was in 1958. According to Knuth and Moore (1975) it should be McCarthy, who voiced the idea during Bernstein's talk in the Dartmouth conference in 1956. The third candidate is Samuel, who claimed in an article published in 1963, that he had already implemented this idea in an early version of his Checkers program in the beginning of the 1950s, but that it was too straightforward to devote a paper to it. His research focus was learning and not pruning. The fourth candidate is Brudno (1963), who published the first real publication on alpha-beta (in Russian).

This is science in all its splendour: scientists claiming priority for the honour only. For Nalimov, an analogous reasoning holds true. In this issue (p. 258) the ICCA honours him as the recipient of the ChessBase Best-Publication Award for the year 2000, for creating and making his tablebases plus generator program publicly available. Thank you, Eugene!

In the 1970s and 1980s many computer-chess aficionados were eager to be involved in computer programs, if only they would not have needed to go through all the details of board representation and move generation. They would have loved to tune the evaluation function and improve the move ordering. At the time it seemed an unattainable desire. However, GnuChess appeared, and later on Bob Hyatt's Crafty, for which Hyatt deservedly received the 1995-1996 Novag Best-Publication Award, helped many computer-chess programmers to start their own program. This service to the public is now topic of discussion.

The area is grey and full of untrodden paths. In Portoroz 1989, the Tournament Directors (Jaap van den Herik and Jonathan Schaeffer) faced a formal protest by the Hegener + Glaser Company, owners of the Mephisto line of machines, against the program Quickstep (see ICCA Journal, Vol. 12, No. 4, pp. 233-234). The evidence was overwhelming and the disqualification was unavoidable. However, science and business have progressed since then and it is no longer clear that cloned programs can be distinguished with the same accuracy as was possible more than ten years ago.

Over the years we have seen an impressive list of scientists. Moreover, we have seen Fidelity, Mephisto and Novag as supporters of computer-chess research. Currently we live in a world dominated by ChessBase. They claim to have the best software regarding playing strength and user friendliness. Still your Editor is looking forward to the next World Championship (WCCC 2002) and is hoping for a tough competition between a scientist and a business professional.

Jaap van den Herik


 

COMPUTER GO: KNOWLEDGE, SEARCH, AND MOVE DECISION

Keh-Hsun Chen1

Charlotte, NC, USA
 

ABSTRACT2

This paper intends to provide an analytical overview of the research performed in the domain of computer Go. Domain knowledge that is essential to Go-playing programs is identified. Various computation and search techniques that can be used effectively to obtain helpful domain knowledge are presented. Four different move-decision paradigms applied by today's leading Go programs are discussed. Conclusions are drawn and two proposals of improvements to current move-decision paradigms are presented.


1 Department of Computer Science, University of North Carolina, Charlotte, NC 28223, USA. Email: chen@uncc.edu.
2 The paper is an edited and extended version of the author's invited lecture "Knowledge and Search in Computer Go" presented at the Game Programming Workshop 2001 held in Hakone, Japan, October 26 to 28, 2001 (Chen, 2001b).

 

ONLINE INTERPRETATION OF CHESS COLUMNS

S. Paramasamy1

St. Augustine, Trinidad
 

ABSTRACT

This paper considers an online interpretation problem related to chess articles containing annotated chess games, published in online newspapers/magazines and chess-based web sites. The formats of most articles examined by the author were rigorous in the sense that a software program could be constructed to play the moves of the annotated games and the moves of the variations given in the articles on online chessboards. The author presents some results based on a preliminary version of a software program that interprets 'well-formed' chess articles. He argues that this type of interpreter should be a feasible alternative to conversion utilities such as PGN-file constructors/readers that are otherwise required to build/interpret these columns.


1 Department of Mathematics and Computer Science, The University of the West Indies, St. Augustine, Trinidad. Email: s_param@hotmail.com.

 

NOTE

3-5-MAN CHESS: MAXIMALS AND MZUGS

G.McC. Haworth1, P. Karrer2, J.A. Tamplin3 and C. Wirth4

UK, Switzerland and USA
 

ABSTRACT

This note reports the combined results of several initiatives in creating and surveying complete suites of endgame tables (EGTs) to the Depth to Mate (DTM) and Depth to Conversion (DTC) metrics. Data on percentage results, maximals and mutual zugzwangs, mzugs, has been filed and made available on the web, as have the DTM EGTs.

1. INTRODUCTION

Nalimov and Wirth independently, and essentially contemporaneously, have completed suites of 3-to-5-man EGTs respectively to the Depth to Mate (DTM) and Depth to Conversion (DTC) metrics (Wirth and Nievergelt, 1999; Nalimov, Haworth and Heinz, 2000, 2001; Wirth, 2000; Hyatt, 2001; Lincke, 2001a; Tamplin, 2001a).

Karrer (2000) has mined Nalimov's EGTs to produce complete lists of:

Wirth (2000) produced the analogous DTC data and also calculated the percentage results, 1-0, draw and 0-1, wtm and btm. As he provided the number of positions won in a specific number of plies (Lincke, 2001b), quick wins based on tactical devices may be discounted as required from these percentages. Because Wirth eliminates from his EGTs duplicates of positions with two Kings on a long diagonal, his percentage statistics are marginally more accurate than Nalimov's. Both, for reasons of comparability, discount only those unreachable positions where the side-not-to-move is in check.

Tamplin and Haworth correlated the mzug data to confirm that the sets of positions had indeed been twin-sourced. Tamplin (2001a) provides, with the assistance of the Lincke (2001a) site, an excellent query service to both the DTC and DTM EGTs and files of endgame data, including the data discussed here.

2. MAXIMAL DATA

The large table of maximal results is published on the web (Tamplin, 2001a) rather than here. It includes for both the DTC and DTM metrics, the maxDTx figures (1-0 and 0-1, wtm and btm) and the %-win statistics derived from Wirth's data. Some observations follow.

Independent maxDTM results by Rasmussen (2000) agreed completely with Nalimov's and Karrer's data. Thompson's original and comprehensive set of 5-man EGTs (Thompson, 2000; Tamplin, 2001b) minimax the DTC of the next btm position rather than strictly optimising the next conversion to a subgame: the weaker side sometimes captures voluntarily as a human player might do. The inconsequential difference is that his maxDTC is just one less than Wirth's for KRKNP, KRRKN and KBNKP. Thompson (2001) now minimaxes the current DTC by minimaxing the number of men on the board first.

Note that, when minimising DTC, the stronger side may unnaturally force-sacrifice surplus force. This occurs for example in KQQQK and KQBNK, and was seen in Game 4 of the Deep Fritz - Deep Junior match in 20015. Wirth used the existing ETH(Zürich) software Retroengine which assumed that captures are made by the winner. Where this need not be so as in wKc3Rb4c2/bKa1+w, Wirth's depths in plies are one ply too great: some maxDTCs6 and counts of maxDTC positions are affected (Tamplin, 2001c). Further, DTC measured in winner's moves can rate moves equi-optimal whose depths differ by one ply. An example is wKc5Rb4c2/bKa1Na7a8 (Thompson, 2001) where Ra4+ and Kd4/5/6 are rated alongside Ra2+.

3. MUTUAL ZUGZWANGS

A reciprocal or mutual zugzwang, mzug, in chess is a position where, ironically, each side could get a better result in theory if it were the other side's turn to move. There are three types of mzug:

ww = /1-0 a 'White win' mzug ... the position is a wtm draw and a btm win for White
bw -1/ = a 'Black win' mzug ... the position is a wtm win for Black and a btm draw
fp -1/1-0 a 'full point' mzug ... the side that has to move loses.

They are relatively rare and the mzug is a running theme in the composition of endgame studies (Roycroft, 1972; Nunn, 1992, 1994, 1995; Beasley and Whitworth, 1996; Elkies, 1998a; Beasley, 2000). Many counts of mzugs by Rasmussen (1991-2000) have already been published in the endgame quarterly EG: they confirm and are confirmed by the data here.

Figure 1: max mzug. Figure 2: max fp mzug. Figure 3: dc = 91. Figure 4: dc = 67.

 

Figure 5: bw, dc = 63. Figure 6: dc = 58. Figure 7: bw, dc = 53. Figure 8: Le Trébuchet.

3.1 The Results

Karrer (2000) scanned Nalimov's 3-to-5-man EGTs (Hyatt, 2001; Tamplin, 2001a) for mzug positions, giving:

The lists were then passed via Haworth to workers in this field including Elkies, Rasmussen, Roycroft, Tamplin and Wirth. Haworth collated the resulting statistics, confirming full agreement between the data of Karrer, Wirth and Rasmussen, and identifying mzugs which were maximal in both DTC and DTM terms.

 

Table 1: 3-5-man data on mutual zugzwangs.

Tamplin (2001a) confirmed that the scans of DTC and DTM tables had yielded exactly the same sets of mzugs of each type, further comprehensive evidence in itself of the integrity of the EGTs.

There are 21,677 ww, 3,395 bw and 33 fp 3-to-5-man-mzugs. These occur in 59 of the 146 endgames. The full point mzugs occur in just six endgames, namely KBPKP, KNPKP, KPKP, KPPKP, KPPKR and KRPKP: each features at least two Pawns. The complete data, statistics and various sets of positions, are available (Tamplin, 2001a). Here, the statistics are in Table 1 and the examples of maximal mzugs are in Table 2.

 

Table 2: Sample maximal mutual zugzwangs of the three types.

Some explanatory notes, which also apply to the associated website (Tamplin, 2001a) are appropriate:

Figures 1-8 illustrate the deepest mzugs of different types. Some facts, snapshots and curiosities:

KNNKP q.v. Figure 1: a maxDTC/M 3-to-5-man mzug with dc = dm = 105 moves.
KNPKP q.v. Figure 2: max fp mzug with (wtm) dc = 1 and dm = 17, (btm) dc = 13 and dm = 28.
KQPKQ q.v. Figure 3: max KQPKQ mzug with dc = 91 and dm = 102.
KBNKN q.v. Figure 4: max KBNKN mzug with dc = 67 and dm = 97.
KRPKQ q.v. Figure 5: the maxDTC/M type-2 mzug with dc = 63 and dm = 91.
KBNKQ 8/8/q7/8/3K4/2N5/8/k1B5: the only maximal P-less mzug with both Kings on a1-h8.
KPPKR only fp mzugs not having Pawns on both sides: one maxDTC, the other maxDTM.
KPKP q.v. Figure 8; 'Le Trébuchet', the KPKP model for 15 of the 33 4-5-man full-point mzugs
KRKN 8/8/8/4k3/3R4/2K5/1n6/8: a diagonally symmetric mzug.

All the 4-5-man full-point mzugs feature at least two Pawns: the 6-man rk1N4/n2K4/P7/8/8/8/8/8 (Elkies, 2000b) needs only one and the 7-man 8/8/8/8/2N5/1N6/r1n5/1b1k1K2 needs none7 (Elkies, 1998b). The likelihood is that there are no pawnless 6-man fp mzugs (Elkies, 2000a).

For a given endgame and type of mzug, ZC and ZM are the sets of maxDTC and maxDTM mzugs respectively. Curiously, ZC and ZM are either disjoint, identical or one is a subset of the other. There is no end-game for which ZC - ZM Ø and ZM - ZC Ø:

ZC ZM = Ø KBNKP ww, KBNKR ww, KBPKN ww, KBPKP bw, KBPKR bw, KBPPK ww, KNNKP bw, KNNKR bw, KNPKP ww, KNPKR ww, KNPPK, KPKP ww (and so bw), KPPKB ww, KPPKP ww, bw and fp, KPPKR fp and KQBKQ ww.
ZC < ZM KNPK ww (1-2), KPPKN ww (1-2) and bw (11-15), KRNKN ww (1-2) and KRPKR ww (1-2).
ZC > ZM KBBKR ww (3-1), KBPKQ bw (2-1), KNPKN ww (3-1), KNPKP bw (6-1), KPKP fp (15-1), KPPK ww (6-1), KRKP ww (6-4), KRPKN ww (4-1), KRPKP bw (2-1) and KRPKQ ww (2-1).

The following 55 2-to-4-man and 3-2 endgames have no mzugs:

KBBK, KBBKB, KBK, KBKB/N, KBNK, KK, KNK, KNKN, KNNK, KNNKB, KQBK, KQBKB/N/P/R, KQK, KQKB/N/P/Q/R, KQNK, KQNKB/N/P/R, KQPK, KQPB/N/P, KQQK, KQQKB/N/P/Q/R, KQRK, KQRKB/N/P/R, KRBK, KRBKB/N, KRK, KRKR, KRNK, KRNKB/P, KRPK, KRRK, KRRKN/P/R.

The only 4-1 endgames with mzugs are KBPPK, KNPPK and KPPPK, echoing the fact that the only 3-1 endgames with mzugs are KBPK, KNPK and KPPK.

4. SUMMARY

This note records the achievement of Karrer, Nalimov and Wirth whose combined work has created a definitive survey of the 3-5-man chess domain. Their work sets an example and provides a basis for further workers to respond to Van der Heijden's challenge (2001) to mine this data for the interesting study-like positions.

Thanks go first of course to Nalimov, and also to Rasmussen and Thompson who provided third and fourth independent sources of data. Our thanks also go to Roycroft who provided access to Rasmussen's contributions in past copies of EG.

5. REFERENCES

Beasley, J. and Whitworth, T. (1996). Endgame Magic. B.T. Batsford, London, UK. ISBN 0-7134-7971-X.

Beasley J. (2000). Creating reciprocal zugzwang studies. EBUR, Vol. 12, No. 2, pp. 8-12.

Elkies, N.D. (1998a) www.h3.org/pub/acj/extra/Elkies/Elkies04.html. Zugzwang (Part I).

Elkies, N.D. (1998b) EG, Vol. 8, No. 128, p. 320. ISSN 0012-7671.

Elkies, N.D. (2000a). Originals. EG, Vol. 9, No. 136, p.59.

Elkies, N.D. (2000b). Private communication.

Heijden, H.M.J.F. van der (2000). Private communication.

Heijden, H.M.J.F. van der (2001). Endgame Tables and Endgame Study Composition. ICGA Journal, Vol. 24, No. 2, pp. 88-92. ISSN 1389-6911.

Hyatt, R. (2001). ftp://ftp.cis.uab.edu/pub/hyatt/TB/. Server providing Nalimov's EGTs and statistics.

Karrer, P. (2000). Private communication.

Lincke, T. (2001a). nobi.inf.ethz.ch/games/chess. 3-5-man DTC EGT query service.

Lincke, T. (2001b). wwwjn.inf.ethz.ch/games/chess/statistics/chs_statistics.html. DTC win and draw statistics for 3-man to 6-man endgames.

Nalimov, E., Haworth, G.McC. and Heinz, E.A. (2000). Space-efficient Indexing of Endgame Tables for Chess. ICGA Journal, Vol. 23, No. 3, pp. 148-162.

Nalimov, E., Haworth, G.McC. and Heinz, E.A. (2001). Space-efficient Indexing of Endgame Tables for Chess. Advances in Computer Games 9, (eds. H. J. van den Herik and B. Monien), pp. 93-113. Institute for Knowledge and Agent Technology (IKAT), Maastricht, The Netherlands. ISBN 90 6216 5761.

Nunn, J. (1992). Secrets of Rook Endings. B.T. Batsford, London. ISBN 0-7134-7164-6. 2nd edition (1999). Gambit. ISBN 1-9019-8318-8.

Nunn, J. (1994). Secrets of Pawnless Endings. B.T. Batsford, London. ISBN 0-7134-7508-0. 2nd edition, to be published. Gambit. ISBN 1-9019-8365X.

Nunn, J. (1995). Secrets of Minor-Piece Endings. B.T. Batsford, London. ISBN 0-7134-7727-X.

Rasmussen, L. (1991-2000). Mutual Zugzwang Results (various). EG, No. 102.2, pp. 962-980; No. 116, p. 633; No. 118, pp. 719-733; No. 119, pp. 775-783; No. 122, pp. 923-950; No. 123, pp. 47-48; No. 124, pp. 106-113; No. 128, pp. 313-318; No. 130, pp. 417-428; No. 131, pp. 481-491; No. 132, pp. 533-544; No. 133, pp. 595-603 and No. 136, pp. 125-148. ARVES, The Netherlands.

Rasmussen, L. (2000). Maximal and Mutual Zugzwang Results. Private communication.

Roycroft, A.J. (1972). Test Tube Chess: A Comprehensive Introduction to the Chess Endgame Study. Faber and Faber Ltd. ISBN 0-5710-9573-9.

Tamplin, J. (2001a). chess.jaet.org/endings/. Chess endgame site: EGTs, maximals and mzugs.

Tamplin J. (2001b). chess.liveonthenet.com/chess/endings/index.shtml. Ken's original 5-man DTC EGTs.

Tamplin, J. (2001c). Private communication.

Thompson, K. (2000). Private communication.

Thompson, K. (2001). cm.bell-labs.com/cm/cs/who/ken/chesseg.html. 6-man EGTs, maximal positions, maximal mutual zugzwangs and endgame statistics.

Wirth, C. and Nievergelt, J. (1999). Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame. ICCA Journal, Vol. 22, No. 2, pp. 67-80.

Wirth, C. (2000). Private communications on the generation of 4-1 DTC EGTs and derived data.


1 33, Alexandra Rd., Reading, Berkshire, UK RG1 5PG. email: guy.haworth@icl.com
2 Plattenstrasse 80, CH-8032 Zurich, Switzerland: pkarrer@active.ch
3 4116, Manson Ave, Smyrna, GA, 30082-3723, USA. email: jat@jaet.org
4 IN4OUT interactive ag, In Boeden 139, CH-8046 Zurich, Switzerland. email: christoph.wirth@in4out.com
5 DJ-DF, r7/8/5R2/2k5/8/3R1K2/6P1/8 w: 70. Rc6+ Kb5 71. Rc5+ Kb4 72. Rb5+ Kc4 73. Rd4+ Kc3 74. Rc5+ K?d4
6 To date, Tamplin (2001c) has identified this second inconsequential maxDTC '1 out' difference for KQ(B/N/Q/R)K, KRRK, KQQKN, KQRKR, KRRK(N/Q), KBBBK, KQ(BN/RB/RN)K and KR(BN/RR)K.
7 White (to move) can do no better than mobilise Black with 1. Kf2, Kg1/2 or Nc5. Black (to move) allows mates in 1.

 

NOTE

AND/OR-TREE SEARCH ALGORITHMS IN SHOGI MATING SEARCH1

Makoto Sakuta and Hiroyuki Iida2

Hamamatsu, Japan
 

ABSTRACT

The note describes the development of AND/OR-tree search algorithms in the mating search of shogi. Originally depth-first algorithms are successfully transformed in best-first algorithms, such as PN*, PDS, and df-pn. Each of these algorithms aims at solving hard tsume-shogi problems. The algorithms can be characterized as variants of proof-number search. We note that PN* only uses proof numbers, while PDS and df-pn uses both proof numbers and disproof numbers. The df-pn search behaviour is similar to proof-number search's behaviour. Recently, the strong shogi programs have come to apply these algorithms in their tournament versions and are now able to find relatively long-step mating sequences in a short time.


1 This note is an edited and extended version of the second author's invited lecture "Advances of AND/OR-tree Search Algorithms in Shogi Mating Search", presented at the Computer Game-Playing Workshop 2001, held in Maastricht, The Netherlands, on August 20-23, 2001, in the framework of the CMG 6th Computer Olympiad in Maastricht, August 19-23, 2001.
2 Department of Computer Science, Shizuoka University, 3-5-1 Johoku, Hamamatsu, 432-8011 Japan. E-mail: {sakuta,iida}@cs.inf.shizuoka.ac.jp}

 

REVIEW

ADVANCES IN COMPUTER GAMES 9

by H.Jaap van den Herik and Burkhard Monien
IKAT, Universiteit Maastricht
Maastricht, The Netherlands
and University of Paderborn
Paderborn, Germany
348 pp. Euro 55

Reviewed by Dap Hartmann


What started in 1975 as the Advances in Computer Chess conference series, has now fully expanded to include all intelligent computer games, and is hence renamed to Advances in Computer Games. Consistently publishing well-edited proceedings has been crucial to the success of this series. The previous two editions already contained a number of papers on games other than Chess. In this ninth volume, the ratio of non-chess to chess papers has risen to 50:50. Of the non-chess papers, three are on Shogi and three are on Go. Backgammon, Amazons, Chinese Chess, and 6×6 Othello & Tsume-Shogi contribute one paper each. In the rock-steady pace of three-year intervals, this conference was held in June 1999 – exactly 24 years after the first meeting. It was hosted by the University of Paderborn, during the 9th World Computer Chess Championship.

Hashimoto et al. present an evaluation function for the game of Amazons. As far as I am aware, it is the first-ever paper on the computer implementation of this fascinating game. It contains sufficient information to write your own Amazons-playing program. My recommendation: by all means, do! This exciting new game could certainly use more competitors. At present, one program sovereignly rules the field, and it has thrashed all opposition from the moment it first came onto the scene. Purely as a diversion from his usual chess programming, Johan de Koning picked Amazons from the list of new games announced for the 2000 Olympiad in London. His brainchild, 8QP (short for Eight Queens Problem), pulled computer Amazons out of its infancy. It finished first in both the 2000 and 2001 Olympiads by winning every single game, in most cases by a large margin. What I like most about the Hashimoto et al. paper, is that it subliminally encourages writing an Amazons program. While reading the paper, it is hard to resist the temptation of trying out a few things on a computer. And before you know it, you are writing a move generator, if only to convince yourself that there are indeed 2176 legal moves in the initial position. The authors probably never set out to accomplishing this, but it is a wonderful achievement, nonetheless. However, they do predict: "We are convinced that further work on the Amazons evaluation function will improve the playing strength considerably." Johan de Koning can attest to that. The question remains: who is next?

One way to discover how various games are interrelated, is to glance through the reference sections. Cazenave's contribution ('Generating Patterns with External Conditions for the Game of Go') cites papers on Nine Men's Morris, Chess, Checkers, Rubik's Cube, and, of course, Go. The paper by Wu and Beal ('Computer Analysis of some Chinese Chess Endgames') refers to several papers on the construction of (Western) Chess endgames. It also contains the oldest reference I ever came across in a computer-science paper: a manuscript by Zhi Xy from 1570. That is, until I read the final paper in this volume, which has references dating back to 1561 and 1497. In this delightful contribution, Frederic Friedel discusses various ways of cheating in Chess. Don't close this book without reading it! The account of Clemens Allwermann playing (cheating) in the Böblinger Open is a real detective story. But more important than an occasional low-ranked player who boosts his performance through illicit computer assistance, are the problems that may occur at the very highest level of play. As Friedel explains: "The problem is more serious the higher you go up the Elo scale. Not only do the players need progressively less information, they also gain progressively more from cheating with the computer." A distinctive cough, a scratch on the head, or any other small inconspicuous signal by an accomplice can communicate that a winning move exists. Friedel relates how during the game Kasparov-Anand (Las Palmas, 1996), Jan Timman found a winning move (g4) for white. FRITZ analyzed this move, and confirmed the win. Kasparov missed it during the game, but Friedel convincingly argues that through a simple prearranged signal (indicating: 'there is a win here') he would certainly have found it. Which raises another question in my mind: how do the (FIDE) rules deal with a spectator who simply shouts out: "g4 wins!"?

I hope that Friedel will consider expanding this paper into a full-length book on the subject. There are certainly other instances of cheating, and the examples he presents deserve a broader exposition. The famous 'yogurt incident' during the Karpov-Korchnoi match in Bagio City in 1978 is merely a footnote, while the notorious Dr. Vladimir Zukhar is not mentioned at all. Surely, the deliberate distraction of the opponent is a form of cheating as well. And while it is still strictly a human vice, cheating is certainly not confined to the human chess world. There are plenty of stories and rumors about cheating in computer chess, but few were ever committed to paper. And then there is Kasparov's accusation that DEEP BLUE cheated in game 2 of the 1997 match in New York. The challenged move (Be4) was apparently so brilliant that, according to Kasparov, only a few of the very best human players could have found it. So, the accusation was really a compliment. Cheating in chess (or any other game) is a fascinating topic with many levels of impact. Another wonderful tale of using a computer to cheat (not in chess but at roulette), is The Eudaemonic Pie by Thomas Bass. Particularly interesting is the way in which the human gambler received information from the computer hidden in his shoes. Guest star in this thrilling adventure is none other than the great Claude Shannon.

Any one who feared that, after a quarter of a century, Advances in Computer Games might be running out of steam, will be in for a treat. The quality of the papers contained in this ninth volume of the series is remarkably high. And it is not just the greater variety of games that makes these proceedings surpass the previous two editions. Perhaps most surprising is the freshness of the Chess contributions, which attest to the still ongoing progress. The fact that the human World Champion lost a match against a chess-playing computer has apparently not discouraged computer-chess research, nor has it weakened the inspiration.

Commercial chess programmers and manufacturers rarely reveal details about their programs. Several years ago, David Levy published in the ICCA Journal a number of ideas implemented in his programs. Now it is Marty Hirsch who spills the beans on the innards of MCHESS. The prime motivation to eventually publish such 'secrets' is seeing these ideas (re)discovered and published by academics and amateurs. The situation is similar to, for example, the invention and publication of public-key encryption by Diffie, Hellman and Merkle. Unknowing to the world, this technique had already been discovered six years earlier by James Ellis, a British cryptographer employed by her Majesty's Secret Service. But he was sworn to secrecy, and it took another 28 years before his accomplishment was made public. James Ellis was the first person to develop public-key encryption, but it earned him no more than a footnote in the history of cryptography. He later wrote: "Most professional scientists aim to be the first to publish their work, because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography is realised by minimising the information available to potential adversaries." Or, in the apologetic words of Marty Hirsch: "The delay of publication is due to commercial considerations." Even though you cannot have your pie and eat it, his belated publication of ideas deserves praise.

Advances in Computer Games 9 is a beautifully edited book, the third in this series supervised by Jaap van den Herik. This time he teamed up with Burkhard Monien of the University of Paderborn to produce another winner. Conference proceedings (and, for that matter, periodicals such as the ICGA Journal) are much more than a bunch of scientific papers wrapped in a cover with some guy's name on the front. For a field as small as computer games, the quality of publishing is unusually high. By now we may have become used to this high standard, but in reality we are truly spoilt. The only minor complaint I have is that the photographs could do with a bit more contrast. But that is almost like complaining that the cover is blue.

I realize that in this limited space, I cannot do equal justice to all contributions in the book. I merely highlighted some of the papers that particularly caught my fancy, to wet the appetite of readers of this review. It is definitely a must-have for anyone interested in intelligent computer games.


 

ARTICLES PUBLISHED ELSEWHERE

SOKOBAN: ENHANCING GENERAL SINGLE-AGENT SEARCH METHODS USING DOMAIN KNOWLEDGE

Andreas Junghanns and Jonathan Schaeffer1

Alberta, Canada

Artificial Intelligence, Vol. 129, Nos. 1-2, pp. 219-251.

We reproduce the abstract:
"Artificial Intelligence(AI) research has developed an extensive collection of methods to solve state-space problems. Using the challenging domain of Sokoban, this paper studies the effect of general search enhancements on program performance. We show that the current state of the art in AI generally requires a large research and programming effort to use domain-dependent knowledge to solve even moderately complex problems in such difficult domains. The application of domain-specific knowledge to exploit properties of the search space can result in large reductions in the size of the search tree, often several orders of magnitude per search enhancement. This application-specific knowledge is discovered and applied using application-independent search enhancements. Understanding the effect of these enhancements on the search leads to a new taxonomy of search enhancements, and a new framework for developing single-agent search applications. This is used to illustrate the large gap between what is portrayed in the literature versus what is needed in practice."

 

THE PN*-SEARCH ALGORITHM: APPLICATION TO TSUME-SHOGI

Masahiro Seo2 , Hiroyuki Iida3 , and Jos W.H.M. Uiterwijk4

Osaka, Hamamatsu, Japan / Maastricht, The Netherlands

Artificial Intelligence, Vol. 129, Nos. 1-2, pp. 253-277.

We reproduce the abstract:
"This paper proposes a new search algorithm, denoted PN*, for AND/OR tree search. The algorithm is based on proof-number (PN) search, a best-first search algorithm, proposed by Allis et al. [Artificial Intelligence 66 (1) (1994) 91-124], and on Korf's RBFS algorithm [Artificial Intelligence 62 (1) (1993) 41-78]. PN* combines several existing ideas. It transforms a best-first PN-search algorithm into an iterative-deepening depth-first approach. Moreover, it is enhanced by methods such as recursive iterative deepening, dynamic evaluation, efficient successor ordering, and pruning by dependency relations. The resulting algorithm turns out to be highly efficient as witnessed by the experimental results.

"The PN* algorithm is implemented in a tsume-shogi (Japanese-chess mating-problem) program, and evaluated by testing it on 295 notoriously difficult tsume-shogi problems (one problem has a depth of search of over 1500 plies). The experimenta1 results are compared with those of other programs. The PN* program shows by far the best results, solving all problems but one. Needless to say, it outperforms the best human tsume-shogi problem solvers by far."

 

PARTIAL ORDER BOUNDING: A NEW APPROACH TO EVALUATION IN GAME TREE SEARCH

Martin Müller5

Edmonton, Canada

Artificial Intelligence, Vol. 129, Nos. 1-2, pp. 279-311.

We reproduce the abstract:
"In computer game-playing, the established method for constructing an evaluation function uses a scalar value computed as a weighted sum of features. This paper advocates the use of partial order evaluation, and describes an efficient new search method called partial order bounding (POB).

"Previous tree search algorithms using a partial order evaluation have attempted to propagate partially ordered values through the search tree, which leads to many problems in practice, such as the complexity of backing up sets of incomparable evaluations. POB compares partially ordered values only in the leaves of a game tree, and backs up boolean values through the tree. A closely related new algorithm, linear extension partial order bounding (LE-POB), uses a standard scalar alpha-beta search with values from a suitably chosen linear extension of the partial order evaluation. As an application, the effectiveness of partial order evaluation is shown in the case of modeling capturing races called semeai in the game of Go."

 

THE EFFECT OF MOBILITY ON MINIMAXING OF GAME TREES WITH RANDOM LEAF VALUES

Mark Levene6 and Trevor I. Penner7

London, UK

Artificial Intelligence, Vol. 130, No. 1, pp. 1-26.

We reproduce the abstract:
"Random minimaxing, introduced by Beal and Smith [ICCA J. 17 (1994) 3-9], 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. The experiments carried out by Beal and Smith, using random minimaxing in Chess, showed that the strength of play increases as the depth of the lookahead is increased. We investigate random minimaxing from a combinatorial point of view in an attempt to gain a better understanding of the utility of the minimax procedure and a theoretical justification for the results of Beal and Smith's experiments. The concept of domination is central to our theory. Intuitively, one move by white dominates another move when choosing the former move would give less choice for black when it is black's turn to move, and subsequently more choice for white when it is white's turn to move. We view domination as a measure of mobility and show that when one move dominates another then its probability of being chosen is higher.

"We then investigate when the probability of a "good" move relative to the probability of a "bad" move increases with the depth of search. We show that there exist situations when increased depth of search is "beneficial" but that this is not always the case. Under the assumption that each move is either "good" or "bad", we are able to state sufficient conditions to ensure that increasing the depth of search increases the strength of play of random minimaxing. If the semantics of the game under consideration match these assumptions then it is fair to say that random minimaxing appears to follow a reasonably "intelligent" strategy. In practice domination does not always occur, so it remains an open problem to find a more general measure of mobility in the absence of domination."

 

COMPUTER GO: AN AI ORIENTED SURVEY

Bruno Bouzy8 and Tristan Cazenave9

Paris, France

Artificial Intelligence, Vol. 132, No. 1, pp 39-103

We reproduce the abstract:
"Since the beginning of AI, mind games have been studied as relevant application fields. Nowadays, some programs are better than human players in most classical games. Their results highlight the efficiency of AI methods that are now quite standard. Such methods are very useful to Go programs, but they do not enable a strong Go program to be built. The problems related to Computer Go require new AI problem solving methods. Given the great number of problems and the diversity of possible solutions, Computer Go is an attractive research domain for AI. Prospective methods of programming the game of Go will probably be of interest in other domains as well. The goal of this paper is to present Computer Go by showing the links between existing studies on Computer Go and different AI related domains: evaluation function, heuristic search, machine learning, automatic knowledge generation, mathematical morphology and cognitive science. In addition, this paper describes both the practical aspects of Go programming, such as program optimization, and various theoretical aspects such as combinatorial game theory, mathematical morphology, and Monte Carlo methods."

Picture from: members.aol.com/allevy/Toronto/pictures2.html

David and Lisa Berkowitz take on JACK.
The exhibition match in Toronto, July 23-28, 2001.


1 Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8. Email: {andreas,jonathan}@cs.ualberta.ca
2 AVC Company, Matsushita Electric Industrial, Co., Ltd., Osaka, Japan. Email: seo@biu.avcg.mei.co.jp
3 Department of Computer Science, Shizuoka University, Hamamatsu, Japan. Email: iida@cs.inf.shizuoka.ac.jp
4 Institute for Knowledge and Agent Technology ( IKAT), Department of Computer Science. Universiteit Maastricht, Maastricht, The Netherlands. Email: uiterwijk@cs.unimaas.nl
5 Department of Computing Science, University of Alberta, Edmonton, Canada T6G 2E8. Email: mmueller@cs.ualberta.ca
6 Department of Computer Science, University College, University of London, Gower Street, London WCIE 6BT, UK. Email: mlevene@cs.ucl.ac.uk
7 Department of Computer Science, Birkbeck College, University of London. Malet Street, London WCIE 7HX, UK. Email: trevor@dcs.bbk.ac.uk
8 Université René Descartes (Paris V). UFR de mathématiques et d'informatique. C.R.I.P.5., 45, Rue des Saints-Pères, 75270 Paris Cedex 06, France. Email: bouzy@math-info.univ-paris5.fr
9 Université Paris 8. Département Informatique. Laboratoire IA 2, Rue de la Liberté, 93526 Saint-Denis Cedex, France. Email: cazenave@ai.univ-paris8.fr