Συντάχθηκε 11-05-2020 14:08
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΑΛΕΞΙΟΣ ΘΕΟΔΩΡΙΔΗΣ
θέμα
Δενδρική Αναζήτηση Monte Carlo στο Πολυπρακτορικό Στρατηγικό Παίγνιο “Diplomacy”
Monte Carlo Tree Search for the “Diplomacy” Multiagent Strategic Game
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης
Αναπληρωτής Καθηγητής Αντώνιος Δεληγιαννάκης
Περίληψη
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.
Abstract
Monte Carlo Tree Search (MCTS) is a collective name for a family of methods seeking to identify optimal decisions in a given domain, while making use of the results of simulated outcomes in the search space. MCTS has received considerable interest in the past decade due to its demonstrated effectiveness in a number of domains, including its much-celebrated success in the game of Go.
In this thesis, we explore the application of MCTS 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 (i.e., a player’s “move order” for this domain) 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 at the creation 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 others, 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.
Σύνδεσμος εκδήλωσης: https://meetingsemea.webex.com/meetingsemea/j.php?MTID=macbb650f56d4c8673eb11d1ef34090b0
Τόπος: Η παρουσίαση θα γίνει με τηλεδιάσκεψη: https://meetingsemea.webex.com/meetingsemea/j.php?MTID=macbb650f56d4c8673eb11d1ef34090b0
Έναρξη: 13/05/2020 12:00
Λήξη: 13/05/2020 13:00
