On Games with Random-Turn Order and Monte Carlo Perfectness

Article type: Research Article

Authors: Althöfer, Ingo¹

Affiliations: Jena, Germany

Note: [1] Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, 07737 Jena, Germany. Email: [email protected]

Note: [2] The contribution is an elaborated and enriched version of the author’s contribution to the 13th Advances in Computer Games conference (ACG2011) in Tilburg, The Netherlands. We are pleased to recognize Springer Verlag for their cooperation.

Abstract: In a game, pure Monte Carlo search with parameter T means that for each feasible move T random games are generated. The move with the best average score is played. We call a game “Monte Carlo perfect” when this straightforward procedure converges to perfect play for each position, when T goes to infinity. Most popular games like Go, Hex, and Amazons are NOT Monte Carlo perfect. In this paper, two-player zero-sum games are investigated where the turn-order is random: always a fair coin flip decides which player acts on the next move. A whole class of such random-turn games is proven to be Monte Carlo perfect. The result and generalisations are discussed, with example games ranging from very abstract to very concrete.2

DOI: 10.3233/ICG-2011-34402

Journal: ICGA Journal, vol. 34, no. 4, pp. 179-190, 2011