Authors:
Hugo Fernandes
;
Pedro Nogueira
and
Eugénio Oliveira
Affiliation:
Faculty of Engineering of the University of Porto, Portugal
Keyword(s):
Monte Carlo Tree Search (MCTS), Upper Confidence Bounds for Trees (UCT), Monte Carlo Search, Artificial Intelligence (AI), The Octagon Theory.
Related
Ontology
Subjects/Areas/Topics:
Agents
;
Artificial Intelligence
;
Bioinformatics
;
Biomedical Engineering
;
Enterprise Information Systems
;
Information Systems Analysis and Specification
;
Methodologies and Technologies
;
Operational Research
;
Simulation
;
State Space Search
;
Symbolic Systems
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.