AN ANALYSIS OF UCT IN MULTI-PLAYER GAMES

Article type: Research Article

Authors: Sturtevant, Nathan¹

Affiliations: Department of Computing Science, University of Alberta

Note: [1] University of Alberta, Dept. of Computing Science, Edmonton, Alberta, email: [email protected]

Abstract: The UCT algorithm has been exceedingly popular for Go, a two-player game, significantly increasing the playing strength of Go programs in a very short time. This paper provides an analysis of the UCT algorithm in multi-player games, showing that UCT is computing a mixed-strategy equilibrium, as opposed to maxn, which computes a pure-strategy equilibrium. We analyze the performance of UCT in several known domains and show that it performs as well or better than existing algorithms. We also test several well-known UCT learning and playout rules. We suggest two criteria, branching factor and n-ply state variance. The experiments show that they are correlated with the success of the techniques.

DOI: 10.3233/ICG-2008-31402

Journal: ICGA Journal, vol. 31, no. 4, pp. 195-208, 2008