Plausible Move Generation in Two-Player Complete Information Games Using Static Evaluation
Grimbergen, R. and Matsubara, H. (2001)
Journal of the Japanese Society for Artificial Intelligence, Vol.16, No.1
Abstract
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.