ICGA Journal

Vol. 26, No. 1 - March 2003

Table of Contents

Table of Contents1
Many Games in Graz (H.J. van den Herik) 1
Increasing Interest (K-H. Chen) 2
The State of the Art in Man vs. "Machine" Chess (D.N.L. Levy) 3
Man Equals Machine in Chess (K. Müller) 9
The Move-Decision Strategy of INDIGO (B. Bouzy) 14
Optimizing GOTOOLS' Search Heuristics using Genetic Algorithms (M. Pratola and T. Wolf) 28
Review:49
Behind Deep Blue (D. Hartmann) 49
Information for Contributors52
News, Information, Tournaments, and Reports:53
Volkov vs. Shredder (M. Müller) 53
The Match Bareev vs. Hiarcs X (J. van Reek and J.W.H.M. Uiterwijk) 55
The 12th International Paderborn Computer-Chess Championship (V. Diepeveen) 57
Report on the Game-on 2002 Conference (P. Spronck) 59
ICGA's Activities in Graz (The Board of ICGA) 60
Rules for the 11th World Computer-Chess Championship (The Board of ICGA) 62
 Calendar of Computer-Games Events in 2003 64
 ICGA Treasurer's Report for 2002 (Treasurer ICGA Board) 65
 The ICGA Chess-Program Rating List (D. Levy) 66
 A Call for Standards in Amazons Notation (R.J. Lorentz) 68
 The ICGA Journal Referees of 2002 69
Call for Participation: The Open Championship Computer Roshambo (J. Donkers) 70
The Swedish Rating List (T. Karlsson)71
How the ICGA Journal Reaches You72

 

MANY GAMES IN GRAZ

In November 2003, the capital of Styria will produce a new contender for FIDE's latest World Champion of chess. The latter will be decided in 2003, too. The battle among humans for the highest ranked position in the chess world is very interesting, in particular since it deals with all kind of elements, such as psychological statements and refusals of potential playing opportunities and of prize money (too low). In the 11th World Computer-Chess Championship to be held in Graz, Styria, Austria, we expect a clash of opponents, too. The favourites are: Deep Junior, Deep Fritz, Shredder, and Brutus. However, the Paderborn tournament (see pp. 57-58) shows that YACE, SOS, GANDALF, and DIEP may be disturbing co-competitors for the title.

Next to the 11th WCCC, the City of Graz will host the 8th Computer Olympiad and the 10th Advances in Computer Games Conference (ACG10). At the Computer Olympiad we will see competitions in a variety of games. We expect Amazons, Backgammon, Bridge, Checkers, Chinese Chess, Dots and Boxes, Draughts, Gipf, Go, Hex, Lines of Action, Othello, Roshambo, and Shogi. We invite participants on other games, e.g., Poker. More information is in this issue and at www.icga.org.

Disregarding the future events announced above, this issue reports on the great success by the Deep Junior team in their human vs. machine contest against Gary Kasparov. Amir Ban and Shay Bushinsky achieved a well-deserved tie, 3 to 3. The machine's score was: 0, ½, 1, ½, ½, ½. When written in this form, it does not look impressive, but as a reader you are invited to follow the match move by move (see pp. 9-13) and you will see that playing at a par with the World Champion is quite a performance. Moreover, we recommend reading David Levy's account on his personal thoughts during the match. Levy describes new vistas and relates them to old sayings by famous chess Grand Masters. Kasparov's mistakes are meticulously revealed and advice for a next match is provided. This is the current state of the art: machines are able to teach Grand Masters on the strategy they should follow. In summary, Deep Junior is a worthy successor of Deep Blue. (We recall the results of the Kasparov matches: 1996: 2 – 4; 1997: 3.5 – 2.5, and of Deep Fritz (playing 4 – 4 against Kramnik)). The ICGA congratulates Amir Ban and Shay Bushinsky with their results and thanks them for being such outstanding representatives of the games community.

Jaap van den Herik


INCREASING INTEREST

Keh-Hsun Chen1

The game of Go is a tantalising challenge for human beings. Although the rules of the game are easy to learn and the goal to reach can be defined straightforwardly, strong human Go players have considerable difficulties in explaining the strategies they follow. Usually computer-Go programmers are not the best Go players of the world. So, the question emerges: where should the programmers start with their programming? In the previous issue of the ICGA Journal, a special issue dedicated to Go, we saw three diffferent approaches of important elements in Go programs, viz. (1) the life-and-death problems by David Fotland, (2) the estimation of the influence of a wall by Zhixing Chen, and (3) the position evaluation by Martin Müller. As a Guest Editor I am pleased to have been given the opportunity to continue my work, so that I can introduce two more refereed articles on Go published in this issue.

The first Go article is by Bruno Bouzy; it is titled The Move-Decision Strategy of INDIGO and provides an example of the organization and move-decision strategy of Go programs. Some modules, such as pattern matching, block-capturing tactics, and group life-and-death search, are so essential that they can be found in almost every Go program. It is instructive to learn how Bouzy has composed its modules and which domain-independent and domain-specific knowledge he uses.

The second article by Matthew Pratola and Thomas Wolf is titled Optimizing GOTOOLS' Search Heuristics using Genetic Algorithms. Thomas Wolf's life-and-death problem solver, GOTOOLS, has long been the envy of the computer-Go world. It is the only program in the Go domain that has reached human expert level. However, GOTOOLS does not play a full Go game; it is specifically designed to solve life-and-death problems with a closed boundary. The current article discusses how the authors use genetic algorithms to tune up the performance of GOTOOLS. We hope to see soon that the tool is able to solve open boundary life-and-death problems in Go.

This continuation of the special issue is meant as appetiser for the computer games community to shift some attention to Go. In his review of Feng-hsiung Hsu's book Behind Deep Blue, Dap Hartmann emphasises that Hsu is a passionate Go player, but the Deep Blue programmer believes that "the game is too hard for a computer at the moment". That is exactly the challenge we are facing and the driving force of our research.


1 Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223, USA. Email: chen@uncc.edu.

THE STATE OF THE ART IN MAN VS. “MACHINE” CHESS

David Levy

ABSTRACT Watching DEEP JUNIOR’s output from the beginning to the end of all six games of its match against Kasparov was both an exciting and an instructive experience. During such an experience any serious chess player will have several thoughts about the program he is watching and about chess programming in general. This article summarizes the author’s own thoughts and ideas during the match.


MAN EQUALS MACHINE IN CHESS

K. Müller

ABSTRACT The world has been eagerly waiting for Kasparov to challenge a computer again to take revenge after his famous loss against IBM’s DEEP BLUE in New York, 1997 (Seirawan, 1997). The programmer’s side of the story has just been revealed in Hsu’s (2002) book Behind Deep Blue. In view of Kramnik’s good start in his match against DEEP FRITZ in Bahrain 2002 (cf. Müller, 2002), where, in the end the computer fought back to 4-4, most commentators thought that Kasparov would win against DEEP JUNIOR in the first official FIDE/ICGA Man vs. Machine World Chess Championship. But the two Israeli programmers Amir Ban and Shay Bushinsky have obviously succeeded in creating a dangerous opponent for the world’s highest rated player and in a match over only six games, one loss may prove decisive. So it was very important that Kasparov scored the first full point as Kramnik did in his Man vs. Machine match. The following analysis is based on my notes for www.chessbase.de.


THE MOVE-DECISION STRATEGY OF INDIGO

Bruno Bouzy1
Paris, France

ABSTRACT This paper describes the move-decision strategy of the Go program INDIGO. It shows that the move-decision process of a Go program can be very different from the processes in other games with a lower complexity than Go. Even though the basic modules are conventional (move generator, evaluation function, and tree search), INDIGO uses them in a specific way, viz. adapted to computer Go. The strategy may be of interest to researchers on other mind games that are as complex as Go. The evaluation function can be “fast”, “slow” or “strategic”. It may include local tree search. The move generation brings about different kinds of moves: “urgent” moves, “life-and-death” moves and “calm” moves. Urgent moves are statically qualified with a global urgency. A two-player quiescence search verifies that the urgent move does not decrease the position evaluation. Calm moves are used within two-player selective global search at a very low depth. Besides, INDIGO also uses single-agent search to refine the strategic importance of the goals. Lastly, INDIGO chooses one out of three (the calm move, the life-and-death move, and the urgent move) to be the global move.


1 C.R.I.P.5, UFR de mathématiques et d'informatique, Université Paris 5, 45 rue des Saints-Pères 75270 Paris Cedex 06 France. Email: bouzy@math-info.univ-paris5.fr.

OPTIMIZING GOTOOLS’ SEARCH HEURISTICS USING GENETIC ALGORITHMS

Matthew Pratola1 and Thomas Wolf2
St. Catharines, Ontario, Canada

ABSTRACT GOTOOLS is a program which solves life-and-death problems in the game of Go. This paper describes experiments using a Genetic Algorithm to optimize heuristic weights used by GOTOOLS’ tree-search. The complete set of heuristic weights is composed of different subgroups, each of which can be optimized with a suitable fitness function. As a useful side product, an MPI interface for FreePascal (Message Passing Interface) was implemented to allow the use of a parallelized fitness function running on a Beowulf cluster. The aim of this exercise is to optimize the current version of GOTOOLS, and to make tools available in preparation of an extension of GOTOOLS for solving open boundary life-and-death problems, which will introduce more heuristic parameters to be fine-tuned.


1 Department of Computer Science, Brock University, Canada, Email: mp00aa@sandcastle.cosc.brocku.ca.
2 Department of Mathematics, Brock University, Canada, Email: twolf@abacus.ac.brocku.ca.