Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/76EEE5E2-BB2A-4E1F-8F18-F94FBA4574E0 | ||
| Year | 2020 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Alexios Theodoridis, "Monte Carlo Tree Search for the “Diplomacy” Multi-agent Strategic Game", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2020 https://doi.org/10.26233/heallink.tuc.85481 | ||
| Appears in Collections |
In this thesis, we explore the application of Monte Carlo Tree Search in the “Diplomacy” multi-agent strategic board game. Diplomacy is a game of high complexity; though it is a game with full observability, the players’ actions are simultaneous. This renders any attempted MCTS implementation challenging, because each action has to be combined with the unknown beforehand, simultaneous actions of six other opponents, thus resulting in a non-predictable outcome. To the best of our knowledge, this is the first work to employ MCTS in the game of Diplomacy. In our work we developed and experimented with several variants of the MCTS algorithm, differentiating in each one of them the amount and quality of domain knowledge provided to the main algorithm. We attempted to keep this domain knowledge to a minimum, while at the same time making the approach worthwhile in terms of time required for effective decision-making. In the core of our MCTS approach lies the well-known “bandit method” Upper Confidence Bounds for Trees (UCT), which attempts to strike a balance between exploration and exploitation during the search tree creation. We provide a thorough experimental evaluation of our approach, in which we systematically compare the performance of our agents against each other and against other known agents, including the to date most successful Diplomacy agent, “D-Brane”. Our results show that several of our agents are quite competitive in this domain, exhibiting as they do performance which is comparable and, in some instances, superior to that of D-Brane. Interestingly, the MCTS agents consistently beat D-Brane in tournaments in which one MCTS agent faces one D-Brane agent and several other opponents. Our experiments also demonstrate that carefully injecting high quality domain knowledge into the MCTS algorithm, improves its performance significantly. Finally, our thesis resulted in the creation of a basic computational framework that allows further research on using MCTS for the game of Diplomacy.
Copyright © DIAS 2013
