ICGA Journal

Vol. 23, No. 3 - September 2000

Table of Contents

Table of Contents 129
The Olympiad (H.J. van den Herik) 129
Large Endgame Databases with Limited Memory Space (T.R. Lincke and A. Marzetta) abstract 131
Solving Kalah (G. Irving, J. Donkers, and J.W.H.M. Uiterwijk) abstract 139
Space-Efficient Indexing of Endgame Tables for Chess (E.V. Nalimov, G.McC. Haworth, and E.A. Heinz) abstract 148
Information for Contributors 163
News, Information, Tournaments, and Reports: 164
The Fifth Computer Olympiad (H.J. van den Herik) 164
SHREDDER wins the 17th WMCC (T. King) 165
MARVIN wins Awari Tournament (T.R. Lincke and R. van der Goot) 173
GOEMATE wins Go Tournament (N. Wedd) 175
YL wins Lines of Action Tournament (Y. Björnsson) 178
8QP wins Amazons Tournament (P. Hensgens and J.W.H.M. Uiterwijk) 179
HEXY wins Hex Tournament (V. Anshelevich) 181
YSS wins Shogi Tournament (H. Iida) 184
Report on the Computer-Games Workshop (J.W.H.M. Uiterwijk) 186
P.CONNERS wins the 10th Grandmaster Tournament in Lippstadt (U. Lorenz) 188
A One-sided Advanced Chess Match. Part 1: The Games (I. Althöfer) 192
Calendar of Computer-Games Events in 2000-2002 198
The Swedish Rating List (T. Karlsson) 199
How the ICGA Journal Reaches You 200

 

THE OLYMPIAD

Let us pledge a toast to the fifth Computer Olympiad. It is a joyful occasion that the Olympiad has been revived and that there are now discussions on how to broaden its scope. Yet, some purists may query the name Olympiad, since the origin goes back to the Olympic Games. The ancient Greeks coined the Olympiad as the four-year interval between the celebrations of the games. Later on, the notion was used, and still is, for the celebration itself.

Be that as it may, as early as in 1927 the chess world adopted the popular name Olympiad for their FIDE World Team Championships, which were usually held at two-year intervals. There have been several attempts to link Chess with the Olympic Games; the first was in Stockholm, Sweden in 1912 and the last in Sydney, Australia in 2000. In 1912 (and also in Paris in 1924) the chess world was not prepared to distinguish between amateurs and professionals. In 2000, some demonstration games of two top Grandmasters were played. However, neither in the circles of Antonio Samaranch, nor in those of Kirsan Ilyumzhinov was there much enthusiasm for Chess as Olympic Game. So, now both groups are waiting to see what their leaders decide for the future.

Obviously, the notion 'Olympiad' has a magic sound. Therefore, the games community was grateful to David Levy when he launched the first Computer Olympiad in Park Lane Hotel in London, 1989. Sixteen games1 competed and Chess was only one of them. This Olympiad was as great a success comparable to the first Chess Olympiad.

Although there was but one year's interval, the next Computer Olympiad in 1990 was a worthy successor. Competitions were held for fourteen games, new participants being Nine-Men's Morris and Qubic. These two games retained the status of Olympic Games only for two years, when Qubic was solved (for insiders: solved again) and Nine-Men's Morris followed suit somewhat later. In the Olympiads of Maastricht (1991) and London (1992) thirteen games competed, with one newcomer in London: Ginrummy. Thereafter the energy to organize such an event dwindled, mainly because it was difficult to find major sponsors interested in computer games with cognitive processes. This was embarrassing for the competitors and the organizers, but it looked like the tide had turned off further development.

Meanwhile, the Mind Sports Olympiad (MSO) proved to be quite successful. The MSO established itself as an Olympiad for talented people, who were (very) skilled players of connection games such as Hex and Twixt as well as strategic games such as cards games, Chess and Kalah.

Apparently, in the year 2000 everything turned out for the best. First, the ICGA Journal was established as a successor of the ICCA Journal, encouraging researchers to publish their results over a broad spectrum of games. Second, the organizers of the MSO and of the new uniform platform World Microcomputer Chess Championship suffered so many setbacks that they shifted their attention towards a fifth Computer Olympiad, including the 17th World Microcomputer Chess Championship. Therefore, this Olympiad was announced rather late, so that there were only contests in seven games. Even so, four games were newcomers, viz. Amazons, Hex, Lines of Action, and Shogi (Japanese chess).

Over the five Computer Olympiads we have seen a number of 23 games in total. Four of them have been solved so far (Connect-Four, Qubic, Go-Moku, and Nine-Men's Morris); two are on the list of games to be solved soon (Awari and Renju). Of the seventeen remaining games, I expect four to be solved (Othello, Hex, Lines of Action, Checkers) in the next decade if students and researchers continue their persistent research work.

This issue of the Journal is intended to encourage researchers in two respects. First, by providing a tournament-by-tournament account of the fifth Computer Olympiad. Second, by the scientific part that aims at solving games. For Awari and Chess the focus is on subgames; for several mancala games the objective is to make an inventory of the distinct configurations solved, including the game of Kalah. Several new techniques have emerged from these research projects. In passing we note that in Chess the subgames are still endgames, but in Awari the 35-, 36- and 37- stone databases discussed can hardly be called endgame databases, since the whole game contains 48 stones. So, in Awari a relatively small gap remains to be bridged. Here too, the competition is open. This means that the ICGA Journal is very eager to hear about the research progress of the groups in Zürich, Switzerland and Edmonton, Alberta. As Editor I hope that the sixth Olympiad will be held in 2001 and that it will be the last to include Awari. This might be a bit optimistic, but should not be impossible.

Finally, I would like to congratulate Stefan Meyer-Kahlen on the prolongation of SHREDDER's World Microcomputer Chess Championship. As we understand, the title prolongation and the way the program arrived at this result fulfilled the author's ambitions and inspired him to challenge World Champion Garry Kasparov to a match. With bated breath we are waiting to see what happens after the Kasparov-Kramnik match. Will SHREDDER be ready for the top?

Jaap van den Herik

1 The games were: Awari, Backgammon, Bridge, Chess, Chinese Chess, Connect-Four, Dominoes, 8x8 Draughts (also called Checkers), 10x10 Draughts, 9x9 Go, 19x19 Go, Go (Wei-Ch'i), Go-Moku, Renju, Reversi (Othello), and Scrabble.


 

LARGE ENDGAME DATABASES WITH LIMITED MEMORY SPACE

Thomas R. Lincke1 Ambros Marzetta2

Zürich, Switzerland

ABSTRACT


In awari, a larger endgame database improves the playing strength of a game engine significantly, since even shallow searches reach positions where many stones have been captured. For example, in more than 15 percent of the positions reached by an 18-ply search from the start position, 14 or more of the 48 stones have already been captured.

It is unfortunate that (1) awari databases are large compared to today's main memory sizes (the 36-stone database requires 17.5 GBytes), and (2) conventional database-calculation algorithms access the data\-base in a non-local fashion, so that caching becomes useless and disk I/O becomes the bottleneck of the calculation.

In this paper we present a disk-I/O-efficient algorithm for awari endgame-database construction requiring one bit per position in main memory. Then we refine the algorithm by introducing a dual indexing scheme which increases disk-access locality and improves caching performance, so that even larger databases can be calculated.

With these algorithms, we calculated all databases up to the 35-stone database (13.5 GBytes) on a 1 GByte machine. The 36-stone (17.5 GBytes) and 37-stone databases (22.5 GBytes) are under construction.


1 ETH Zürich, CH-8092 Zürich. Email: thomas.lincke@inf.ethz.ch.
2 AWK Engineering AG, CH-8050 Zürich. Email: ambros.marzetta@inf.ethz.ch.

 

SOLVING KALAH

Geoffrey Irving1

Pasadena, California

Jeroen Donkers and Jos Uiterwijk2

Maasricht, The Netherlands

ABSTRACT


Using full-game databases and optimized tree-search algorithms, the game of Kalah is solved for several starting configurations up to 6 holes and 5 counters per hole. The main search algorithm used was iterative-deepening MTD(f). Major search enhancements were move ordering, transposition tables, futility pruning, enhanced transposition cut-off, and endgame databases.


1 Student at Computer Science Dept., California Institute of Technology, Pasadena, CA 91125, USA. E-mail: irving@caltech.edu.
2 Dept. of Computer Science, Universiteit Maastricht, Maastricht, The Netherlands. E-mail: {uiterwijk,donkers}@cs.unimaas.nl.

 

SPACE-EFFICIENT INDEXING OF CHESS ENDGAME TABLES1

E.V. Nalimov2, G.M cC. Haworth3 and E.A. Heinz4

USA and England

ABSTRACT

Chess endgame tables should provide efficiently the value and depth of any required position during play. The indexing of an endgame's positions is crucial to meeting this objective. This paper updates Heinz' previous review of approaches to indexing and describes the latest approach by the first and third authors.

Heinz' and Nalimov's endgame tables (EGTs) encompass the en passant rule and have the most compact index schemes to date. Nalimov's EGTs, to the Distance-to-Mate (DTM) metric, require only 30.6 x 109 elements in total for all the 3-to-5-man endgames and are individually more compact than previous tables. His new index scheme has proved itself while generating the tables and in the 1999 World Computer Chess Championship where many of the top programs used the new suite of EGTs.


1 This is an edited version of the presentation by Ernst Heinz, delivered on June 18, 1999 at the Advances in Computer Games 9 Conference in Paderborn, Germany, q.v. the Proceedings of the ACG 9 Conference.
2 Microsoft Corporation, One Microsoft Way, Redmond, WA 98052-6399, USA: eugenen@microsoft.com.
3 ICL, Sutton's Park Avenue, Reading, RG6 1AZ, UK: guy.haworth@icl.com.
4 M.I.T. Laboratory for Computer Science (NE 43-228). 545 Technology Square, Cambridge, MA 02139, USA: heinz@mit.edu.