Note: [1] This work was partly supported by the ESPRIT Basic Research Action No. 7141 (ALCOM II) and by the Leibniz award fund of B. Monien from the DFG (German Research Association) under grant Mo 476/99.
Note: [*] The authors are with the University of Paderborn, Department of Mathematics and Computer Science, 33095 Paderborn, Germany. Email: johta2@uni-paderbom.de.
Abstract: 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 en 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 a-p 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 on 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, every selection step selecting a set of leaves for expansion, the algorithm will prove well-suited to parallelization.
DOI: 10.3233/ICG-1995-18302
Journal: ICGA Journal, vol. 18, no. 3, pp. 135-147, 1995
