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