University of Macedonia Economic and Social Sciences
Decision making in multiplayer environments: application in backgammon variants
Abstract
dc:descriptionTesauro’s TD-Gammon was the first major success of machine learning and artificial intelligence in general, when it demonstrated world-class performance against the human backgammon champion of that time. Even more impressively, the method used required little expert knowledge, relying on self-playing and training neural networks using reinforcement learning. However, apart from standard backgammon, several – yet unexplored – variants of the game exist, which use the same board, number of checkers and dice, but have different rules for moving the checkers, starting positions or movement direction. In this thesis we focus our research on three such popular variants in Greece and neighboring countries, named Portes, Plakoto, and Fevga (collectively called Tavli). Motivated by the successful methods of TD-Gammon, we extend and devise new reinforcement learning methods for building artificial intelligent agents and show that expert-level play can also be achieved in these games. All the resulting agents created in this thesis are packaged in a freely available program, PALAMEDES, where everyone can play against the AI. To test the effectiveness of our approach, PALAMEDES participated in two backgammon Computer Olympiads, in 2011 and 2015, with opponents some of the best backgammon-playing programs in the world, emerging victorious in both of them. Additionally, we used the trained agents and self-play experiments to analyze key characteristics of these games for the first time, identifying one major flaw in the Fevga variant. The resulting statistics are then used to devise better strategies when playing in a match setting.Finally, in order to facilitate later research efforts, we devised a framework called bcdGammon for reducing/extending the complexity of backgammon games, preserving the key characteristics of the originals.
Degree
thesis:*- Grantor dc:publisher
- University of Macedonia Economic and Social Sciences
- Year dc:date
- 2015
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Papahristou, Nikolaos
- Παπαχρήστου, Νικόλαος
Subjects
dc:subject × 13Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/43622