Evaluating the Complexity of Players’ Strategies using MCTS Iterations

摘要

Monte Carlo Tree Search (MCTS) does not require any prior knowledge about a game to play, except for its legal moves and end conditions. Thus, the same MCTS player can be applied (almost) as it is to a wide variety of games. Accordingly, MCTS may be used as a touchstone to evaluate artificial players on different games. In this paper, we propose to use MCTS to qualitatively evaluate the strength of artificial players as the minimum number of iterations that MCTS needs to perform equivalently to the target player. We define this value as the 'MCTS complexity' of the target player. We introduce a bisection procedure to compute the MCTS complexity of a player and present experiments to evaluate the proposed approach on three games: Connect4, Awari, and Othello. Initially, we apply our approach to compute the MCTS complexity of players implemented using MCTS with a known number of iterations, next to players using different strategies. Our preliminary results show that our approach can identify the number of iterations used by MCTS target players. When applied to players implementing unknown strategies, it produces results that are coherent with the underlying players’ strength, assigning higher values of MCTS complexity to stronger players. Our results also suggest that, by using iterations to evaluate the strength of players, we may be able to compare the strength of algorithms that would be incomparable in practice (e.g. a greedy strategy for Connect4 and alpha-beta pruning for Awari).