ICCA Journal, Volume 19:  Number 2  (June 1996)

TABLE OF CONTENTS

Editorial:                                                                                          
    Chess or Beyond? (I.S. Herschberg and H.J. van den Herik) ..................................  73
Contributions:                                                                                      
    An Explanation Tool for Chess Endgames Based on Rules (H. Herbeck and W. Barth) ............  75
    Beware the Bishop Pair (M. Sturman) ........................................................  83
Notes:                                                                                              
    A Parallel Algorithm for Solving Hard Tsume-Shogi Problems (Y. Nakayama, T. Akazawa,            
        and K. Noshita) ........................................................................  94
    Why did Kasparov Blink? (H.J. Berliner) ....................................................  99
Literature Received:                                                                                
    Searching Game Trees under a Partial Order (P. Dasgupta, P. Chakrabarti, and S. DeSarkar) .. 101
Reports:                                                                                            
    Natural Developments in Game Research (H. Matsubara, H. Iida, and R. Grimbergen) ........... 103
    The Choice of a Research Direction (V.V. Vikhrev) .......................................... 113
    Report on the Match 3-Hirn vs. Christopher Lutz (Chr. Lutz) ................................ 115
    Recent Advances in Computer Chess Workshop (J.W.H.M. Uiterwijk) ............................ 120
    Expectations on Chess, Computer Chess, and AEGON (H.J. van den Herik) ...................... 122
    The 11th AEGON Man-Machine Tournament (C. de Gorter) ....................................... 124
    Feast and Famine: ICCA Treasurers Report for 1995 (D.F. Beal) .............................. 133
    The ICCA Best Annotation Award for 1995 (D. Levy and T. Marsland) .......................... 135
    The 1996 World Microcomputer-Chess Championship (D. Levy) .................................. 136
    Provisional Programme: Advances in Computer Chess 8 ........................................ 141
    Calendar of Computer-Games Events 1996 ..................................................... 142
    The Swedish Rating List (T. Karlsson and G. Grottling) ..................................... 143

ABSTRACTS OF SCIENTIFIC ARTICLES

An Explanation Tool for Chess Endgames Based on Rules

Heinz Herbeck and W. Barth

[19(2):75-82]   Moves played by a chess program are often hard to comprehend by a human opponent and the ``idea'' the program ``had in mind'' when it chose that specific move is difficult to see: chess programs usually do not provide any explanation of their moves. The rule method for endgames (Barth and Barth, 1991, 1992) uses a combination of expert knowledge with a modified version of alpha-beta-search. The expert knowledge is expressed by rules such as can be easily understood by a human chess-player; therefore they can be used to give the chess-player a blow-by-blow explanation of the program's decisions. In this paper, several methods for generating such explanations for endgame programs are described.

Beware the Bishop Pair

Mark Sturman

[19(2):83-93]   (Text still missing ...)

A Parallel Algorithm for Solving Hard Tsume-Shogi Problems

Yasuichi Nakayama, Tadafumi Akazawa, and Kohei Noshita

[19(2):94-98]   For the last four years, the power of Tsume-shogi solvers (i.e., programs for solving Japanese-chess problems) has advanced remarkably. Hard problems with 19 to 25 steps are now being attacked by several different types of search algorithms in the hope of solving all but a small set of these problems within a short time. In this paper, we present a parallel algorithm on network-connected distributed UNIX workstations, and show new computing results by solving 100 hard problems. The results confirm that our parallel program can solve most of the problems much more quickly than the best sequential program on a UNIX workstation.

Why Did Kasparov Blink?

Hans J. Berliner

[19(2):99-100]   (Text still missing ...)

Natural Developments in Game Research

Hitoshi Matsubara, Hiroyuki Iida, and Reijer Grimbergen

[19(2):103-112]   In game programming research there are four interesting and related domains: chess, xiang qi (Chinese chess), shogi (Japanese chess) and go. In this article we will compare chess with shogi, both comparing the rules and the computational aspects of both games. We will see that chess and shogi are very similar, but that there are some important differences that complicate game programming for shogi. Most important difference is the game tree complexity, which is considerably higher than the game tree complexity of chess.

We will then argue that these similarities and differences make shogi a good choice for further research in game programming. Chess will soon no longer be competitively interesting. Xiang qi has a game tree complexity similar to chess, suggesting that the same AI techniques will also be successful in this domain. Go is too risky as a next research target because little is known about the cognitive aspects of the game, which in our view hold the key to developing new techniques. Also in this article, a short history of computer shogi with the results of the latest CSA computer shogi tournament is given. In the appendix a short introduction to the rules of the game is included.

EDITORIAL

Chess or Beyond?

I. Samuel Herschberg and H. Jaap van den Herik

[19(2):73-74]   For some time now an informal solution to the game of chess has been in the making. As always in matters of opinion and even in opinionated matters, views differ. According to some, the game of chess has been solved in the particular and irksome form that passionate players cannot vanquish their machines. To a privileged few, this statement is met with derision: they, a privileged tenscore or so, regularly bring their computer opponent to its figurative knees. With Olympian detachment, we can only conclude that nearly all the hard work has been done and that computer chess reigns supreme. This is not merely expressed as half points or points won even over the top-players of the game, it also comes to the fore in the emergence of explanation tools for chess endgames and of awards for the best annotation.

This is well beyond outplaying the majority: it is explaining the quality of a move to those not perhaps inspired enough to produce the move themselves. In other words, many computers are not only playing better, but, with their program, are capable of expounding the why and wherefore of their moves. Such an explanation takes the form of what is roughly a Grandmaster's comment on the moves. Chess, therefore, to all but a few hundred has acquired the status of solved and explicable.

The question before your Editors is now clear: in a famous metaphor, chess has been dubbed the Drosophila of at least one variety of Artificial Intelligence. The Drosophila's genetic make-up having been solved, the question remains: what is the next subject of research? A direction of research, as Vikhrev points out in this issue, should be prospective and even prepared to tack and veer with the winds of change.

Accepting this as a truth, where shall we go? Shall we pursue the course of an ICCA Journal where chess is the main subject and even more detailed chess subjects will be the main bill of fare, or should we branch out? A restriction to chess has the advantage of maintaining continuity, but may lose its edge by being overly specialized, interesting to only a handful of experts world-wide.

By contrast, opening up the pages of our Journal to all manner of computer games can be no more than sighting the tip of an iceberg, not even scratching it. Restriction to chess is too limitative, extension to all computer games is unbounded to a degree.

Yet, in the somewhat longer run, such a choice is inevitable and a clear policy is required: shall it be chess for the chess specialists or any computerizable game not solved so far? The choice is up to our readers and strong opinions for our correspondence column are invited: shall the Editors of this Journal provide delicacies for the few or should they rather provide fare for a host of gaming folk? Will our readers, please, help to decide between such extremes as the article by Herbeck and Barth, explicatory in nature, and the approach of Matsubara, Iida and Grimbergen which at one fell swoop extends solved Chess by way of Shogi to unsolved Go? We think that the sweeping conclusion of Shogi and Go is premature.

Nevertheless, the ultimate decision rests with our readers and contributors; your Editors still feel that they find themselves at a crossroads. To put it at its simplest, will the ICCA Journal, possibly then most easily available on some Web, be about computer chess or about computer games?