Monte Carlo Tree Search in The Octagon Theory

Hugo Fernandes, Pedro Nogueira, Eugénio Oliveira

2014

Abstract

Monte Carlo Tree Search (MCTS) is a family of algorithms known by its performance in difficult problems that cannot be targeted with the current technology using classical AI approaches. This paper discusses the application of MCTS techniques in the fixed-length game The Octagon Theory, comparing various policies and enhancements with the best known greedy approach and standard Monte Carlo Search. The experiments reveal that the usage of Move Groups, Decisive Moves, Upper Confidence Bounds for Trees (UCT) and Limited Simulation Lengths turn a losing MCTS agent into the best performing one in a domain with estimated gametree complexity of 10293, even when the provided computational budget is kept low.

Paper Citation

in Harvard Style

Fernandes H., Nogueira P. and Oliveira E. (2014). Monte Carlo Tree Search in The Octagon Theory . In Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-758-015-4, pages 328-335. DOI: 10.5220/0004757603280335

in Bibtex Style

@conference{icaart14,
author={Hugo Fernandes and Pedro Nogueira and Eugénio Oliveira},
title={Monte Carlo Tree Search in The Octagon Theory},
booktitle={Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2014},
pages={328-335},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004757603280335},
isbn={978-989-758-015-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - Monte Carlo Tree Search in The Octagon Theory
SN - 978-989-758-015-4
AU - Fernandes H.
AU - Nogueira P.
AU - Oliveira E.
PY - 2014
SP - 328
EP - 335
DO - 10.5220/0004757603280335