ICCA Journal, Volume 18:  Number 4  (December 1995)

TABLE OF CONTENTS

Editorial:                                                                                          
    Breakage and Seepage (I.S. Herschberg and H.J. van den Herik) .............................. 189
Contributions:                                                                                      
    Tutoring Strategies in Game-Tree Search (H. Iida, K. Handa, and J.W.H.M. Uiterwijk) ........ 191
    Quantification of Search-Extension Benefits (D.F Beal and M.C. Smith) ...................... 205
Notes:                                                                                              
    On Barth's ``Combining Knowledge and Search to Yield Infallible Endgame Programs''              
        (S.J. Edwards) ......................................................................... 219
    The KPKP Endgame: An Amplification (W. Barth) .............................................. 225
Literature Received:                                                                                
    How to Use Limited Memory in Heuristic Search (H. Kaindl, G. Kainz, A. Leeb and H. Smetana)  226
Reviews:                                                                                            
    Proc. of the Game Programming Workshop in Japan '95 (J.W.H.M. Uiterwijk and H. Iida) ....... 227
    Schach am PC (I.S. Herschberg and H.J. van den Herik) ...................................... 230
    Der Schachcomputerkatalog (I.S. Herschberg and H.J. van den Herik) ......................... 231
Reports:                                                                                            
    The 13th World Microcomputer-Chess Championship ............................................ 233
        Report on the 13th World Microcomputer-Chess Championship (U. Lorenz) .................. 233
        Results and Selected Games (R. Feldmann) ............................................... 236
    The 15th Dutch Computer-Chess Championship (H. Weijer and Th. van der Storm) ............... 245
    The ACM Computer-Chess Challenge (M. Newborn) .............................................. 248
    The ACM Computer-Chess Workshop (M. Newborn) ............................................... 248
    The Sixth Harvard Cup: Human-versus-Computer Chess Challenge (C. Chabris) .................. 249
    Calendar of Computer-Games Events 1995/1996 ................................................ 250
    ICCA Journal Referees in 1995 (The Editorial Board) ........................................ 250
    Second Call for Papers: Advances in Computer Chess 8 (Maastricht, The Netherlands) ......... 251
    The Swedish Rating List (T. Karlsson and G. Grottling) ..................................... 252
    Tablebase of Contents, Continued (J. Uiterwijk) ............................................ 253
Correspondence:                                                                                     
    An Appeal (I. Botvinnik) ................................................................... 255

ABSTRACTS OF SCIENTIFIC ARTICLES

Tutoring Strategies in Game-Tree Search

Hiroyuki Iida, Ken-ichi Handa and Jos W.H.M. Uiterwijk

[18(4):191-204]   Pursuing the idea of a good working knowledge of one's opponent model (OM search), loss-oriented search (LO search) goes beyond OM search in occasionally presenting the opponent with an intentional give-away move. When this model is extended to the tutorial level, a delicate balance must be maintained: give-away moves are allowed under the important proviso that, on a balance of probabilities, they should go unnoticed. It is acknowledged that the model is possibly too detailed to be realistic and rather naively replaces the stochastic quality (does the opponent recognize a give-away move?) by a numerical value. Yet, the paper provides valuable though preliminary results on an idealized opponent and how to tutor him.

Quantification of Search-Extension Benefits

Don F. Beal and Michael C. Smith

[18(4):205-218]   This paper considers several search-extension rules and one pruning rule that have been described in the literature. An experiment was performed to see how effective each rule was in isolation, and in various combinations. The experiment was performed on a fixed testset of positions, and results measured using node counts. The emphasis of the work was to make repeatable measurements on well-defined tasks, for future comparison with other search-extension rules. In the test domain chosen, some extension rules were strongly advantageous compared with fixed-depth search, but disadvantageous in combination with others. Notably, singular extensions were strongly beneficial if added to a fixed-depth search, but detrimental if added to a search already using check extensions, recaptures and null moves.

On Barth's ``Combining Knowledge and Search to Yield Infallible Endgame Programs''

Steven J. Edwards

[18(4):219-224]   [The article by Barth (1995) gave rise to a reply by Steven Edwards, desirous of setting the record straight. Below we publish his comments to which Mr. Barth was given the right to reply. His answer is also reproduced below. All Barth's (1995) diagrams have been republished with the same numbering in Edwards' Section 3 below. - Eds.]

The KPKP Endgame: An Amplification

Wilhelm Barth

[18(4):225]   (See explanation provided provided for Edwards' note above.)          

EDITORIAL

Breakage and Seepage

I. Samuel Herschberg and H. Jaap van den Herik

[18(4):189-190]   Somewhere in Holland, there is a statue to Hans Brinker. Brave Hans, the legend goes, put his finger into the dyke (a dam to the Dutch) and kept it there overnight, thus stopping the waters from breaking trough into the polder. Not only is the figure of Hans purely fictitious, the legend goes against physics, hydrology and common sense.

Physics dictate that the threat to a dam is not from a hole that can be plugged by a boy's finger. Rather, outside pressure causes the inimical waters to seep through and under the dam, inflicting much more damage by seepage than imaginatively could be caused by a finger-sized breach.

Yet the statue is there for the benefit of tourists, while the steady work, maintained over the centuries by engineers to tame the seepage goes unsung. The moral is of course that hydrological achievement is not the work of a mythical individual who reaps the intoxicating benefits of the headlines, but of plodding members of the community who, if they write at all, are quite content with dull reports in the literature of their profession.

Let us apply the lesson to our own field: of course, it is newsworthy that next February Garry Kasparov is to play DEEP BLUE. The kitty is commensurate with the estimated impact of the event and we do not blame anybody who is impressed by half a million dollars in prize money. Editorially we may be forgiven, a slight smile: was not part of the reason for such largesse in the prizes be the desire to persuade the ordinary citizen that there must be something in it, otherwise hard-nosed companies would not make so many good greenbacks available.

Regular readers of our Journal will refuse to see this match, whatever its outcome, as a breakthrough though it will be labelled as a very public piece of breaking through a dam of opposition for computer chess.

We are amused, but not impressed. To us, this pretended act of breakage is far overshadowed by the quiet seepage, the oozing of ideas, the percolation of techniques, in short, the seepage which these pages have witnessed for over a dozen years. In this seepage, it was shown very acutely that not all new ideas had the future that was confidently expected for them by their originators. Let us, without blushing, quote some examples. The B* algorithm fizzled out, as did the singular-extensions technique. By way of contrast, transposition tables and the null-move algorithm did prove their mettle.

Recording the successes and failures, however, is only secondary to our argument. Our main assertion is that, owing to the seepage which would never make nation-wide headlines, the quality of programs has improved continuously - and when we say continuously we indeed mean by imperceptible stages.

Due to seepage, embodied in this Journal and others or even merely secretively incorporated into actual playing programs, all previous estimates of computer playing strengths have been made obsolete.

A few years ago, it was estimated that only 2,000 players in the world could consistently outdo the best of the programs the industry had to offer. Reviewing recent results, Paderborn and Hong Kong among them, we challenge our readers to revise this estimate. How many players, they believe, would consistently outdo a good program on a well-equipped but otherwise unacceptional PC? A drastic downward revision will be in order.

In our view, the overall improvement with the march of time of consistently good programs on modest equipment is far more telling in favour of the maturity of computer chess than any spectacular result that ``Like Snow upon the Desert's dusty Face, Lighting a Little Hour or Two - Is Gone.''