Enhancing Search Efficiency by Using Move Categorization Based on Various Game Progress Values in Amazons
Higashiuchi, Y. and Grimbergen, R. (2005).
in: The 10th Game Programming Workshop in Japan (GPW2005),
pp. 97--103, Kanagawa, Japan.
Abstract
Amazons is a two-player perfect information game with an average number of legal moves that is
higher than chess, shogi or Go. Our aim is to improve the search efficiency of
an Amazons program by finding good moves to search first, thus improving the efficiency of
alpha-beta search. In earlier work, we established that a static move ordering scheme has
important problems and that move ordering needs to be changed as the game progresses. The number
of moves from the start of the game was used as a simple method to measure game progress and this
improved the playing strength of our Amazons program. However, move number might be a too simplistic
method and positions where using move number as progress value gives the wrong results can easily
be constructed. In this paper we propose three other methods to measure game progress:
using territory, using mobility and a combination of territory and mobility. We then compare
the performance of the four different methods for measuring game progress using self-play experiments.
These experiments indicate that territory is the most promising of the four methods,
but the results are not clear enough to warrant a definite conclusion.