TABLE OF CONTENTS

 

Table of Contents................................................................................................................................................................ 185

Many Friends, Many Differences (H.J. van den Herik) ................................................................................................ 185

Game Over: Black to Play and Draw in Checkers (Jonathan Schaeffer)...................................................................... 187

Computing “Elo Ratings” of Move Patterns in the Game of Go (Rémi Coulom)........................................................ 198

Note: ..................................................................................................................................................................................... 209

                Using the Loopy Belief Propagation in Siguo (Zhengyou Xia, Yongping Zhu, and Hui Lu) ................. 209

Reviews: ............................................................................................................................................................................... 221

                F#ck Your Comp#ter (Dap Hartmann).............................................................................................................. 221

                On the Importance of Self-Contained Papers (Dap Hartmann)..................................................................... 223

Information for Contributors.............................................................................................................................................. 225

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

                Zappa vs. Rybka (Anthony Cozzie)............................................................................................................ 226

                The 27th Open Dutch Computer-Chess Championship (Theo van der Storm) .......................................... 231

                The 2nd Chinese Computer-Games Championship (Shih-Chieh Huang)...................................................... 233

                The 11th Annual World Computer-Bridge Championship (Alvin Levy) ..................................................... 235

                The ICGA Journal Referees 2007....................................................................................................................... 241

                The 10th Joint Conference on Information Sciences (Mark Winands)......................................................... 242

                The 2006 and 2007 ChessBase Best-Publication Award .............................................................................. 243

                Thank you, Tony (Jaap van den Herik and David Levy) ............................................................................. 244

                Thank you, Monty (David Levy and Jaap van den Herik)............................................................................ 245

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

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

Make Sure the ICGA Journal Reaches You..................................................................................................................... 248

 

 

 

Many Friends, many differences

 

There are a variety of researchers in the computer games world. Some of them are friends, others are life-long opponents, but all feel comfortable in a community that now exists for over thirty years. The International Computer Chess Association (ICCA) was established in 1977 at the 2nd World Computer-Chess Championship in Toronto, Canada. In July 2002, the ICCA changed its name into ICGA (International Computer Games Association), broadening its scope towards many other games besides chess. In these settings (ICCA/ICGA) many friendships arose in combination with the exchange of scientific ideas and mutual visits at the universities and institutes involved.

 

Over the years we may distinguish four generations, viz. (1) the founding fathers of computer chess (with Claude Shannon to be mentioned in the first place), (2) the founding fathers of the ICCA (where Ben Mittman was the first President), (3) the established active researchers (among them Jonathan Schaeffer), and (4) the young generation (among them Vasik Rajlich). From the founding fathers Claude Shannon and John McCarthy have been actively involved with our community. Their role was mainly as guests of honour, but they fulfilled that role with great pleasure. They are respected scientists in many domains besides computer games.

 

The three other generations currently form our community. In this editorial I would like to focus the spotlight on four persons who served the ICCA/ICGA as Board members. This implies that my ties as Editor-in–Chief of this Journal are quite close with all four of them: they are my friends.

 

This being so, they are all four very different. Two of them, Tony Marsland and Monty Newborn are now officially stepping down as Associate Editors of the ICGA Journal. The other two, Jonathan Schaeffer and David Levy, have performed two extra ordinary tasks that are reported in this issue. The tasks are very different, but the common theme is that they were able to reach the front pages of many, if not all, daily newspapers around the world.

 

First, we would like to thank Tony and Monty for their longstanding effort to keep the ICCA and the ICCA/ICGA Journal alive. They succeeded very well in this task and without their leadership our community would never have reached our current position. They gave us self respect and convinced the world that Artificial Intelligence in the form of computer chess and computer games would be the start of a change in technology and therefore the start of a change towards a different world. Tony and Monty belong to the second generation which is now starting to reduce their activities in our circles. On the pages 244-246 we provide an overview of their activities within our community.

 

Second, we would like to congratulate Jonathan and David with their performances. Both are friends of mine and of each other. Yet, they are very different and so are their performances. Jonathan and his team succeeded to solve the game of Checkers. A report of his experiences is published in this issue. The game is a draw, assuming perfect play by both sides. He continues his research in the field of Poker. Their attempts to build a world-championship-caliber poker bot reached the front pages too.

 

David Levy took a completely different angle to reach the same result. He shifted his research from chess to the Turing test in general (i.e., he has competed in the Loebner prize competitions, winning in 1997). Then he developed new ideas on what computers can do and what humans are expecting that computers cannot do. The answer is in the area of attachment, physical attachment, love, and sex. His performance is described by Dap Hartmann in a review published in this issue. Whatever your original opinions are when hearing about the topic for the first time, I can assure you that the thesis is very interesting, the ideas are thought provoking and the descriptions deserve to be cited worldwide. I heard that it is a Ph.D. thesis most frequently cited in three months after its defence assuming that newspaper citations also count.

 

Whatever the case, Jonathan and David, the ICGA is happy to have you in our community. We hope to see you at our next events in Beijing, China where we have the 16th World Computer Chess Championship, the 13th Computer Olympiad, and the Computer Games 2008 Conference. I look forward to new breakthroughs, and expect them in the domain of UCT and Monte-Carlo Tree Search (MCTS).

 

 

Jaap van den Herik

 

Text Box: ICGA Journal readers who are interested in information on our publications are referred to our website. A complete list of all articles, notes, and literature reviews published in the ICCA Journal and the ICGA Journal is accessible on the Internet at http://www.icga.org 

The credits of the photographs in this issue are to: Al Levy, Theo van der Storm, and Monroe Newborn.

 

 

Game Over: Black to Play and Draw in checkers

 

 

Jonathan Schaeffer[1]

 

Edmonton, Alberta, Canada

 

 

ABSTRACT

 

In 1989, an effort to solve the game of checkers began. It was naïve because of the daunting size of the search space, 5´1020 positions, and because of computer capabilities of the time. Nevertheless the work continued, with the final calculation completing in 2007. The result? Perfect play by both sides leads to a draw. Checkers is the largest popular game that has been solved to date.

 

 

COMPUTING “ELO RATINGS” OF MOVE PATTERNS IN THE GAME OF GO

Rémi Coulom2

Lille, France

 

ABSTRACT

Move patterns are an essential method to incorporate domain knowledge into Go-playing programs. This article presents a new Bayesian technique for supervised learning of such patterns from game records. The technique is based on a generalization of Elo ratings. Each sample move in the training data is considered as a victory of a team of pattern features. The "Elo ratings" of individual pattern features are computed from these victories, and will be used in previously unseen positions to compute a probability distribution over legal moves. In this approach, several pattern features may be combined, without an exponential cost in the number of features. Despite a very small number of training games (652), this algorithm outperforms most previous pattern-learning algorithms, both in terms of mean log-evidence (2.69), and prediction rate (34.9%). The 19×19 Monte-Carlo program

 

 

NOTE

 

USING THE LOOPY BELIEF PROPAGATION IN SIGUO

 

Zhengyou Xia, Yongping Zhu, Hui Lu1

Nanjing, China

 

ABSTRACT

Siguo is an oriental game with imperfect information. In this note, we suggest using probability in a Bayesian sense to model the uncertainty regarding the opponent’s types of pieces. We use loopy belief propagation for rapid inference and prediction about the piece types of an opponent. Our experimental results indicate that the method can successfully infer the exact type of the opponent’s piece. The ratio of true inference is approximately 48.7%, which is more than elementary players’ inference strength.



[1] Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, T6G 2E8. E-mail: jonathan@cs.ualberta.ca.