ICGA Journal: The Journal of the Computer Games Community

This paper describes a High-performance parallel tree-search algorithm that uses Dynamic Tree Splitting (DTS) for searching α β minimax game trees. The Algorithm Divides the search tree among several processors on a shared-memory parallel machine. The paper deals with the following topics: (1) the DTS algorithm, (2) analyzing α β to select split points, (3) performance results of the algorithm, and (4) analysis of the results to see where further improvements might occur.

Current endgame databases provide optimal sequences of moves from a given position to conversion or to mate. They do not investigate whether the given position is legitimate. This contribution considers the database as a model of the particular chess configuration under investigation and attempts to classify the positions in legitimate and illegitimate positions. Assuming a position to be legitimate if it can be reached from the starting position by legal moves only, the question is what means do we need to prove the legitimacy of a position.

For this purpose, we first define three new concepts initially illegitimate, derivedly illegitimate and isolatedly illegitimate. Then we propose a constructive procedure which enables us to show that a position can be reached. Related to the new concepts we introduce a broad definition of illegitimacy (based on initially illegitimate only) and a narrow definition (taking into account also derivedly illegitimate). For both cases we have examined the 3- and 4-man databases of which results are given. Further research of 5- and 6-man databases is envisaged.

A new domain-independent pruning method is described that guarantees returning a correct game value. Even though α β -based chess programs are already searching close to the minimal tree, there is still scope for improvement. Our idea hinges on the recognition that the game tree has two types of node those where cut-offs occur, and those that must be fully explored. In the latter case one of the moves is best and yields the subtree value, thus for the remaining alternatives it is enough to show their inferiority. This otters an opportunity for pruning, while introducing some potential for uncertainty in the search process. There are two cases of interest. One considers the immediate alternatives to the Principal Variation itself, here a new safe cut-off is presented. The other is a proposal for an unsafe generalization, one which offers substantial search reduction but with the potential for control of the error probability. Experiments with the new pruning method show some savings in the search.