Analyzing Competitive Coevolution across Families of N-Player Games through Tree Search

In this work, we examine Monte Carlo tree search (MCTS) as an adaptive benchmark for competitive coevolution, both as a method for characterizing individual solutions, and as a measure of global progress throughout a coevolutionary run. We find that MCTS provides a much more practical measurement of solution quality than existing methods of comparing to randomly-sampled solutions. Additionally, we introduce a class of n-player games for which MCTS can be shown to have comparable performance for different n, allowing for the characterization of how coevolution performs in games with different numbers of players. We demonstrate these techniques for n-player Nim and an n-player variant of Othello.