Editorial:
Game Over (H.J. van den Herik) ............................................................. 73
Contributions:
Extended Futility Pruning (E.A. Heinz) ..................................................... 75
Experiments in Parameter Learning using Temporal Differences (J. Baxter, A. Tridgell,
and L. Weaver) ......................................................................... 84
Learning to Play Chess Selectively by Acquiring Move Patterns (L. Finkelstein
and S. Markovitch) ..................................................................... 100
Reports:
Israel Samuel Herschberg: An Obituary (The Editor) ......................................... 121
A Eulogy for Bob Herschberg (H.J. van den Herik) ........................................... 122
David Hooper: A Tribute (H.J. van den Herik) ............................................... 125
Advanced Chess by Kasparov and Topalov (F. Friedel) ........................................ 126
List-3-Hirn vs. Grandmaster Yusupov (I. Althoefer) ......................................... 131
Report on the 8th CSA World Computer-Shogi Championships (R. Grimbergen and H. Iida) ....... 135
The Professor Gaetano Salvatore Award (The Board of ICCA) .................................. 138
Ernst A. Heinz: A Biographical Sketch .................................................. 138
ICCA Constitution and By-Laws (The Board of ICCA) .......................................... 139
Calendar of Computer-Games Events 1998 ..................................................... 142
The Swedish Rating List (T. Karlsson) ...................................................... 143
Although extended futility pruning is theoretically unsound, extensive experiments with our master-strength chess program DARKTHOUGHT show that it works markedly well in practice. Even at fixed search depths, extended futility pruning exhibits hardly any loss of tactical strength while shrinking the search trees by 10 to 20 percent on average as compared with normal futility pruning.
Moreover, extended futility pruning combines nicely with a conservatively limited variation of razoring. It reduces the search trees at fixed search depths of more than 10 plies by an additional 5 to 15 percent on average. Finally, we have observed that the presented pruning schemes scale very well with the search depth, and reap ever more benefits at higher depths.
From the game-playing point of view we see two signs, viz. Advanced Chess and Shuffle Chess. Both emerged as new versions of our royal game. Are they indications that the game of chess is over, and that we have to look for a new game? Who knows? In the case of a pinball machine, a new game is easy, since inserting a new coin is sufficient to start a completely different game. Of course, the question is: is this actually a new game? One might argue that this is so, since the pins on the pin table provide a wider range of possibilities than chess players can imagine in their game. Moreover, pin tables are a much greater obsession for many than chess-boards for some. Thus, for pinball machines the rules should not be changed. But for chess?
According to the players who have almost reached perfection in chess, Garry Kasparov and Robert Fischer, it is high time to try and find a different game. They did so by proposing Advanced Chess and Shuffle Chess, respectively. The former World Champions - both players still regard themselves as the World Champion - have indicated that the game of chess has lost (some of) its attractiveness. It no longer seems to be a challenge to them. Although their motives may be different, both are complaining about the computer's playing strength.
For Kasparov, one is inclined to believe that he is a true follower of the adage: "if you can't beat them, join them" and for Fischer it seems to hold that new start configurations evoke new ideas in his thinking process. As an aside, for an adapted Fischer game, we would like to put forward the following question. Assuming that White has the usual starting configuration: which shuffled position is best for Black? Indeed, many other questions about (shuffled) games may evolve. But the principal question remains: is a change of rules really necessary? My answer is a definite no. The game of chess has an overwhelming number of secrets still to be detected and this will not change in the foreseeable future.
The statement above brings us back to the idea of Advanced Chess, and the question whether it may be regarded as the next stage on our way to perfection. The report by Frederic Friedel seems to pave the way to a dominant position of computers, showing the thinking process of a Grandmaster as well as giving the players the right opening moves, and preserving them from making severe mistakes. The only prerequisite so far is that the Grandmasters should have a better time control than shown in the match in León. Moreover, the proposals by Fischer and Kasparov are not new in themselves. Some seventy years ago, World Champion José Raoul Capablanca, who reigned over the chess world from 1921 to 1927, believed that he had reached such a degree of perfection in chess that he called it a dead game. He thought that he could always make a draw with any opponent. Since he believed that he had unravelled the chess mystery and that the game no longer had any secrets for him, he turned to Bridge, taking many of his colleagues with him to this related game, which differs essentially by its characterization of being a game of incomplete knowledge.
Later on, it turned out that the gap between Capablanca's perfection and optimal play from both sides (i.e., solving the game) was incredibly wide. Even today, we still have no idea what the game-theoretical outcome is.
>From the scientific point of view we remark that new games are attractive, since they call for new strategies and for thoughts on the final solution. Hence, it is important to formulate (strategic) rules to handle the game. These rules can be developed by human players, but in this respect AI techniques may support us even better. The ever developing learning techniques are the third sign of the increasingly dominant position of computers over human beings, and in particular over chess players. Two contributions in this issue deal with these techniques.
In summary, the three signs can be characterized as classic (machine learning), provocative (Shuffle Chess), and promising (Advanced Chess). In particular, we mention that a man-machine team in Advanced Chess has an estimated Elo rating of over 3000. Yet, the game of chess is not over, neither now, nor in the near future. Although humans and computers co-operate quite closely to reach their goal of perfection, I do not believe that the gap will be bridged in the next century.