Single Player Monte-Carlo Tree Search Based on the Plackett-Luce Model

Authors

  • Felix Mohr Universidad de La Sabana, Chía, Colombia
  • Viktor Bengs Paderborn University, Germany
  • Eyke Hüllermeier Paderborn University, Germany

Keywords:

Sampling/Simulation-based Search

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.

Downloads

Published

2021-05-18

How to Cite

Mohr, F., Bengs, V., & Hüllermeier, E. (2021). Single Player Monte-Carlo Tree Search Based on the Plackett-Luce Model. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12373-12381. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17468

Issue

Section

AAAI Technical Track on Search and Optimization