Abstract
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.
Get full access to this article
View all access options for this article.