Συντάχθηκε 31-10-2016 09:31
από Esthir Gelasaki
Email συντάκτη: egelasaki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΕΜΜΑΝΟΥΗΛ ΚΑΡΑΜΑΛΕΓΚΟΥ
με θέμα
Δενδρική Αναζήτηση Monte Carlo στο Παιχνίδι Στρατηγικής "Άποικοι του Κατάν"
Monte Carlo Tree Search in the "Settlers of Catan" Strategy Game
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Αντώνιος Δεληγιαννάκης
Αναπληρωτής Καθηγητής Μιχαήλ Γ. Λαγουδάκης
Περίληψη
Παραδοσιακές μέθοδοι Τεχνίτης Νοημοσύνης χρειάζονται είτε υψηλή γνώση πάνω στον τομέα που εφαρμόζονται, είτε χρειάζονται αρκετό χρόνο ώστε να προσαρμοστούν. Η Δενδρική Αναζήτηση MonteCarlo (Monte Carlo Tree Search – MCTS) είναι μια μέθοδος αναζήτησης που συνδυάζει την ακρίβεια της δενδρικής αναζήτησης με την γενίκευση που προσφέρουν οι τυχαίες δειγματοληψίες. Η οικογένεια των αλγορίθμων MonteCarlo έχει επιτύχει αισιόδοξα αποτελέσματα σε κλασικά παιχνίδια, με πλήρη πληροφορία, όπως το επιτραπέζιο παιχνίδι Go. Στην εργασία μας, εφαρμόζουμε Δενδρική Αναζήτηση MonteCarlo στο μη-ντετερμινιστικό, επιτραπέζιο παιχνίδι στρατηγικής "Άποικοι του Κατάν". Αναπτύξαμε έναν πράκτορα που, για πρώτη φορά, λαμβάνει υπόψη όλες τις πτυχές του παιχνιδιού με καθόλου, εκ των προτέρων, γνώση του παιχνιδιού.
Στην εργασίας μας τρέχουμε πειράματα χρησιμοποιώντας τη μέθοδο ενισχυτικής μάθησης Αξία της Τέλειας Πληροφόρησης (Value of Perfect Information) και δύο μεθόδους «κουλοχέρη», την μέθοδο Άνω Όριο Συντελεστή (Upper Coefficient Bound) και μια επέκταση αυτής της μεθόδου - την μέθοδο Μπαεσιανού Άνω Ορίου Συντελεστή(Bayesian Upper Coefficient Bound). Στόχος αυτών των μεθόδων είναι να εξισορροπήσουν την σχέση εκμετάλλευσης-εξερεύνησης (exploration-exploitation problem) κατά την δημιουργία του δένδρου αναζήτησης.
Για πρώτη φορά στην σχετική με το Settlers of Catan βιβλιογραφία, αναπτύσσουμε έναν πράκτορα που χρησιμοποιεί MCTS ο οποίος λαμβάνει υπόψη όλους τους κανόνες του παιχνιδιού ενώ ταυτόχρονα μπορεί να διαπραγματευτεί ανταλλαγές με τους υπόλοιπους παίχτες. Επιπρόσθετα, συμπεριλάβαμε στον πράκτορα μια εναλλακτική στρατηγική αρχικής τοποθέτησης που υπάρχει στην βιβλιογραφία, και η οποία χρησιμοποιεί γνώση προερχόμενη από την ανάλυση συμπεριφοράς ανθρώπων κατά την τοποθέτηση κομματιών.
Στα πειράματά μας εξετάζουμε την απόδοση των μεθόδων μας όταν έρχονται αντιμέτωπες μεταξύ τους, ή με κατάλληλα επιλεγμένους αντιπάλους (benchmarks), όπως οι γνωστοί JSettlers agents. Επίσης, εξετάζουμε το πώς το βάθος και το πλήθος των προσομοιώσεων επηρεάζει τη απόδοση των αλγορίθμων μας. Τα αποτελέσματά μας υποδεικνύουν ότι η μέθοδος VPI με λιγότερες προσομοιώσεις είναι πιο ανταγωνιστική σε σχέση με τις μεθόδους ληστές, παρά το γεγονός ότι οι τελευταίες χρησιμοποιούν πολλαπλάσιες προσομοιώσεις. Επίσης, είναι σημαντικό να υπολογιστεί το βάθος των προσομοιώσεων στον αλγόριθμο, ώστε οι μέθοδοι να μην χάνονται σε ατέρμονες προσομοιώσεις απίθανων σεναρίων, αλλά ταυτόχρονα να μην τελειώνουν την εξερεύνηση, χωρίς να έχουν κάνει μια επαρκή εκτίμηση των επόμενων κινήσεων. Τέλος, τα πειράματά μας δείχνουν πως η εναλλακτική στρατηγική τοποθέτησης που εξετάσαμε βοηθάει στην αύξηση της απόδοσης του πράκτορά μας.
Abstract
Classic approaches to game AI require either a high quality of domain knowledge, or a long time to generate effective AI behavior. Monte Carlo Tree Search (MCTS) is a search method that combines the precision of tree search with the generality of random sampling. The family of MCTS algorithms has achieved promising results with perfect-information games such as Go. In our work, we apply Monte-Carlo Tree Search to the non-deterministic game "Settlers of Catan", a multi-player board-turned-web-based game that necessitates strategic planning and negotiation skills. We implemented an agent which takes into consideration all the aspects of the game for the first time, using no domain knowledge.
In our work, we are experimenting using a reinforcement learning method Value of Perfect Information(VPI) and two bandit methods, namely, the Upper Coefficient Bound and Bayesian Upper Coefficient Bound methods. Such methods attempt to strike a balance between exploitation and exploration when creating of the search tree.
For first time, we implemented an agent that takes into consideration the complete rules-set of the game and makes it possible to negotiate trading between all players. Furthermore, we included in our agent an alternative initial placement found in the literature, which is based on the analysis of human behavior in Settlers of Catan games.
In our experiments we compare the performance of our methods against each other and against appropriate benchmarks (e.g., JSettlers agents), and examine the effect that the number of simulations and the simulation depth has on the algorithms’ performance. Our results suggests that VPI scores significantly better than bandit based methods, even if these employ a much higher number of simulations. In addition to this, the simulation depth of the algorithm needs to be calculated so the method will neither get lost in deep simulations of improbable scenarios neither end up shortly without given a proper estimation of the upcoming moves. Finally, our results indicate that our agent performance is improved when the alternative, human behavior-based, initial placement method.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 145Π-58
Έναρξη: 03/11/2016 10:00
Λήξη: 03/11/2016 11:00
