Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/76EEE5E2-BB2A-4E1F-8F18-F94FBA4574E0 | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.85481 | - |
| Language | en | - |
| Extent | 76 pages | el |
| Title | Monte Carlo Tree Search for the “Diplomacy” Multi-agent Strategic Game | en |
| Title | Δενδρική αναζήτηση Monte Carlo στο πολυπρακτορικό στρατηγικό παίγνιο “Diplomacy” | el |
| Creator | Theodoridis Alexios | en |
| Creator | Θεοδωριδης Αλεξιος | el |
| Contributor [Thesis Supervisor] | Chalkiadakis Georgios | en |
| Contributor [Thesis Supervisor] | Χαλκιαδακης Γεωργιος | el |
| Contributor [Committee Member] | Lagoudakis Michail | en |
| Contributor [Committee Member] | Λαγουδακης Μιχαηλ | el |
| Contributor [Committee Member] | Deligiannakis Antonios | en |
| Contributor [Committee Member] | Δεληγιαννακης Αντωνιος | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content Summary | 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. | el |
| Content Summary | O γενικός όρος Δενδρική Αναζήτηση 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 Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2020-05-15 | - |
| Date of Publication | 2020 | - |
| Subject | Artificial intelligence | en |
| Subject | Multi-agent systems | en |
| 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 | en |
| Bibliographic Citation | Αλέξιος Θεοδωρίδης, "Δενδρική αναζήτηση Monte Carlo στο πολυπρακτορικό στρατηγικό παίγνιο “Diplomacy”", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2020 | el |
Copyright © DIAS 2013
