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
Notes: ................................................................................................................................................................................ 199
On
the Importance of Embracing Risk in Tournaments (D.
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
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 (
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
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,
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
NEW APPROXIMATE STRATEGIES FOR
PLAYING SUM GAMES\\
BASED ON SUBGAME TYPES
Manal M. Zaky and Cherif R. S.
Andraos and Salma A. Ghoneim
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
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,
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,
[2] This is an expanded version of a note
that appeared in the ``Reader's Corner" of Plus
Mag., Issue 40 September 2006