TABLE OF CONTENTS

 

Table of Contents................................................................................................................................................................ 181

Overchampion (H.J. van den Herik) ................................................................................................................................. 181

Welcome and Farewell (Editor).......................................................................................................................................... 182

A New Heuristic Search Algorithm for Capturing Problems in Go (K. Chen and P. Zhang).................................... 183

New Approximate Strategies for Playing Sum Games based on Subgame Types (M.M. Zaky, C.R.S. Andraos,

                and S.A. Ghoneim)............................................................................................................................................... 191

Notes:    ................................................................................................................................................................................ 199

                On the Importance of Embracing Risk in Tournaments (D. Billings)........................................................... 199

                Nim is Easy, Chess is Hard – But Why?? (A. Fraenkel)................................................................................ 203

Information for Contributors.............................................................................................................................................. 207

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

                Kramnik vs. Deep Fritz 10 (ChessBase communication)........................................................................... 208

                Shredder Wins Second Chess960 Computer-Chess World Championship (E. van Reem)................. 214

                The 5th Polish Computer-Chess Championship: The Second Comeback of Butcher (M. Szmit)........ 219

                The 26th Open Dutch Computer-Chess Championship (Th. van der Storm)............................................... 220

                The 11th Games-Programming Workshop in Japan 2006 (R. Grimbergen)................................................... 222

The Gifu Challenge 2006 World Computer-Go Championship (S. Soeda, K. Takahashi, and

H. Matsubara) ..................................................................................................................................................... 224

New Website for ICGA Tournaments (R. Coulom)........................................................................................ 226

The Revolution of 2005 and the Rating Lists (J. Noomen)............................................................................ 227

                Habilitation of Dr. Ulf Lorenz (I. Althöfer)....................................................................................................... 230

                Calendar of Computer-Games Events 2006 - 2008........................................................................................... 231

                The ICGA Journal Referees 2006 (The Editorial Board) ................................................................................ 231

                Correspondence: World’s Smallest Chess Program (O. Toledo)................................................................. 231

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

                Adriaan de Groot (1914-2006) – An Obituary (H.J. van den Herik and H. Visser)..................................... 233

                Adriaan de Groot: Marriage of Two Passions (F. Gobet).............................................................................. 236

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

 

 

Overchampion

 

The title World Champion has a magic sound. It expresses the idea that a player is stronger than all other players in the world. It is the superlative among players. There is nothing above, … or is there? In the 1970s the Dutch Grandmaster Hein Donner introduced the title Overchampion for Grandmaster Victor Korchnoi, since his performances in tournaments, in matches, and in single games were extraordinary, as was his play. Although he did not live up to these expectations in his 1974 and 1978 matches against Karpov, it was generally accepted that Korchnoi was the Overchampion and Karpov the World Champion, whatever that meant.

 

Since December 2006, the (computer-)chess world has a new Overchampion, in the entity Deep Fritz 10. The way the program won its match against World Champion Vladimir Kramnik was superb. If we disregard the win in the second game and only look at the final game, we must admit that Deep Fritz 10 is the better player, the Overchampion. The Overchampion most clearly showed its strength in game six by introducing a novelty followed by a couple of brilliant ideas. Our congratulations go to Frans Morsch, Mathias Feist, and the ChessBase team for their continuous improvements of the program, their perseverance to reach this goal, and their outstanding achievement (see pages 208-213 of this issue).

 

Meanwhile we observe that there are many runners-up. They believe that they are equally strong or even stronger than the Overchampion. In this issue Jeroen Noomen provides an overview of the 2005 revolution and the ratings of the runners-up (see pages 227-229). He discusses Rybka, Zappa, Fruit, mentions Hydra, as well as Junior, Shredder, and Fritz. Whatever the case, the current situation is as follows: Junior is the 2006 World Champion and Deep Fritz 10 is the 2006 Overchampion.

 

With the seven contenders mentioned, the fight is severe and intense. Paraphrasing Sir Walter Scott (1771-1832), we are tempted to state: “What shall be the chess game’s fate? Who shall be the fatal research mate?” By this semi-quotation we also imply to formulate the following question as a next research question: Can we solve the game of chess? If the answer is affirmative, then other questions emerge, such as when, by whom, and by what means? At this victorious moment of the birth of an Overchampion, your Editor will not speculate on the “when” question, since that is in fact of subordinate nature. It is clear that solving the game is the next step.

 

In 1958, Herbert Simon stated: “Within ten years, a computer will be the World Champion unless the rules bar it from competition.” He had to wait until 1997 (when Deep Blue defeated Kasparov), before it actually happened. Simon’s statement has been taken by many as an example of an overclaim by AI researchers. The opponents of strong AI call it a bold prediction. In my opinion, the opponents are wrong since the 1958 prediction was only an optimistic estimation of the length of the time needed. The idea of underestimating the cost in an algorithm that is searching for the optimal path as happens in the A* algorithm is essential for achieving the goal. So did Simon. It is good that he made such a prediction.

 

In retrospect, we should have asked for two more predictions: (1) when will a computer be an Overchampion? and (2) when will the game be solved? How difficult such predictions are can be seen in the two obituaries of Adriaan de Groot. The eminent Dutch scientist, who passed away in August 2006, was a close friend of Herb Simon, but scientifically they were opponents. De Groot’s work, which includes the well-known book Thought and Choice in Chess, contains many contributions to the AI domain and in particular to chess and cognition. The latter topic is elaborated upon by Fernand Gobet (see pages 236-243).

 

Next to Chess, this issue contains new ideas on capturing problems in Go, on Sum Games, on Risk, and on Complexity. Moreover, we have the tournament reports and the conference reports all producing the same rhythm: “progress in science is going very fast: within the next three years many breakthroughs are to be expected.” Our readers may be assured, this Journal will report on them.

 

Jaap van den Herik

 

 

Welcome and Farewell

 

The composition and production of the ICGA Journal is an interesting but laborious task, as is the editing of all contributions, being articles, notes, and reports. Up to January 2007, the Editor-in-Chief was pleased with the support by Dr. Jeroen Donkers as Deputy Editor. Jeroen did his Ph.D. research in Opponent Modelling some years ago and thereafter he served our community. A year ago he has decided to take up his original computer-science research in the area of biology-inspired informatics. Since January 1, 2006 he is the coordinator of the BIOMICC group within our institute MICC-IKAT. The new task takes a great deal of his time and therefore he believed it was wise to step down as Deputy Editor. The Editorial Board and all other ICGA officers would like to thank Jeroen for the smooth cooperation over the years and wish him much success in his next job.

 

The same Board and officers are grateful to Dr. Mark Winands for his willingness to succeed Dr. Donkers in the function of Deputy Editor. We expect to cooperate equally well with Mark, who is known to our readers by his Ph.D. research of the game Lines of Action, performed within our institute. – Ed.

 

The credits of the photographs in this issue are to: ChessBase, Ingo Althöfer, Maciej Szmit, Eric van Reem, family De Groot.

 


A NEW HEURISTIC SEARCH ALGORITHM \\FOR CAPTURING PROBLEMS IN GO[1]

 

Keh-Hsun Chen and Peigang Zhang

Department of Computer Science, University of North Carolina,

Charlotte, NC, USA. Email: chen@uncc.edu, pzhang1@uncc.edu

 

We propose a highly selective heuristic search algorithm for capturing problems in Go. This iterative deepening

search works on the crucial chain in which the prey block is located.  The algorithm starts using three order liberties of the chain as the basis of the position evaluation, the value is then adjusted by the presence of few liberty-surrounding opponent blocks. The algorithm solved most capturing problems in Kano's four volumes of graded Go problems. Moreover, it is fast enough to be used by Go programs in real time.

 

 

NEW APPROXIMATE STRATEGIES FOR PLAYING SUM GAMES\\

BASED ON SUBGAME TYPES

 

Manal M. Zaky and Cherif R. S. Andraos and Salma A. Ghoneim

Ain Shams University, Cairo, Egypt. Email: manalmourad@yahoo.com,

cherif.andraos@ieee.org, salma\_ghoneim@hotmail.com

 

In this work we investigate the potential of combining AI tree-search algorithms with the algorithms of combinatorial game

theory to provide more efficient strategies for playing sum games based on subgame types. Two new approximate strategies are developed and tested using a specified game model. Both strategies achieve higher performance than approximate strategies previously proposed in the literature without being computationally more expensive.

 

 

ON THE IMPORTANCE OF EMBRACING RISK IN TOURNAMENTS

 

Darse Billings

University of Alberta, Edmonton, Canada. Email: darse@cs.ualberta.ca

 

The issue of playing style is not normally given much consideration in chess and other two-player perfect information games with draws. Nevertheless, between two equally strong players, a player who tends to win or lose games has a significantly better chance of winning a tournament than a player who draws a lot of games.  This note will attempt to quantify the effects of playing style on the probability of winning a tournament.

 

 

NIM IS EASY, CHESS IS HARD --- BUT WHY??[2]

 

Aviezri S. Fraenkel

Department of Computer Science and Applied

Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel.

Email: fraenkel@wisdom.weizmann.ac.il

http://www.wisdom.weizmann.ac.il

 

The game of chess appears to be hard. According to authoritative sources, this is due to the extremely large number of possible chess moves. We refute this argumentation by showing that simple games of moderate size --- as an example we consider nim --- have a larger number of moves than chess, yet possess a very easy winning strategy. So perhaps chess has also an easy strategy which remains elusive? We argue that this is rather unlikely, in view of several high-complexity aspects of chess, notably the proven



[1] This article is a slightly adapted version of the authors' article in the CG'06 conference proceedings. It is republished with permission of the Editors of the Proceedings and of the publisher, Springer-Verlag, Heidelberg, Germany. \

 

[2] This is an expanded version of a note that appeared in the ``Reader's Corner" of Plus

Mag., Issue 40 September 2006