Institutional Repository
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Monte Carlo Tree Search for the “Diplomacy” Multi-agent Strategic Game

Theodoridis Alexios

Simple record


URIhttp://purl.tuc.gr/dl/dias/76EEE5E2-BB2A-4E1F-8F18-F94FBA4574E0-
Identifierhttps://doi.org/10.26233/heallink.tuc.85481-
Languageen-
Extent76 pagesel
TitleMonte Carlo Tree Search for the “Diplomacy” Multi-agent Strategic Gameen
TitleΔενδρική αναζήτηση Monte Carlo στο πολυπρακτορικό στρατηγικό παίγνιο “Diplomacy”el
CreatorTheodoridis Alexiosen
CreatorΘεοδωριδης Αλεξιοςel
Contributor [Thesis Supervisor]Chalkiadakis Georgiosen
Contributor [Thesis Supervisor]Χαλκιαδακης Γεωργιοςel
Contributor [Committee Member]Lagoudakis Michailen
Contributor [Committee Member]Λαγουδακης Μιχαηλel
Contributor [Committee Member]Deligiannakis Antoniosen
Contributor [Committee Member]Δεληγιαννακης Αντωνιοςel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitTechnical University of Crete::School of Electrical and Computer Engineeringen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Content SummaryIn 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. el
Content SummaryO γενικός όρος Δενδρική Αναζήτηση Monte Carlo (Monte Carlo Tree Search - MCTS) περιγράφει μια κατηγορία αλγορίθμων εύρεσης βέλτιστων αποφάσεων σε ένα δοσμένο περιβάλλον, χρησιμοποιώντας τα αποτελέσματα προσομοιωμένων εκβάσεων στο χώρο αναζήτησης. Τα τελευταία χρόνια η Δενδρική Αναζήτηση Monte Carlo είναι ιδιαίτερα δημοφιλής λόγω της αποδεδειγμένης αποτελεσματικότητάς της σε μια σειρά από περιβάλλοντα, συμπεριλαμβανομένου του εξαιρετικά δύσκολου για τον άνθρωπο παιχνιδιού Go. Στην παρούσα διπλωματική εργασία, ερευνούμε την εφαρμογή αλγορίθμων MCTS στο πολυ-πρακτορικό στρατηγικό παίγνιο «Diplomacy». Το Diplomacy είναι ένα παιχνίδι υψηλής πολυπλοκότητας. Αν και είναι ένα πλήρως παρατηρήσιμο παίγνιο (όχι μερικής παρατηρησιμότητας), απαιτεί ταυτόχρονες ενέργειες εκ μέρους των επτά συμμετεχόντων αντιπάλων. Αυτό αυξάνει τη δυσκολία της εφαρμογής της MCTS προσέγγισης, επειδή κάθε ενέργεια (εντολή κίνησης σε αυτό το περιβάλλον) σε συνδυασμό με τις ενέργειες των υπόλοιπων (έξι στον αριθμό) αντιπάλων, καταλήγει σε μη προβλέψιμο αποτέλεσμα. Στη δουλειά μας προτείναμε και πειραματιστήκαμε με πολλαπλές εκδοχές του αλγόριθμου MCTS, διαφοροποιώντας την ποσότητα και την ποιότητα της σχετικής με το περιβάλλον γνώσης που χρησιμοποιούμε σε κάθε μία από αυτές. Προσπαθήσαμε να μην παρέχουμε υπερβολική γνώση του περιβάλλοντος στον πράκτορα ώστε να κρατήσουμε την υλοποίησή του όσο πιο γενική και εγγύτερη στην κλασική MCTS προσέγγιση γινόταν. Ταυτόχρονα, προσπαθήσαμε να κτίσουμε έναν αποτελεσματικό αλγόριθμο που να βελτιστοποιεί τις αποφάσεις του σε συνάρτηση με το χρόνο που έχει στη διάθεσή του για τη λήψη τους. Στο κέντρο της MCTS προσέγγισής μας βρίσκεται μια γνωστή μέθοδος «κουλοχέρη», η λεγόμενη μέθοδος χρήσης “Άνω Ορίου Εμπιστοσύνης για Δέντρα” (Upper Confidence Bounds for Trees - UCT), η οποία προσπαθεί να ισορροπήσει μεταξύ εξερεύνησης και εκμετάλλευσης πληροφορίας κατά τη δημιουργία του δέντρου αναζήτησης. Η εργασία μας παρέχει μια εκτενή και προσεκτική πειραματική αξιολόγηση της προσέγγισης μας. Συγκεκριμένα, παρέχουμε μια συστηματική αξιολόγηση της απόδοσής των αλγορίθμων μας, συγκρίνοντάς τους μεταξύ τους καθώς και με άλλους αντιπάλους πράκτορες γνωστούς από τη βιβλιογραφία. Στους τελευταίους περιλαμβάνεται και ο “D-Brane”, o πλέον επιτυχημένος ως τώρα πράκτορας στο παιχνίδι Diplomacy. Τα αποτελέσματα δείχνουν ότι αρκετοί από τους πράκτορες μας αποδεικνύονται εξαιρετικά ανταγωνιστικοί σε αυτό το απαιτητικό παιχνίδι, με απόδοση που είναι συγκρίσιμη και ορισμένες φορές καλύτερη από αυτήν του D-Brane. Είναι σημαντικό το ότι οι πράκτορές μας κερδίζουν συστηματικά τον D-Brane σε τουρνουά στα οποία συμμετέχει ένας MCTS πράκτορας, ένας D-Brane πράκτορας, και πέντε άλλοι, διαφορετικοί, αντίπαλοι. Τα πειράματά μας επίσης αποδεικνύουν ότι η προσεκτική εισαγωγή καλής ποιότητας γνώσης πεδίου στον MCTS αλγόριθμο, βελτιώνει την απόδοσή του σημαντικά. Σε αυτή τη δουλειά αναπτύσσουμε διάφορες εκδοχές της προσέγγισής μας και μια συστηματική τους αξιολόγηση. Τέλος, η διπλωματική μας προσέφερε τη δημιουργία ενός βασικού υπολογιστικού πλαισίου που επιτρέπει την περαιτέρω έρευνα σχετικά με την χρήση MCTS τεχνικών στο παιχνίδι Diplomacy.el
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2020-05-15-
Date of Publication2020-
SubjectArtificial intelligenceen
SubjectMulti-agent systemsen
Bibliographic CitationAlexios 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, 2020en
Bibliographic CitationΑλέξιος Θεοδωρίδης, "Δενδρική αναζήτηση Monte Carlo στο πολυπρακτορικό στρατηγικό παίγνιο “Diplomacy”", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2020el

Available Files

Services

Statistics