|Table of Contents||65|
|Making Headway (H.J. van den Herik)||65|
|Some Practical Techniques for Global Search in Go (K. Chen) abstract||67|
|KQQKQP and KQPKQP~ (P. Karrer) abstract||75|
|Computer Chess Meets Planning (M. Brockington) abstract||85|
|A Measure of Beauty (The Editor)||93|
|Deepest Chess Win Revisited (G.McC. Haworth)||94|
|Games in AI Research (D. Hartmann)||97|
|Information for Contributors||100|
|News, Information, Tournaments, and Reports:||101|
|Championship on the FRITZ (D. Hartmann)||101|
|FRITZ SSS* and Loek van Wely (J. Welling)||109|
|Report on the 1999 World Computer-Bridge Championship (M.L. Ginsberg)||111|
|Report on the 10th CSA Computer-Shogi Championship (R. Grimbergen)||115|
|The 1999 ChessBase Best-Publication Award (The Board of ICCA)||121|
|Calendar of Computer-Games Events in 2000-2002||122|
|The 5th Computer Olympiad (D.N.L. Levy)||123|
|Call for Papers: Computer-Games Workshop (J. Uiterwijk)||125|
|The Game-On 2000 Conference (Ph. Geril)||126|
|The Swedish Rating List (T. Karlsson)||127|
|How the ICGA Journal Reaches You||128|
A dispute in science is a clash of opinions that may lead to an outcome generally considered to be true. A hot dispute in society may lead to a war, of which the outcome is often unpredictable. In between we find a dispute in the world of games. This may lead to a serious controversy and a remarkable verdict as we have seen in the last Dutch National Chess Championship.
After Kasparov’s defeat against DEEP BLUE in 1997, our Editorial statement was that the next step should be a match between the human World Champion and a computer program with the world title at stake, preferably a match under the aegis of FIDE. Until then the DEEP BLUE-Kasparov matches were played under the supervision of the ICCA and even IBM. Although in these matches honour and money had some competition, money always was the dominant issue. Kasparov might have been angry that he lost his 1997 match, but at least he earned a considerable amount of money and did not lose his official honour of being the World’s Best.
The feeling that honour is worth more than the sum of all amounts paid so far as prize money in computer-chess matches is shared by many chess players. Therefore, the suggestion by GM Genna Sosonko to invite a computer program to play in the Dutch National Chess Championship constituted a breakthrough for scientists since a calibration of playing strength is best performed when both sides are doing their utmost. With the honour at risk human players are assured to fight for what they are worth. Of course, they should be encouraged to play such a tournament and for that purpose money could serve. So, honour and money are the perfect ingredients for something New in Chess.
Merely the announcement that a computer was invited to participate in the Dutch Championship was sufficient to bring alive many protest voices from all over the world. In this issue Dap Hartmann gives a well-written account of the event and the arguments pro and con. Meanwhile, we may conclude that FIDE belongs to the side that is furiously against computers playing in tournaments, let alone in National Championships. During the tournament they ruled that the results of future tournaments in which a computer participates will be no longer eligible for inclusion in the rating list.
In contrast, we believe that computer chess is not only a frontrunner in the world of games, but also serves as a guideline for the introduction of agent technology in the world of human beings. Soon software agents will make many decisions, for instance in the domains of commerce, economics and law. The world of chess forebodes such a development. The prevailing question therefore is do we wish to go along or do we object. FIDE clearly objects, but the winner of the Dutch Championship, Loek van Wely, obviously is in favour of combining honour and money as he states: “(…) the computer must be allowed to play next year again, if it generates more money.”
A glance over the statements of chess columnists shows that most of them are rather fanatic against the participation. However, a deeper investigation of the background of these columnists brings to light that they are usually not well acquainted with the world of computer science or computer games. Of course, this observation does not affect the validity of their opinion (e.g., we all have opinions on the atom bomb, but only a few have knowledge of it), but it makes a discussion difficult. As a case in point, reading the magazine New in Chess is recommended and in contrast to the magazine’s title, we can observe that the new development in chess is not well appreciated. New in Chess apparently hints only at new opening moves, or - albeit reluctantly - new endgame database results. New developments such as shuffle chess and advanced chess have a rather low priority. With the pace of the current development it is not difficult to predict that the contents of the magazine soon will change.
The new obstacles encountered after a change of policy are clear: a novel domain of expertise should be developed. This statement also applies to the ICGA Journal, since widening our scope meant widening the expertise and implied the co-operation with many more researchers. In this issue we are happy to publish articles on Go, Chess and Planning, as well as reports on Shogi, Bridge and Chess (now seen as the game that makes headway in the world at large). Some scientists predict a new economy, others have hesitations whether it will happen the way it is predicted. But obviously in this century the relation between science, commerce, and sportive competition will change fundamentally. The interrelationship will be mixed and integrated: human and computers will play at a par. The Royal Dutch Chess Association understands this development and is one of the first organizations that recognizes its importance. Therefore we offer them our sincere congratulations with the headway made.
Jaap van den Herik
A position evaluation and a candidate-move-generation strategy for global selective search in Go are described. Moreover, some Go-specific enhancements to the basic global selective alpha-beta game-tree search procedure are discussed. Finally, empirical results on the performance of the enhancements are presented.
Inspired by the game between World Champion Garry Kasparov and the “Rest of the World”, the author has constructed a set of 6-man Endgame Tables for positions with King, Queen and a single Pawn on each side. The tables have the restriction that underpromotions in 6-man positions are not considered2; nevertheless, they have been shown to be extremely useful in post-mortem analysis of the Kasparov-World game. As a follow-up project, KQQKQP (without promotion restrictions) was produced; this is the first 6-man EGT with Pawns that has been computed.
The EGTs were produced using a modified version of the EGT generator program written by Eugene Nalimov. This article describes the nature of these modifications and presents a general method of producing EGTs for endgames involving Pawns, requiring relatively moderate computer resources. Some of the more interesting results applied to the Kasparov-World game are presented, as well as statistical information about the EGTs.
Recently many papers have been published on how to improve the A* planning algorithm. A number of these papers are from ex-computer-chess practitioners. This paper attempts to summarize some of the enhancements to A*, and shows why a “computer chess”-style A* approach may be considered to be profitable when implementing A*.
H.J. van den Herik
in cooperation with
University of Shizuoka
Dfl. 75.- US$ 30.-
Reviewed by Dap Hartmann1
This book contains a total of 18 papers from two different workshops held in 1997: Game-Tree Search in the Past, Present, and Future (Princeton, NJ, August 5) and Computer Games: Using Games as an Experimental Testbed for AI Research (Nagoya, Japan, August 24-25).
When you think about it, computer chess has come a long way in a relatively short time. Barely 50 years after von Neumann and Morgenstern proposed MiniMax as an algorithm to find the best move, human world champion Garry Kasparov was beaten in a six-game match against a computer program that used MiniMax at the core of its move decision making. Marsland and Björnsson outline the current technology behind today’s chess programs, how it has developed, and where it may go in future. Another paper by these authors discusses selective depth-first search methods. By identifying desirable characteristics of pruning heuristics, the authors attempt to understand the shortcomings of existing techniques, and acquire insights to enable improvements. “Pruning heuristics should be concerned with the question: What is the likelihood of making an erroneous pruning decision, and if an erroneous decision is made, how likely is it to affect the principal variation?”
Four search innovations in CHINOOK are the topic of one of two papers contributed by Jonathan Schaeffer. CHINOOK, of course, was the first program to win a world championship against a human in any game. Now that the program has retired, the main innovative techniques used are revealed. “Although none of the ideas is in itself a major contribution to our understanding of game-playing programs, each played a significant role in creating a world championship program.” In another paper, Junghanns and Schaeffer present their efforts in constructing a program that can solve Sokoban puzzles. This one-player game, which originated in Japan, is quite challenging, and highly addictive. Those readers who are unfamiliar with these puzzles are encouraged to check out http://xsokoban.lcs.mit.edu/xsokoban.html, where ‘the standard suite’ of 90 Sokoban problems is available. But temporary loss of productivity in other areas may be the serious consequence of doing so. The complexity of these single-agent search problems is much greater than for comparatively ‘simple’ problem domains such as sliding-tiles puzzles or Rubik’s Cube. Only three of the 90 problems have a solution of less than 100 moves, while the solution to problem #39 requires 674 moves. “Clearly, being able to search this deep without getting lost in the exponential complexity of the search is a daunting task.” At the time when this paper was presented at the conference, ROLLING STONE (the authors’ Sokoban solving program) could find the optimal solution of only 12 of the 90 problems. But since then, considerable progress was made. In a postscript, the authors claim that the program can presently solve 58 problems. Most of this progress was achieved by incorporating the ideas presented in the section ‘Enhancing the current program’.
The only other paper in this book on single-agent problems is by Richard Korf, whose program found the first optimal solutions to random instances of Rubik’s Cube. “The key idea, due to Culberson and Schaeffer (1996), is to take a subset of the goals of the original problem, and precompute and store the exact number of moves needed to solve these subgoals from all possible initial states.” The median optimal solution length appears to be 18 moves. An experimental test suite of ten problems was constructed by carrying out 100 random moves starting from the initial (solved) state. One problem was solved in 16 moves, three required 17 moves, and the remaining six problems were 18 moves away from the initial state. Korf’s program generates 700K nodes per second, at which speed a complete depth-18 search requires about four weeks of CPU time. A very impressive result, considering the complexity of the problem: 43x1018 different states for a 3x3x3 Rubik’s Cube.
M. Buro contributes two papers on Othello. The first one deals with the construction of opening books by means of learning from mistakes made in previous games. In the second paper, he describes a new evaluation function for Othello, and introduces a generalized selective search heuristic. The combined effect results in an increased playing strength equivalent to a speed-up by more than a factor of ten.
A description of his Othello-playing program KEYANO is presented by Mark Brockington, one of the many researchers in the field of computer games from the University of Alberta. “[…] most first attempts at writing an Othello program are significantly flawed”, according to the author. The revealing of the innards of KEYANO, which routinely finished in the top six in 21 computer Othello tournaments, will therefore be much appreciated by aspiring Othello programmers. One distinguishing feature of the program is that databases of games were used to tune parameters in the openings book, in the search routine, and in the midgame evaluation function. “Training from top-quality Othello games, is vital to the success of any Othello program.”
There are two papers on Shogi, and perhaps the only blemish on this very well-edited book is that a different style of diagrams is used in each. In Grimbergen and Matsubara’s contribution on the use pattern recognition for candidate move selection, kanji characters are used, whereas the paper on the automatic composition of Shogi mating problems by Watanabe, Iida, and Uiterwijk employs chess symbols, with the pieces of the white player printed upside-down. Neither method is very enlightening to those who are unfamiliar with Shogi. Perhaps a new set of symbols should be agreed upon, whereby different pieces are more easily distinguishable, and in which it is clear at a glance which pieces belong to which side.
Even though the preface of this book claims that there are two papers on computer Bridge, there is, in fact, only one. Smith and Nau compare two competing approaches to computer Bridge, namely planning and brute force, but fail to come to any particular conclusion. If I had been a referee for this paper, I would not have accepted it for publication, because the relevant contents is very close to zero.
Frank, Basin, and Matsubara investigated games with imperfect information by applying Monte-Carlo simulations to the unknown (hidden) pieces of information. But, unfortunately, as depth increases, the observed error rapidly approaches 100%. This is probably the second paper on Bridge in the editors’ opinion. Certainly, Frank and Basin have published papers on computer Bridge before, but this paper addresses the general class of games with imperfect information. “The experience with Bridge suggests that a measure is needed for imperfect information games that describe game properties that have a bearing on the difficulty of solving the game with a Monte-carlo approach.”
The paper by Iida, Uiterwijk, and Van den Herik explores cooperative strategies for so-called ‘pair-playing’, in which two pairs of players alternate moves (without any communication) in a two-person game with perfect information. A distinction is made between cases in which the players have exhaustive knowledge or only partial knowledge of their partner’s strategy. Furthermore, it is also assumed that each pair consists of players of different strength. “[…] the performance of a cooperative search strategy […] is better than that of a non-cooperative strategy when a player has exhaustive knowledge of the partner’s strategy.”
The remainder of the papers deal with computer Go. Martin Müller describes a generalized thermography applied to the game of Go, in which a ‘mast value’ (a measure of the score) and a ‘temperature’ (a measure of the urgency to move) are computed for a wide range of Go positions. In ‘Flexible acquisition of various types of Go knowledge’, Kojima, Ueda, and Nagano describe an algorithm to extract knowledge from Go game records. The appendix provides 18 examples of rules acquired through the use of this method. The application of the algorithm to other games is discussed briefly.
Nakamura presents two graph-theoretic approaches for estimating the number of eyes of groups in Go positions. “The first method is based on Euler’s formula for connected plane graphs in which the number of minimal loops is given by the number of vertices and edges. The second method is based on labelled graphs called situation diagrams representing higher-order Go board situations and enabling the analysis of complex capturing races.”
A study of the memory performance of Go players is presented by Burmeister et al., more or less analogous to similar cognitive studies in chess by de Groot and Chase & Simon. Even at the highest presentation speed tested (half a second per move), Go experts had little difficulty in reproducing the games which were shown to them in this way. “[…] experts can extract significant information in less than 500 milliseconds per move.”
Saito and Yoshikawa make a case for using Go as the next drosophila for studies in cognitive science. They argue that Go presents a greater challenge than chess, because it is full of unsolved problems and because perceptual-level features are closely related to higher-level plans and strategies. Even though I generally agree with the authors, my personal opinion is that the game of Go is too big a hurdle to take after the successful challenge of the human chess world champion. Sadly, there were no contributions on Amazons. This fascinating game may provide an intermediary challenge between a world-champion-level chess program and expert-level Go programs. The former goal has been achieved, while the latter one must be considered to be decades away. However, as of this writing, the strongest Amazons-playing programs are probably already outperforming the few humans who excel in this intriguing game, simply because the game does not have the long history and tradition of chess and Go. Nevertheless, like Go, the game of Amazons has a huge branching factor which creates the challenging conditions of having to abandon the deep full-width searches which underlie the world’s strongest chess programs.
Most papers in Games in AI Research are highly accessible to anyone with ‘merely’ a computer-chess background. In that, it sets the perfect example of what the ICGA Journal has yet to prove to its readers: papers on games (and puzzles) other than chess, at a level which is non-trivial to the experts in those particular games, while being accessible to the former ICCA members, whose expertise will be predominantly in computer chess. I found that 90 percent of the papers in the present book fell in that category. Warmly recommended.