Plausible move generator
Posted: Fri Nov 09, 2012 11:27 pm
Hi All,
Recently I have taken a glance on an abstract written by Reijer Grimbergen talking about the possibility of making a selective move generator, here I transcript some parts of the abstract, has somebody tried a similar approach on their engine? thanks for the feedback.
Plausible Move Generation Using Move Merit Analysis with Cut-Off Thresholds in Shogi, Reijer Grimbergen
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.
Recently I have taken a glance on an abstract written by Reijer Grimbergen talking about the possibility of making a selective move generator, here I transcript some parts of the abstract, has somebody tried a similar approach on their engine? thanks for the feedback.
Plausible Move Generation Using Move Merit Analysis with Cut-Off Thresholds in Shogi, Reijer Grimbergen
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.