Introduction

Without knowing about Slate's 1984 article we independently reinvented his original ``interior-node score bounds'' [190]. Based thereon, we developed our own so-called ``interior-node recognizers'' and have used them in our chess program DARKTHOUGHT [96] since its tournament début at the 8th World Computer-Chess Championship (WCCC) in Hong Kong, May1995.

DARKTHOUGHT is a fast yet sophisticated alpha-beta searcher using PVS/NEGASCOUT [51,174] with state-of-the-art enhancements like extended and normal futility pruning [95,182,216], internal iterative deepening [7,184], dynamic move ordering (history+killer heuristic) [3,76,180,183,191], recursive null-move pruning [20,62,77], selective extensions [7,17], and an extended transposition table [161,191]. DARKTHOUGHT routinely reaches 200K nodes per second (nps) and search depths of 11-13 plies in normal middlegame positions at tournament time-controls on a 500MHz DEC Alpha-21164a PC164 workstation. The search speed often doubles in endgame positions and actually peaks at 750K nps on the aforementioned hardware.

To the best of our knowledge, there exist no other published works about interior-node recognition than Slate's article written 14 years ago. At least somewhat related are two equally old articles by Beal who explored how to mix heuristic and perfect evaluations [22,23]. In contrast to Slate's disjoint score bounds for these different kinds of evaluations (see Section 1.4.3), Beal's ``nested minimax'' solution requires the search to back up multiple values that indicate the degree of reliability for the resulting scores. But Beal's scheme combines poorly with alpha-beta pruning because it substantially reduces the number of possible cutoffs. Regarding research in another area, private communication with J. Schaeffer revealed that the reigning World Man-Machine Checkers Champion CHINOOK [176,179] employs techniques that are similar in concept to interior-node recognition. Unfortunately, however, the CHINOOK team has not yet published anything as to this respect.

The strongest chess programs running on supercomputers of the early 1980s barely reached search depths of 8 plies in the middle game while processing around 20K nps. Thence, it is hardly surprising that Slate's article does not mention any efficiency problems related to the implementation of interior-node recognizers. This seems to have been no big issue back in 1984 because slow searchers usually tend to invest much effort into accurate evaluations. But at today's speeds of several hundred thousand nodes per second, the efficiency of the whole recognizer implementation matters a lot.

In the following sections we discuss and explain in detail how we solved all the conceptual and efficiency problems related to interior-node recognition if applied by a modern high-performance chess program. We seamlessly integrated interior-node recognition with the rest of our search (e.g. transposition tables) while never comprising any speed, knowledge, or accuracy. Our design and implementation proved their practical viability under tough tournament conditions during the 15th World Microcomputer Chess Championship (WMCC) in Paris, October 1997. The version of DARKTHOUGHT competing there contained a lot of recognizers for many different types of endgame positions. With all its recognizers enabled and running on a cooled 767MHz DEC/Kryotech Alpha-21164a workstation DARKTHOUGHT surpassed the magic speed limit of 1M nps during this event [82,97].



Created by Ernst A. Heinz, Thu Dec 16 23:28:11 EST 1999