Plausible Move Generation in Two-player Complete Information Games Using Static Evaluation

概要

論文の詳細を見る
In games where the average number of legal moves is too high, it is not possible to do full-width search to a depth sufficient for good play. A way to achieve deeper search is to reduce the number of moves to search. In this paper a new method for Plausible Move Generation (PMG)will be presented that considerably reduces the number of search candidates. This plausible move generation method will be applied to shogi. We will present different types of plausible move generators for different types of moves, based on the static evaluation of a shogi position. Test results show that in shogi this set of plausible move generators reduces the number of moves to search by 33.2% on average. Plausible move generation is still very accurate: 99.5% of all expert moves in 12097 test positions were generated by our method. Search based on plausible move generation has also been compared with search without plausible move generation. First, in 298 tactical shogi problems, using plausible move generation increased the number of solved problems with 34%. Second, in a self-play experiment a shogi program based on plausible move generation beat a shogi program based on full-width search in 80% of the games.
社団法人　人工知能学会の論文
2001-11-01