Single player monte-carlo tree search based on the Plackett-Luce model

Abstract

The problem of minimal cost path search is especially difficult when no useful heuristics are available. A common solution is roll-out-based search like Monte Carlo Tree Search (MCTS). However, MCTS is mostly used in stochastic or adversarial environments, with the goal to identify an agent's best next move. For this reason, even though single player versions of MCTS exist, most algorithms, including UCT, are not directly tailored to classical minimal cost path search. We present Plackett-Luce MCTS (PL-MCTS), a path search algorithm based on a probabilistic model over the qualities of successor nodes. We empirically show that PL-MCTS is competitive and often superior to the state of the art.

El problema de la búsqueda de rutas de coste mínimo es especialmente complejo cuando no se dispone de heurísticas útiles. Una solución común es la búsqueda basada en despliegue, como la Búsqueda de Árbol de Monte Carlo (MCTS). Sin embargo, la MCTS se utiliza principalmente en entornos estocásticos o adversarios, con el objetivo de identificar el mejor siguiente movimiento de un agente. Por esta razón, aunque existen versiones de MCTS para un solo jugador, la mayoría de los algoritmos, incluyendo UCT, no están directamente adaptados a la búsqueda clásica de rutas de coste mínimo. Presentamos Plackett-Luce MCTS (PL-MCTS), un algoritmo de búsqueda de rutas basado en un modelo probabilístico sobre las cualidades de los nodos sucesores. Demostramos empíricamente que PL-MCTS es competitivo y, a menudo, superior al estado del arte.