TABLE OF CONTENTS

 

Table of Contents.................................................................................................................................................................. 53

The Interpretation of Rules (H.J. van den Herik) ............................................................................................................. 53

A New Implementation of Error Analysis in Game Trees (U. Lorenz)........................................................................... 55

Computer Analysis of World Chess Champions (M. Guid and I. Bratko)................................................................... 65

Notes:    .................................................................................................................................................................................. 74

                Never-Ending Moves in Bao (T. Kronenburg, H.H.L.M. Donkers, and A.J. de Voogt)............................. 74

                Chess Endgame News (G.McC. Haworth).......................................................................................................... 79

Review: ................................................................................................................................................................................... 80

                Finally, History Repeats Itself Correctly  (D. Hartmann) ................................................................................ 80

Information for Contributors................................................................................................................................................ 82

News, Information, Tournaments, and Reports:............................................................................................................... 83

                The 14th World Computer-Chess Championship (H.J. van den Herik and J.W. Hellemons)...................... 83

                        Hardware Overview (Y. Björnsson)............................................................................................................ 94

                        The 11th World Computer Speed-Chess Championship ......................................................................... 94

                The 11th Computer Olympiad  (H.J. van den Herik and J.W. Hellemons)...................................................... 95

                        Crazy Stone Wins 9x9 Go Tournament (R. Coulom and K. Chen)................................................... 96

                        GnuGo Wins 19x19 Go Tournament (R. Coulom and K. Chen)............................................................. 98

                        NeuChess Wins Chinese-Chess Tournament (S-J. Yen and S-C. Hsu)............................................ 100

                        TD King Wins Draughts 10x10 Tournament (T. Tillemans)................................................................ 102

                        Yss Wins Shogi Tournament (T. Hashimoto)........................................................................................ 105

                        Pan Wins Clobber Tournament (M. Winands)..................................................................................... 106

                        Darkboard Wins Kriegspiel Tournament (P. Ciancarini and G.P. Favini).................................... 108

                The 6th International CSVN Tournament (Th. van der Storm)....................................................................... 110

                Calendar of Computer-Games Events in 2006.................................................................................................. 111

                The 5th Computer and Games Conference 2006 (M. Guid)............................................................................. 112

                The ICGA Treasurer’s Report for 2005 (H. Iida)............................................................................................. 113

                The 2004 and 2005 ICGA Journal Award Recipients (The Board of ICGA) ............................................... 114

                MICC-IKAT (H.J. van den Herik) ..................................................................................................................... 114

                The Swedish Rating List (T. Karlsson)............................................................................................................. 115

How the ICGA Journal Reaches You................................................................................................................................ 116

 

 

THE INTERPRETATION OF RULES

 

The origin of computer chess is – as we all agree – in von Kempelen’s Turk, for the first time presented to Maria Theresia at the Court in Vienna in 1769.  After this occasion we have seen many developments in the form of (a) successors such as Ajeeb and Mephisto, (b) novels on the topic, for instance by Edgar Allen Poe, (c) the development of mechanical techniques (cf. Babbage and Torres y Quevedo), and (d) computer technology (from Shannon to the performances in the Olympic Oval). Primarily, we see inspired and inspiring scientists standing on each other’s shoulders to design an even better device.

 

Scientists have the duty to publish their findings while for commercial ventures it is debatable (cf. the Microsoft case in the European Union); only competitors for the World Computer-Chess Champion title may have their secrets. Yet, in the latter case we enter a difficult area. Clearly, a stolen program should be excluded from competition. This is rather simple (at least in theory). A software program is tangible or material, and so it can be traced, but how about ideas? They are vague and sensible, but also understandable and many times implementable. Is there a copyright, a patent, or another legal security issue? And how would our community deal with it?

 

As a Tournament Director, I have experienced several of the issues mentioned above. In the 9th World Microcomputer Chess Championship (Portorož, 1989), the program Quickstep by Mr. Langer was excluded from further participation after four rounds. The reason was that the program was “an unauthorized version of the Mephisto Almeria program” (cf. ICCA Journal, Vol. 12, No. 4, pp. 232-236). In the 11th WCCC (Graz, 2003) the author of the program List refused inspection of his program code and was banned from the tournament for precisely this reason (cf. ICGA Journal, Vol. 26, No. 4, pp. 252-259).

 

Over the years the Board of ICGA have learned their lessons, but nevertheless they stumbled into a new case in the 14th WCCC. The story is too long for an editorial, but it is indicative for the attractiveness of computer chess and for the desire to achieve a top position in that world.

 

The Lion++ 1.5 team made use of Fabien Letouzey’s program Fruit. Fruit is composed from open-source software and it unexpectedly finished in a second place in the 13th WCCC in Reykjavik, Iceland, last year. The Lion++ 1.5 team members are honest people, they had checked our ruling with their legal advisors. It deals with rule 2 (see Vol. 29, No.1, p. 48) that states: “Each program must be the original work of the entering developers. Programming teams whose code is derived from or including game-playing code written by others must name all other authors, or the source of such code, in their application details. Programs which are discovered to be close derivatives of others (e.g., by playing nearly all moves the same), may be declared invalid by the Tournament Director after seeking expert advice. For this purpose a listing of all game-related code running on the system must be available on demand to the Tournament Director.”

In the tournament report (pp. 83-93) you will find that one of the participants made a protest against Lion++ 1.5. After inspection by Yngvi Björnsson and later (independently) by Jonathan Schaeffer it was clear that the code was similar to Letouzey’s. However, the remarkable thing was that the Lion++ 1.5 team members did not deny this fact, but pointed: (a) to the credit for Letouzey as mentioned in their files, and (b) to all the newly developed routines which surrounded the ideas by Letouzey. Their interpretation of rule 2 diverged in three aspects from my interpretation. The aspects are: (1) original work, (2) application details, and (3) close derivatives. I discuss the three points briefly below.

(Ad 1) “original work of the entering developers”. If they had included Fabien Letouzey (with his permission) in the list of authors, there would have been no concerns. Since they had not done so, the discussion was on “original work”. Clearly, the main part of the program Lion++ 1.5 was not their original work. However, rule 2 had five more lines, which the team perceived as an explanation of the notion “original” (see ad 2 and ad 3).

(Ad 2) “must name (....) in the application details”. The Lion++ 1.5 team had interpreted “application” as ‘program’ and therefore they had included a file crediting the effort by Fabien Letouzey. Well done, but invisible for other people. Of course, the ICGA board had meant the ‘submission form’ should contain these names and credits. Then they could decide whether they would admit the program.

(Ad 3) “to be close derivatives”. Here the legal question arises: what is meant by “close”. The chief arbiter of the human Chess Olympiad, Geurt Gijssen, who has ample experience with World Championship matches, was consulted for interpretation. He pointed to the fact that when ‘close’ would mean “over 80 per cent”, it should be stated that way. Yet, the interpretation by Björnsson and, independently, by Schaeffer was that it was “a close derivative”.

 

For long-standing members of our community – we assume – the above the interpretation of the rules is clear. In Turin, the ICGA had the pleasure to welcome some new members who became three-year members according to the rules for participating in a WCCC. So far, we believed that the three-year rule was a rule for the continuity of the membership, now we know that this rule should be interpreted as a rule for familiarisation with the ICGA community.

 

Disregarding the Lion++ 1.5 misinterpretation of the rules, the Turin event was wonderful and the pages of the second half of the Journal report colourfully on these events. However, with so many reports we had to postpone some of them to the September issue of which the scientific part will be dedicated to the game of Poker.

 

Jaap van den Herik

 

 

 

The credits of the photographs in this issue are to Rémi Coulom, Tsuyoshi Hashimoto, Johanna Hellemons, Jahn Takeshi Saito, Kees Sio, Ton Tillemans, and Shi-Jim Yen.

 

A NEW IMPLEMENTATION OF ERROR ANALYSIS IN GAME TREES1

Ulf Lorenz2

 

Paderborn, Germany

 

ABSTRACT

Game-tree search is the core element of most attempts to make computers play games. Yet another

approach is (1) to store all possible positions in a database, (2) to precompute the true values for all

the positions, and (3) to extract a move with the help of a depth-one search. The databases allow

computers to play optimally, in the sense that they will win every game once they have reached a

winning position. Moreover, they will never lose from a drawn or won position. We find the database

approach in games such as Nine-Men’s-Morris and Connect-4, in endgames of chess, and in many

other settings. Nevertheless, it has been observed that the database programs do not play strongly

when they have to play a tournament with strong, but non-perfect human players attending.

In this paper, we will present an algorithm which has the perfect knowledge of a game database

as input, and whose task it is to bring an opponent without perfect knowledge into trouble. The

proposed method exploits a specialised game-tree search on top of the database. More precisely, we

perform an extended local look-ahead, although the true values of all positions are known. The idea is

borrowed from a known theoretical error analysis in game trees. It emphasises that the combinatorial

structure of the tree underlying a given position determines how difficult it is for a fallible opponent

to find a correct answer. Our experiments show encouraging results.

 

 

COMPUTER ANALYSIS OFWORLD CHESS CHAMPIONS1

 

Matej Guid2 and Ivan Bratko2

 

Ljubljana, Slovenia

 

ABSTRACT

Who is the best chess player of all time? Chess players are often interested in this question that

has never been answered authoritatively, because it requires a comparison between chess players

of different eras who never met across the board. In this contribution, we attempt to make such a

comparison. It is based on the evaluation of the games played by the World Chess Champions in

their championship matches. The evaluation is performed by the chess-playing program CRAFTY.

For this purpose we slightly adapted CRAFTY. Our analysis takes into account the differences in

players’ styles to compensate the fact that calm positional players in their typical games have less

chance to commit gross tactical errors than aggressive tactical players. Therefore, we designed a

method to assess the difficulty of positions. Some of the results of this computer analysis might be

quite surprising. Overall, the results can be nicely interpreted by a chess expert.

 

 

NEVER-ENDING MOVES IN BAO1

 

Tom Kronenburg [1], Jeroen (H.H.L.M.) Donkers1, and Alex J. de Voogt[2]

 

Ljubljana, Maastricht, The Netherlands


ABSTRACT

For this purpose we slightly adapted CRAFTY. Our analysis takes into account the differences in

Bao is a member of the large family of mancala games. It is generally considered to be the most complex mancala game with respect to the number of game rules (Townshend, 1986; De Voogt, 1995). Within the context of this note, it is impossible to describe the rules of Bao in their full length, so we restrict ourselves to the main discriminative characteristics, and to those rules that are necessary to understand the note. The complete rules for Bao can be found in De Voogt (1995) and also, adapted to computer Bao, in Donkers et al. (2005).  

An interesting question for Bao players is whether there are never-ending moves in Bao. The Bao masters of Africa do not believe that Bao can produce a never-ending move (De Voogt, 1995, p. 38). In contrast, Donkers and Uiterwijk (2002) argue that there is a high probability that a never-ending move does occur in real game play. In this note we present an overview of never-ending moves; we discuss both trivial and complex never-ending moves. Moreover, we also show a never-ending move that occurs during a game of Bao. Finally, the implications of never-ending moves to the rules are discussed.

 


[1] MICC-IKAT, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands.
Email: tom.kronenburg@gmail.com; donkers@micc.unimaas.nl.

[2] Department of Experimental Psychology, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands. Email: alex.devoogt@psychology.unimaas.nl.