グリムベルゲン　ライエル   Ｇｒｉｍｂｅｒｇｅｎ　Ｒｅijer    所属   コンピュータサイエンス学部 コンピュータサイエンス学科    職種   教授
言語種別	英語
発行・発表の年月	2000/10
形態種別	国際会議論文
査読	査読あり
標題	Plausible Move Generation Using Move Merit Analysis with Cut-Off Thresholds in Shogi
執筆形態	単著
掲載誌名	In: T.A.Marsland and I.Frank (Eds.), Computer and Games, Second International Conference, CG 2000
出版社・発行元	Hamamatsu, Japan
巻・号・頁	LNCS 2063,pp.315-332
概要	In games where the number of legal moves is too high, it is not possible to do full-width search to a depth sufficient for good play. Plausible move generation (PMG) is an important search alternative in such domains. In this paper we propose a new method for plausible move generation in shogi. During move generation, Move Merit Analysis (MMA) gives a value to each move based on the plausible move generator(s) that generated the move. These values can be used for different cut-off schemes. We investigate the following alternatives: 1) Keep all moves with a positive MMA value; 2) Order the moves according to their MMA value and use cut-off thresholds to keep the best N moves. PMG with MMA and cut-off thresholds can save between 46% and 68% of the total number of legal moves with an accuracy between 99% and 93%. Tests show that all versions of shogi programs using PMG with MMA outperform an equivalent shogi program using full-width search. It is also shown that MMA is vital for our approach. Plausible move generation with MMA performs much better than plausible move generation without MMA. Cut-off thresholds improve the performance for N=20 or N=30.