グリムベルゲン　ライエル   Ｇｒｉｍｂｅｒｇｅｎ　Ｒｅijer    所属   コンピュータサイエンス学部 コンピュータサイエンス学科    職種   教授
言語種別	英語
発行・発表の年月	1999
形態種別	国際会議論文
査読	査読あり
標題	Candidate Relevance Analysis for Selective Search in Shogi
執筆形態	単著
掲載誌名	In: H.J.van den Herik and B.Monien (eds.), Advances in Computer Games 9
出版社・発行元	Van Spijk, Venlo, The Netherlands
巻・号・頁	pp.233-246
概要	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.