Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/47FFB724-C399-400A-9204-0466FD08FCB5 | ||
| Year | 2014 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Konstantinos Panousis, "Real-time planning and learning in the "Settlers of Catan" strategy game", Diploma Work, School of Electronic and Computer Engineering, Technical University of Crete, Chania, Greece, 2014 https://doi.org/10.26233/heallink.tuc.18113 | ||
| Appears in Collections |
Monte Carlo Tree Search (MCTS) is a generic method for optimal decision making in a given domain.The technique operates by searching a decision tree that is progressively built via the -essentially random- sampling of potential action sequences.After its successful application in the two-player, perfect information game of Go, researchers are trying to obtain a better understanding of the MCTS strengths and weaknesses.In this thesis, we apply MCTS in the Settlers of Catan (SoC) strategy game, which is a non-deterministic, partially observable, multi-player strategic board game.We develop and evaluate three different enhancements in the tree policy of the main MCTS algorithm: namely, UCT, Bayesian UCT and Value of Perfect Information (VPI).These refined methods essentially constitute attempts to balance the exploration-exploitation dilemma in this domain.In addition, we created various heuristic strategies to cope with specific situations that may arise in the game; and, unlike most SoC automated players, our implementation also provides a simple negotiation scheme that gives our agent the ability to trade with other players.We note that this is possibly the first time that the MCTS algorithm is employed within a highly complex multi-agent environment.Moreover, this is the first time that the Bayesian UCT MCTS variant is used in the Settlers of Catan domain, and the first time that VPI is employed in conjunction with MCTS in general.We pit our agents against each other, and against existing AI implementations, including the strongest existing heuristic-based SoC automated player.Our results are very encouraging, and suggest that MCTS can benefit from the various tree policy enhancements implemented.The VPI agent, in particular, appears to be quite competitive, achieving performance that is comparable to thatof existing SoC AI players, even when operating within a computational budget that was actually significantly more restricted than theirs.
Copyright © DIAS 2013
