Note: [1] This article is a revised and updated version of the following two contributions: (1) Nijssen, J.A.M. and Winands, M.H.M. (2012). An Overview of Search Techniques in Multi-Player Games. Computer Games Workshop at ECAI 2012, pp. 50–61, Montpellier, France; (2) Nijssen, J.A.M. and Winands, M.H.M. (2011). Enhancements for Multi-Player Monte-Carlo Tree Search. Computers and Games (CG 2010) (eds. H.J. van den Herik, H. Iida, and A. Plaat), Vol. 6515 of LNCS, pp. 238–249, Springer-Verlag, Berlin, Germany.
Note: [2] Games and AI Group, Department of Knowledge Engineering, Faculty of Humanities and Sciences, Maastricht University, Email: pim.nijssen@maastrichtuniversity.nl, m.winands@maastrichtuniversity.nl
Abstract: In this article we investigate how three multi-player search policies, namely maxn, paranoid, and Best-Reply Search, can be embedded in the MCTS framework. The performance of these search policies is tested in four different deterministic multi-player games with perfect information by running self-play experiments. We show that MCTS with the maxn search policy overall performs best. Furthermore, we introduce a multi-player variant of the MCTS-Solver. We propose three update rules for solving nodes in a multi-player MCTS tree. The experimental results show that the multi-player variant of the MCTS-Solver is a genuine improvement for MCTS in multi-player games.
DOI: 10.3233/ICG-2013-36102
Journal: ICGA Journal, vol. 36, no. 1, pp. 3-21, 2013
