Note: [1] This paper is an extended and improved version of the CIG’08 paper “A comparative Study of Solvers in Amazons Endgames” (Kloetzer, Iida, and Bouzy, 2008). The current version is refereed by ICGA Journal referees.
Note: [2] Research Unit for Computers and Games, JAIST, j.kloetzer,iida@jaist.ac.jp
Note: [3] LIPADE - UFR de mathématiques et d’informatique, Université René Descartes, bruno.bouzy@parisdescartes.fr
Abstract: The game of the Amazons is a fairly young member of the class of territory games. Since few humans play the game, it is difficult to estimate the level of current programs. However, it is believed that humans could play much stronger than today’s programs, given sufficient training and incentives. With the more general goal of improving the playing level of Amazons programs in mind, we focus here on the playing of endgame positions. Our study compares two solvers, DFPN and WPNS, and three game-playing algorithms, Minimax with Alpha/Beta, Monte-Carlo Tree Search, and Temperature Discovery Search. We show that even though the computing process is quite expensive, traditional PNS-based solvers are best suited for the task of finding the best moves in a subgame of Amazons. No specific improvement is needed to classical game-playing engines to play well in the subdomain of Amazons endgames. Moreover, we show that Monte-Carlo Tree Search (MCTS), the new Amazons standard plays the Amazons endgames pretty well, despite their frequently occurring weaknesses in handling precise tasks such as solving.
DOI: 10.3233/ICG-2009-32303
Journal: ICGA Journal, vol. 32, no. 3, pp. 140-148, 2009
