Plausible Move Generation Using Move Merit Analysis with Cut-Off Thresholds in Shogi
Grimbergen, R. (2000)
In: Proceedings of CG2000, the Second International Conference on Computers and Games, Hamamatsu, Japan, October 2000
Abstract
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.