FROM GRAZ TO RAMAT-GAN

On our way from Graz to Ramat-Gan we would like to consider the state of the art of game-playing programs. We do so in retrospect to the events in Graz, Austria, and in prospect to the upcoming events in Ramat-Gan, Israel. Science is en route, programs are improving month by month and the end is still unpredictable, but some milestones are foreseeable, certainly the milestones on our research agenda.

The ICGA is flourishing and in full swing. The events in Graz were a big success. There we welcomed three new World Champion programs, viz. in Chess, Backgammon, and Poker. The title is important not only for the authors of the programs, but for the ICGA too, since we are trying to promote more matches between the silicon champions and the human World Champions of the games involved. Therefore, we congratulate the authors and collaborators of the programs Shredder, Bgblitz, and Vexbot. In passing we mention that Shredder succeeded in winning the 2003 World Computer Speed Chess Championship, too.

Next to the computer World Champions, we would like to honour the new Olympic Champions, 10 in total (11 when RoShamBo is included). They represent the true spirit of the Olympic ideas: come together, challenge each other's program, and learn from your opponent. In Graz, there were many things to learn, in particular since the 10^th Advances in Computer Games conference took place in three morning sessions anticipating the heroic contests of the afternoons and evenings in the Dom im Berg (the 11^th WCCC) and in the Casineum (the 8^th Computer Olympiad). This issue reports on the WCCC, the Computer Olympiad, and the ACG-10 conference. A review of the ACG-10 proceedings will appear in the next issue. In all reports the Graz organizing committee is gratefully acknowledged and your Editor concurs with this gratitude. In particular he would like to thank Professor Jungwirth and Walter Kastner.

Meanwhile, on the horizon we see Ramat-Gan, a lovely place in Israel, near Tel Aviv. The ICGA is indebted to Professor Nathan Netanyahu and Omid Tabibi for taking on the challenging tasks of organizing a three-event ICGA activity. This time it will be: the 12^th World Computer-Chess Championship, the 9^th Computer Olympiad, and the 4^th Computer and Games Conference (usually called CG 2004). The events will take place from July 4 to July 12, 2004. For details and web links we refer to their contribution (on page 293) and to the Calendar of computer-games events in 2004 (this issue, p. 294).

A few questions raised in the previous Editorial remain to be answered, as other points need attention too; they will be discussed below. Obviously, it is not yet the time to state that computer-chess programs have definitively surpassed the human players (Fritz only drew last month with Kasparov in New York; see David Levy's report on pp. 288-289). Moreover, the expected five best programs of Graz turned out to be only four, or should we say three? In the end, two programs had the right to state that they were the best. The final result, i.e., Shredder wins the World Champion title, did not alter my opinion on the two best programs.

The Tournament Director had a tough time in Graz. He was facing an official protest of one of the participants on the authenticity of the programming code of another program. Fortunately, we had rules for inspection and so he could handle this affair convincingly (see the report by Omid Tabibi, in this issue pp. 252-259). Moreover, we had the three-times-repetition issue and the right to claim a draw. Serious questions as (1) "Who should claim?", (2) "When should it be claimed?" and (3) "Is it a right or a duty to claim?" were the subject of a passionate debate. Questions (2) and (3) are answered by the FIDE rules and as such they are part of the ICGA rules for competition. As to question (1) it all comes down to: should the program claim a draw or the operator? If the program claims it, then it should be a claim and not an observation, and the move to be played should be announced and not executed on the board. If we allow the operator to claim it – this may be the case if the program does not have a claim feature – then it should be a right and not a duty. Of course, moral aspects exist and should be taken seriously into account. Yet, the current ruling is clear, fair, and transparent.

The dates of submitting contributions to the CG conference and of submitting programs to the Computer Olympiad and the World Computer-Chess Championship are approaching. We have published announcements on the Web and invited you to reply to these announcements. In this issue, we have given priority to the publication of the reports on the Graz events above the new announcements.

Owing to the pairings of the last rounds in the 11^th WCCC and the corresponding outcomes, the ICGA currently reconsiders the scheduling procedure of the future World Computer-Chess Championships. It may be changed into five rounds according to the Swiss system (in one or two groups) and thereafter sudden-death matches for the best four to eight programs. The other programs then will, of course, complete the full 11-round tournament (maybe together with the programs that lost their matches). By all these changes we should never forget that in the early times of computer chess, the World Championship title was decided in five games only. The world has changed, the playing strength too; the ruling and scheduling should not remain behind. The current developments predict a beautiful clash of silicon thoughts on chess and games. Therefore, we look forward to Ramat-Gan .

Jaap van den Herik

 ABALEARN: A PROGRAM THAT LEARNS HOW TO PLAY ABALONE
 

Thibault Langlois¹ and Pedro Campos²

ABSTRACT

The article describes Abalearn, a self-learning Abalone program capable of automatically reaching an intermediate level of play. This is achieved without expert-labelled training examples, deep searches, and exposure to competent play.

Our approach is based on a reinforcement-learning algorithm that is risk seeking, since defensive players in Abalone tend to postpone a game endlessly. We show that risk sensitivity allows a successful self-play training. Moreover, we propose a set of features that seem relevant for achieving a rather skilled level of play.

We evaluate our approach using a fixed heuristic opponent as a benchmark. We pit our agents against human players on-line and compare samples of our agents at different times of training.

¹ Faculdade de Ciências da Universidad de Lisboa (FCUL), Departamento de Informática, Campo Grande, 1749-016 Lisboa, Portugal, email: tl@di.fc.ul.pt.
² Universidade da Madeira, Departamento de Matematica e Engenhiaria (INEGC-ID), 9000-390 Funchal, Portugal, email: pcampos@uma.pt.

THE PERFECT 7-PIECE CHECKERS DATABASE

E. Trice and G. Dodgen

Hatfield, Pennsylvania, USA
 

ABSTRACT

Many research teams and individuals have computed endgame databases for the game of chess which use the distance-to-mate metric, enabling their software to forecast the number of moves remaining until the game is over. This is not the case for the game of checkers. Only one programming team has generated a checkers database capable of announcing the distance to the terminal position. This note examines the benefits and detriments associated with computing three different types of checkers endgames databases, demonstrates a 253-ply solution to the longest win in the 7-piece checkers database, and demonstrates a winning improvement to a common checkers ending dating back to 1756.

This note is an abbreviated and updated version of the article The 7-piece perfect play lookup database for the game of checkers published in Advances in Computer Games – Many Games, Many Challenges (eds. H.J. van den Herik, H. Iida, and E.A. Heinz), pp. 211- 230. It is partly republished here with the permission of the authors, editors, and publisher for which the Editorial Board of the ICGA Journal would like to thank the persons involved.

Gothic Chess Federation. GothicChessInfo@aol.com; GilDodgen@cox.net, www.GothicChess.org.

 SUPERCHESS
 

H. van Haeringen¹ and H.J. van den Herik²

ABSTRACT

Superchess is a natural and flexible extension of chess. It contains additional pieces which results in additional possibilities in game playing. One of the advantages definitely is that (so far) theoretical knowledge, in particular of the opening phase, is subaltern. Until now chess is one of the most satisfying and successful thinking games in the world of games. To some extent the chess pieces and their movements are chosen in an arbitrary process of historical development; the same holds for the initial position of the pieces on the board. In chess different pieces have different movements. This observation may lead to the scientifically intriguing question of the optimality of chess. Can we imagine chess-like games that are equally well or even more satisfying than chess? If the answer is affirmative, then the question arises, how can we determine such games?

The note briefly discusses various aspects of optimal games and possible modifications of chess. In particular, the benefits of superchess are advocated: new pieces possessing new movements in combination with (a part of) the generally accepted chess pieces. The new movements introduce fascinating new tactical combinations, whereas the character of chess is essentially preserved. Opening theory plays no role in practice because of the large number of different initial positions. The players' freedom to select a different set of pieces in each new game constitutes another appealing feature. Finally, the most challenging task is, of course, to transform the current chess-playing programs into superchess-playing programs of considerable strength.

¹ Delft University of Technology, Faculty of Electrical Engineering, Mathematics and Computer Science, Dept. AMA, Mekelweg 4, 2628 CD Delft, The Netherlands. Email: superchess@planet.nl. Websites: www.superchess.nl and www.superschaak.nl.

² IKAT, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands; Rommesingel 42, 2641 VJ Pijnacker, The Netherlands. Email: herik@cs.unimaas.nl.