Candidate Relevance Analysis for Selective Search in Shogi
Grimbergen, R. (1999)
9th Advances in Computer Chess Conference, Paderborn, Germany
Abstract
In this paper we present Candidate Relevance Analysis (CRA), a method
for plausible move generation in two-player perfect information
games. Plausible move generation has not been widely used because
of the risks of losing important search candidates. However, there are
search domains where the number of search candidates is too large to
do a complete search. CRA limits the number of search candidates by
analysing the relevance of the candidates with respect to the goal
of a game, discarding all candidates judged irrelevant. CRA can
easily be incorporated in alpha-beta search. Furthermore, the knowledge
acquired by CRA can be used to improve the move ordering, thus
improving the efficiency of alpha-beta search. In the domain of
shogi (Japanese chess), CRA reduces the number of candidates by
39.7%, while maintaining an accuracy of 99%. Also, in shogi
alpha-beta search with CRA outperforms full-width alpha-beta search
even for small search depths.