ICGA Journal: The Journal of the Computer Games Community

This paper is intended to fill a gap in the documentation of Hitech, the highest-rated chess computer in the world. Thus far, publications have appeared on the move-generator design (Ebeling and Palay, 1984), the design and construction of the Hitech machine and software (Ebeling, 1986), and the artificial-intelligence implications of the design (Berliner and Ebeling, 1986). Here we fill in some of the details of less general interest, but of interest to those that build chess programs and follow their development. Most of the information is chess-specific. What is of general interest is the developmental history of Hitech in which we intend to show how a complex system evolves with unexpected turns and twists in the road. In projects such as this, it is not possible to determine the full effect of any change, nor can one anticipate the vehicle’s needs over more than one change at a time. At this writing, we feel that the pattern-recognizer structure described herein is principally responsible for Hitech’s success. We have not begun fully to exploit this structure, so the potential for large further improvement remains.

Conventional parallelizations of the alpha-beta (α-β) algorithm have met with limited success. With current algorithms, beyond 10 processors additional ones are of little benefit. This paper introduces speculative computing as a means of extending the effective number of processors that can be used. Scout processes speculatively search ahead in the tree, looking for wins and losses of material at a depth not normally achievable by an α-β search program. This tactical information is communicated back to a regular α-β searching chess program and used in the decision of which move to play. In this way, the effective search depth is extended. The deeper tactical searches allows the chess program to 1) find winning lines not normally possible, and 2) avoid making moves that deeper searches show to lose material. These ideas have been tested empirically as part of the chess program Phoenix.

The endgame KNNKP(h) is investigated in the ultimate sense, giving rise to a full data-base including all conversions of that game. It turns out that the only possible conversions are to KNNKA, where A stands for any of Q, R, B or N, and to KNKP(h). Other theoretically possible conversions are excluded by lemmatics, i.e., the application of theorem-proving to heuristics. The paper distinguishes prospective analysis, retrospective analysis and the backward-chaining construction. The latter is complicated by the presence of the two conversions. It is believed that our database is the first one to deal with a black Pawn, pursuing all the consequences beyond conversion in an ultimate sense. An anthology of results is presented as well as an application to a famous position (Smyslov-Lilienthal, 1941), now shown to have been erroneously analysed by several authors.

The notion of mobility has long been considered to be of fundamental importance in positional evaluation. Several different definitions of mobility exist, and they all show a high correlation with having a good position and eventually winning the game, as shown by experiments. However, this article contests the fundamental importance of mobility. Some alternative, and proposedly more useful, definitions of mobility are given. It is also argued that an extensive, second-order mobility analysis is not cost-effective.