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).

Evaluating the complexity of players' strategies using MCTS iterations

Lanzi P. L.
2019-01-01

Abstract

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).
2019
IEEE Conference on Computatonal Intelligence and Games, CIG
978-1-7281-1884-0
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1133159
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact