Monte Carlo *-Minimax Search

Lanctot, Marc; Saffidine, Abdallah; Veness, Joel; Archibald, Christopher; Winands, Mark H. M.

Monte Carlo *-Minimax Search

Marc Lanctot, Abdallah Saffidine, Joel Veness, Christopher Archibald, Mark H. M. Winands

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 580-585.

Abstract

This paper introduces Monte Carlo *-Minimax Search (MCMS), a Monte Carlo search algorithm for turned-based, stochastic, two-player, zero-sum games of perfect information. The algorithm is designed for the class of of densely stochastic games; that is, games where one would rarely expect to sample the same successor state multiple times at any particular chance node. Our approach combines sparse sampling techniques from MDP planning with classic pruning techniques developed for adversarial expectimax planning. We compare and contrast our algorithm to the traditional *-Minimax approaches, as well as MCTS enhanced with the Double Progressive Widening, on four games: Pig, EinStein Wurfelt Nicht!, Can't Stop, and Ra. Our results show that MCMS can be competitive with enhanced MCTS variants in some domains, while consistently outperforming the equivalent classic approaches given the same amount of thinking time.

Marc Lanctot, Abdallah Saffidine, Joel Veness, Christopher Archibald, and Mark H. M. Winands. 2013. Monte Carlo *-Minimax Search. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 580–585. https://ijcai.org/proceedings/2013/93

@inproceedings{ijcai2013p93,
  title     = {Monte Carlo *-Minimax Search},
  author    = {Lanctot, Marc and Saffidine, Abdallah and Veness, Joel and Archibald, Christopher and Winands, Mark H. M.},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {580--585},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/93},
}

TY  - CPAPER
TI  - Monte Carlo *-Minimax Search
AU  - Lanctot, Marc
AU  - Saffidine, Abdallah
AU  - Veness, Joel
AU  - Archibald, Christopher
AU  - Winands, Mark H. M.
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 580
EP  - 585
UR  - https://ijcai.org/proceedings/2013/93
ER  -