ICCA Journal, Volume 18:  Number 3  (September 1995)

TABLE OF CONTENTS

Editorial:                                                                                          
    Bright and Beautiful, Great and Small (I.S. Herschberg and H.J. van den Herik) ............. 133
Contributions:                                                                                      
    Controlled Conspiracy-Number Search (U. Lorenz, V. Rottmann, R. Feldmann, and P. Mysliwietz) 135
    Combining Knowledge and Search to Yield Infallible Endgame Programs (W. Barth) ............. 148
Note:                                                                                               
    An Examination of the Endgame KBNKN (S.J. Edwards and the Editorial Board) ................. 160
Literature Received:                                                                                
    Computer-Chess Championship Programs (J.-C. Weill) ......................................... 168
Reports:                                                                                            
    An Interview with Robert Byrne (D.N.L. Levy) ............................................... 170
    Extrapolation and Speculation (D.N.L. Levy) ................................................ 171
    Aegonics (I.S. Herschberg and H.J. van den Herik) .......................................... 175
    Computer Wins Man-versus-Machine Match on ICC (E. Peterson) ................................ 178
    The 1995 World Microcomputer-Chess Championship (Paderborn, Germany) ....................... 179
    Landslide Victory for Computers (A. Tridgell) .............................................. 183
    Calendar of Computer-Games Events 1995/1996 ................................................ 184
    Call for Papers: Advances in Computer Chess 8 (Maastricht, The Netherlands) ................ 185
    The Swedish Rating List (T. Karlsson and G. Grottling) ..................................... 186
Correspondence:                                                                                     
    Errata to the Reporting of the 1995 WCCC ................................................... 187

ABSTRACTS OF SCIENTIFIC ARTICLES

Controlled Conspiracy-Number Search

Ulf Lorenz, Valentin Rottmann, Rainer Feldmann, and Peter Mysliwietz

[18(3):135-147]   We present a new conspiracy-number search algorithm (CNS), called Controlled Conspiracy-Number Search (CCNS). The basic steps of any CNS algorithm, the selection, the expansion, and the backup of results have been modified compared to other CNS algorithms. The selection is done by assigning demands, so called cn targets, on the nodes of a game subtree in a top-down fashion. Doing so, a set of leaves is selected in a single action. An expansion is used to check whether a leaf node can fulfil the demands imposed upon it in terms of conspiracy number. A backup subalgorithm uses heuristic information gained from the expansion step in order to prepare the game subtree for the next selection phase.

We have found our algorithm to be stronger than the alpha-beta algorithm in tactical positions. This has been shown by comparison them on a recognized set of test positions. It is able to play reasonably even in non-tactical positions, as shown at the 4th International Paderborn Computer-Chess Championship, where ULYSSES CCN, a program based on the CCNS algorithm, participated in a complete tournament with creditable results. Prospects are that, with every selection-step selecting a set of leaves for expansion, the algorithm will prove well-suited to parallelization.

Combining Knowledge and Search to Yield Infallible Endgame Programs

Wilhelm Barth

[18(3):148-159]   A provably correct program for the competition of passed Pawns in the KPKP endgame has been developed, using a method described due to Barth and Barth (1992). The method combines the application of strict rules with alpha-beta search. The rules cover a large part of the positions of the endgame. For each such position they define an interval guaranteed to contain the true value. An alpha-beta search finds the values for all positions not covered and removes uncertainties left by too wide intervals in rule-valued positions. Thus, the method yields a correct evaluation for every position and, furthermore, the rules governing the position or its successors provide some tutorial insight to the user about the reasons behind the evaluations. Moreover, automatic validation assures that mistakes in the rules will be discovered and then can be eliminated in dialogue.

Only a few simple rules are essential to the KPKP algorithm, all of which are well-known to skilful chess-players. Some of them are almost trivial, yet they have to be formulated with cautious precision and to be cast into an algorithmic format. Surprising oddities come to light in the process. The behaviour of the program has been tested by solving many studies and by analyzing some game positions discussed in the literature.

An Examination of the Endgame KBNKN

Steven J. Edwards and the Editorial Board

[18(3):160-167]   (Text still missing ...)

EDITORIAL

Bright and Beautiful, Great and Small

I. Samuel Herschberg and H. Jaap van den Herik

[18(3):133-134]   Who was the genius who discovered that an army marched better when in unison than when allowing the fastest hoplites to outpace those burdened down with heavy impediments? Could it be an early genius such as Xenophon, marching back his Ten Thousand through the wilds of Asia Minor? Or did the principle of a disciplined march in serried ranks come in as late as Alexander the Great?

Whoever invented, perfected or even orchestrated that way of proceeding physically, on the ground, in difficult terrain, had an immense edge on the undisciplined, the boastful, the indomitable individualists. Our best witness are the Romans who would march as though by clockwork.

It is not too far-fetched to apply the discipline of marching in an orderly way along a parallel front to what we see happening in computer chess nowadays. Not too long ago, the world was, it seemed, a contentious place in which only the hardest of hardware, marching ahead of all the rest, stood a chance of achievement. Such, we now think, would have been a throwback to prideful, Homeric times: the race would be to the swift, and to precious few among them only.

By all the signs we can read at the start of the academic year which will carry us into the late summer of 1996, the race is not to the swift, or not so exclusively. The battle is to the strong indeed, but those strong players differ widely in brawn, far more widely than they vary among themselves in sheer speed or brute-force features.

To unmix our metaphors: from what we can discern, we now see that the great and the small, the mighty workstations and the clever vest-pocket engines, march in parallel, presenting a united front, irresistibly and harmoniously progressing against silicon-only arrogance. All events scheduled for this academic year project the image of a formidable army marching in disciplined unison against its human opponents, with a remarkable unanimity: we, the machines, are united, we are disciplined and we have harmonized any discrepancies that might distract us from showing that we are your betters.

Three varieties of event are on the books which will hint at the march of our mechanical masters, if such should indeed materialize. Let us take them in turn. We are expectant of many a meeting between computers, human beings excluded except as humble operators. First and foremost among these chip-chip-chip events will be the WMCC in Paderborn. More interesting to readers of this Journal will be those mixed occasions - call them SiC, Silicon against Carbon - where chippies and hippies stand on an equal footing; thus, three key words will have to identify them, say Harvard, AEGON, and to be topped off by Kasparov.

Finally, ahead of us, excitingly, there is a conference on Advances in Computer Chess. Your Editors take a pleasantly congratulatory position on this: any eighth edition of a triennial book marks its 21st birthday, the traditional coming of age. Thus, by analogy, one of this year's events will constitute the true adulthood of computer chess - hurray for its majority!

It will not have escaped our readers's attention that, taking them for all in all, we have noticed a parallel disciplined march from the slow and humble to the bright, brash and bold: whatever their physical strength, they now seem united; whether great or small, it would be brazen to describe this season's engines as anything but bright and beautiful.