TABLE OF CONTENTS

 

Table of Contents....................................................................................................................... 1

Cross-fertilization (H.J. van den Herik) ....................................................................................... 1

A Program to Play Kriegspiel (P. Ciancarini and G.P. Favini)....................................................... 3

Using Bitboards for Move Generation in Shogi (R. Grimbergen)................................................. 25

Playing the Right Atari (T. Cazenave)........................................................................................ 35

Note: 43

Fanorona is a Draw (M.P.D. Schadd, M.H.M. Winands, M.H.J. Bergsma, J.W.H.M. Uiterwijk,

and H.J. van den Herik)......................................................................................................................................... 43

Review: 45

Algorithms and Assessment in Computer Poker (D. Hartmann).................................................................... 45

Information for Contributors................................................................................................................................................ 48

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

The Rybka vs. Ehlvest Pawn-Handicap Match (L. Kaufman)..................................... 49

IPCCC 2006: The International Paderborn Computer-Chess Championship (T. Scheuschner) 52

Chess Grandmaster L’Ami against Zappa (J. van Reek and J.W.H.M. Uiterwijk)........ 54

The World’s Smallest Chess Program? (H.G. Muller).................................................... 56

The 15th World Computer-Chess Championship (The Board of the ICGA).................... 58

Rules for the 15th World Computer-Chess Championship (The Board of the ICGA)...... 59

Calendar of Computer-Games Events in 2007-2008..................................................... 61

ICGA Treasurer’s Report for 2006 (H. Iida)................................................................. 62

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

How the ICGA Journal Reaches You.................................................................................................................................. 64

 

 

 

CROSS-FERTILIZATION

 

Two important concepts in the world of science are generalization and specialization. Any researcher who has achieved a research goal by using method X will address the question “is method X applicable in a wider set of domains?” This may be a completely different domain, a related domain, or a domain that is enriched with respect to the original domain (e.g., more complex, more rules, a larger board, etc.). In the section ‘future research’ of the article to be written on the finding, the researcher is expected to make a strong case at such a generalization.

 

Some methods seem to be general, almost by nature, but we remark that the first research attempts must have been performed in some specific domain. As telling examples of general methods, we mention data compression, datamining, filtering, profiling, adaptive learning, and agent technology.

 

Specialization is the other way around. One of the six methods mentioned above may be applied so successfully to a particular domain that it results in a method with its own name, mostly connected to the result of the method. For instance, in the computer-chess world we may speak of Nalimov databases.

 

In the world of science many breakthroughs have been achieved on the dividing line of two or more research areas, sometimes as a direct consequence of generalization, other times as a result of cross-fertilization. Well-known researchers who have achieved successes by generalization or cross-fertilization are John von Neumann (1903-1957) (from mathematics to computer science), Norbert Wiener (1894-1964) (from mathematics to cybernetics), and Jan Tinbergen (1903-1994) (from physics to econometrics). von Neumann and Wiener were established researchers when they founded a new discipline, but Tinbergen was a Ph.D. student at the time. His supervisor Professor Paul Ehrenfest was not amused when the clever Ph.D. student suggested applying newly-developed wave equations in the world of economics so as to characterize the nature of conjunctural waves. In the end they agreed that the Ph.D. thesis should consist of three parts, viz. the thesis with a new theory on the wave equations and two appendices, one with an application in physics and one with an application in economics.[1]

 

In this issue of the Journal we see them all, generalization, cross-fertilization, and specialization. Generalization is shown by Maarten Schadd et al. Well-known methods, such as retrograde analysis and PN search, have been applied to the game of Fanorona. The game is weakly solved, the result is a draw (see pp. 43-44).

 

A clear example of cross-fertilization is seen in Reijer Grimbergen’s article that introduces the use of bitboards for move generation in Shogi. The shogi board is 99 and thus differs in size from the chessboard (where the number of squares is conveniently “designed” to fit in a 64-bit word). Yet, Grimbergen succeeded in using the idea of bitboards (of 81 squares) in an analogous way as used by chess programmers. The result is a large improvement in performance, which will inevitably lead to an improvement in the playing strength of Shogi programs.

 

A form of specialization is found in the article by Ciancarini and Favini, who redefine the concept of a metaposition, earlier introduced by Sakuta and Iida. It is now dedicated to be used efficiently in a game tree of a program that plays the full game of Kriegspiel. So far, in this research domain, most of the programs are restricted to only playing endgames. To show that extreme specialization is also possible, we refer to the article by Cazenave. He reduces the goal of every game programmer “to play the best move” to the effective Go heuristic of “playing the right Atari”.

 

In 1978 Ben Mittman and Barend Swets started the ICCA Newsletter. It was specialized on chess. Owing to the series of Advances in Computer Chess Conferences, which in 1999 changed to Advances in Computer Games Conferences, the ICCA Journal broadened its scope, too, and published articles on other games. This can be seen as a generalization. As a direct consequence, the Journal was renamed into ICGA Journal. Pointing to the successes of this policy we remark that the current issue deals with six different games: Kriegspiel, Shogi, Go, Fanorona, Poker, and Chess. However, the main observation is the successful cross-fertilization as embodied by Reijer Grimbergen’s contribution. Continuing this way of research, we may expect a considerable increase of playing strength in all game programs. In the coming years, our Computer Olympiads may prove this expectation. The next Olympiads are in Amsterdam (June 11 to June 18, 2007) and in Beijing (July 27 to August 3, 2008). I look forward to see the performances of the game programs in these events.

 

Jaap van den Herik

 

 

 

A PROGRAM TO PLAY KRIEGSPIEL

 

Paolo Ciancarini and Gian Piero Favini1

Bologna, Italy

 

ABSTRACT

 

The game of Kriegspiel is a variant of the game of Chess. Kriegspiel is interesting because most chess rules are still valid, but gameplay is characterized by incomplete information as players may not see their opponent’s pieces and can only try to guess their positions by listening to the messages of a referee.

We describe a Kriegspiel-playing program based on the concept of metaposition, that is, the merging of a rather large set of possible game states into a single entity. This merging operation allows us to exploit traditional perfect-information game-theory tools, such as the Minimax theorem. We provide a general representation of Kriegspiel states through metapositions and describe an algorithm for building and exploring a game tree of metapositions. Our method does not assume that the opponent will react with a best defence model. We have evaluated our approach by competing against both human and computer players.

 

USING BITBOARDS

FOR MOVE GENERATION IN SHOGI

 

Reijer Grimbergen

 

Yamagata, Japan

 

ABSTRACT

 

In this paper it will be explained how to use bitboards for move generation in shogi. In chess, bitboards have been used in most strong programs because of the easy representation of a chess board by a single 64-bit integer. For shogi, a less efficient representation has to be used because a shogi board has 81 squares instead of 64. A representation with an array of three integers is proposed, where each integer represents 27 squares of the board. This representation is then used for move generation in a similar way to the methods used in chess, for example by using rotated bitboards for generating the moves of the sliding pieces Rook and Lance. For generating the moves of the Bishop, rotated bitmaps are not completely satisfactory and a different method using the alignment of diagonals is proposed for move generation. A comparison of the move-generation speed between using bitboards and the more common method of using attack tables showed that even without using hardware-dependent optimizations the move-generation speed of the shogi program SPEAR using bitboards was more than 40% faster than the move generation using attack tables.

 

 

 

PLAYING THE RIGHT ATARI

 

Tristan Cazenave

Paris, France

 

ABSTRACT

 

Playing the right atari is an intriguing heuristic that can be used for a powerful optimization of Monte-Carlo Go tree search. It consists in dealing appropriately with strings that have two liberties. The heuristic is contained in one page of code and the Go program that uses it improves from 50 per cent of won games against GNU GO 3.6 to 76 per cent of won games.

 

 

NOTE

 

FANORONA IS A DRAW

 

Maarten P.D. Schadd, Mark H.M. Winands, Maurice H.J. Bergsma,

Jos W.H.M. Uiterwijk, and H. Jaap van den Herik1

Maastricht, The Netherlands

 

1. INTRODUCTION TO FANORONA

Fanorona is the national and indigenous board game originally played in Madagascar. There are three commonly known variants of the game which differ in board size: (1) Fanoron-Tsivy commonly referred to as Fanorona and played on a 59 board; (2) Fanoron-Dimyand played on a 55 board, and (3) Fanoron-Telo played on a 33 board. The initial position of a Fanorona game is depicted in Figure 1. The board is a 59 grid, pieces are placed on the intersections of lines. The players alternately move a stone, starting with White. One is only allowed to move over a line and only to an adjacent point. Capturing is done by approaching or withdrawing opponent stones. It is possible to capture a complete line of opponent stones at once if these stones are positioned on the same line directly behind the approached or withdrawn stone. During a capturing sequence, it is not allowed (1) to arrive at the same position and (2) to move the stone in the same direction as moved directly before in the capturing sequence. Capturing is obliged if possible, moreover, it is allowed to continue capturing with the same stone if possible, but discontinuing the capture is also allowed. The objective of the game is to capture all opponent stones. If both players cannot find a way to win the game by capturing its opponents stones, the game is a draw. For a complete description of the rules and some examples we refer to Schadd (2006) and Chauvicourt and Chauvicourt (1980).

 

Analysis of the game has shown that the game-tree complexity is 1040 and the state-space complexity is 1021. Furthermore, a superficial investigation reveals that the majority of moves is played with only a few stones on the board. Since solving games has always been a great challenge for AI research (Van den Herik, Uiterwijk, and Van Rijswijk, 2002) and since the analysis indicated that Fanorona might be weakly solvable (Allis, 1994), we

decided to undertake this challenge. Next to the standard board, we decided to solve other board sizes too.



[1] I would like to thank Dr. G. Alberts (2007, lecture ICT Delta, Utrecht) for providing the specific information on Jan Tinbergen.