Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Σχεδιασμός και μάθηση σε πραγματικό χρόνο για το παιχνίδι στρατηγικής "Άποικοι του Κατάν"

Panousis Konstantinos

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/47FFB724-C399-400A-9204-0466FD08FCB5-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.18113-
Γλώσσαen-
Μέγεθος128 Σελίδεςel
ΤίτλοςReal-time planning and learning in the "Settlers of Catan" strategy gameen
ΤίτλοςΣχεδιασμός και μάθηση σε πραγματικό χρόνο για το παιχνίδι στρατηγικής "Άποικοι του Κατάν"el
ΔημιουργόςPanousis Konstantinosen
ΔημιουργόςΠανουσης Κωνσταντινος-Παναγιωτηςel
Συντελεστής [Επιβλέπων Καθηγητής]Chalkiadakis Georgiosen
Συντελεστής [Επιβλέπων Καθηγητής]Χαλκιαδακης Γεωργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Lagoudakis Michaelen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Λαγουδακης Μιχαηλel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Deligiannakis Antoniosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Δεληγιαννακης Αντωνιοςel
ΕκδότηςTechnical University of Creteen
ΕκδότηςΠολυτεχνείο Κρήτηςel
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electronic and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστώνel
ΠεριγραφήΔιπλωματική Εργασία που υποβήθηκε στη Σχολή ΗΜΜΥ για την ολοκλήρωση των προϋποθέσεων για τη λήψη του προπτυχιακού τίτλου σπουδών. el
ΠερίληψηΟ αλγόριθμος Monte Carlo Tree Search (MCTS) είναι μια γενική μέθοδος για την λήψη βέλτιστων αποφάσεων. Η μέθοδος αξιοποιεί τη λήψη (ουσιαστικά τυχαίων) δειγμάτων από τις πιθανές ενέργειες, και δημιουργεί ένα δέντρο αποφάσεων, μέσω του οποίου αναζητείται η βέλτιστη απόφαση. Μετά την επιτυχημένη εφαρμογή της μεθόδου, στο παιχνίδι -δύο παικτών και τέλειας πληροφορίας- Go, και τις προσδοκίες που δημιούργησε, η επαρκής κατανόηση των πλεονεκτημάτων και των αδυναμιών του αλγορίθμου είναι ένα ζητούμενο. Στην εργασία αυτή, εφαρμόζουμε τον αλγόριθμο MCTS, στο επιτραπέζιο παιχνίδι στρατηγικής Άποικοι του Κατάν, ένα παιχνίδι πολλών παικτών,μη-ντετερμινιστικό και μερικώς παρατηρήσιμο. Αναπτύσσουμε και αξιολογούμε τρεις διαφορετικές παραλλαγές στο κομμάτι της δημιουργίας του δέντρου του αλγορίθμου: συγκεκριμένα τη μέθοδο UCT, τη μέθοδο Bayesian UCT και τη μέθοδο Value of Perfect Information (VPI). Οι αλγόριθμοι αυτοί κατ'ουσίαν επιχειρούν να ισορροπήσουν το δίλημμα μεταξύ εξερεύνησης (exploration) και εκμετάλλευσης(exploitation) στο συγκεκριμένο τομέα. Επιπρόσθετα, δημιουργήσαμε διάφορες ευριστικές στρατηγικές για να μπορεί ο πράκτορας μας να ανταπεξέλθει σε συγκεκριμένες καταστάσεις που μπορούν να εμφανιστούν και οι οποίες απορρέουν από τους κανόνες του παιχνιδιού· σε αντίθεση με τους περισσότερους αυτοματοποιημένους παίκτες για τους Αποίκους του Κατάν, η υλοποίηση μας προσφέρει ένα (έστω απλό) σχέδιο διαπραγμάτευσης για να έχει ο πράκτορας μας τη δυνατότητα να ανταλλάσει πόρους με άλλους παίκτες. Αξίζει να σημειωθεί ότι είναι η πρώτη φορά που η μέθοδος Bayesian UCT χρησιμοποιείται στον αλγόριθμο MCTS στο παιχνίδι Άποικοι του Κατάν και είναι επίσης η πρώτη φορά που η μέθοδος VPI χρησιμοποείται σε σύζευξη με τον αλγόριθμο MCTS γενικότερα. Δοκιμάζουμε και αξιολογούμε τους πρακτόρες μας με βάση την αποτελεσματικότητα τους σε μεταξύ τους αναμετρήσεις, αλλά και σε αναμετρήσεις τους ενάντια σε υπαρκτές υλοποιήσεις άλλων αυτόνομων πρακτόρων, συμπεριλαμβανομένης και της ισχυρότερης υπάρχουσας ευρετικής υλοποίησης αυτόνομου πράκτορα. Τα αποτελέσματα μας είναι ενθαρρυντικά, και υποδηλώνουν ότι ο αλγόριθμος MCTS μπορεί να επωφεληθεί από τις παραλλαγές που υλοποιήσαμε. Ειδικά ο πράκτορας που χρησιμοποιεί την μέθοδο VPI, εμφανίζεται να είναι αρκετά ανταγωνιστικός, και η απόδοση του μπορεί να συγκριθεί με την απόδοση άλλων υπαρκτών αυτόνομων παικτών του παιχνιδιού Άποικοι του Κατάν, παρόλο που οι υπολογιστικοί πόροι που αξιοποιεί ήταν ιδιαίτερα περιορισμένοι σε σχέση με αυτούς που αξιοποιούν οι αντίπαλοι του. el
ΠερίληψηMonte Carlo Tree Search (MCTS) is a generic method for optimal decision making in a given domain. The technique operates by searching a decision tree that is progressively built via the -essentially random- sampling of potential action sequences. After its successful application in the two-player, perfect information game of Go, researchers are trying to obtain a better understanding of the MCTS strengths and weaknesses. In this thesis, we apply MCTS in the Settlers of Catan (SoC) strategy game, which is a non-deterministic, partially observable, multi-player strategic board game. We develop and evaluate three different enhancements in the tree policy of the main MCTS algorithm: namely, UCT, Bayesian UCT and Value of Perfect Information (VPI). These refined methods essentially constitute attempts to balance the exploration-exploitation dilemma in this domain. In addition, we created various heuristic strategies to cope with specific situations that may arise in the game; and, unlike most SoC automated players, our implementation also provides a simple negotiation scheme that gives our agent the ability to trade with other players. We note that this is possibly the first time that the MCTS algorithm is employed within a highly complex multi-agent environment. Moreover, this is the first time that the Bayesian UCT MCTS variant is used in the Settlers of Catan domain, and the first time that VPI is employed in conjunction with MCTS in general. We pit our agents against each other, and against existing AI implementations, including the strongest existing heuristic-based SoC automated player. Our results are very encouraging, and suggest that MCTS can benefit from the various tree policy enhancements implemented. The VPI agent, in particular, appears to be quite competitive, achieving performance that is comparable to that of existing SoC AI players, even when operating within a computational budget that was actually significantly more restricted than theirs. en
ΤύποςΔιπλωματική Εργασίαel
ΤύποςDiploma Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by-nc/4.0/en
Ημερομηνία2014-06-20-
Ημερομηνία Δημοσίευσης2014-
Θεματική ΚατηγορίαMulti-Agent Learningen
Θεματική ΚατηγορίαLearningen
Θεματική ΚατηγορίαMonte Carlo Tree Searchen
Θεματική ΚατηγορίαAI (Artificial intelligence)en
Θεματική ΚατηγορίαArtificial thinkingen
Θεματική ΚατηγορίαElectronic brainsen
Θεματική ΚατηγορίαIntellectronicsen
Θεματική ΚατηγορίαIntelligence, Artificialen
Θεματική ΚατηγορίαIntelligent machinesen
Θεματική ΚατηγορίαMachine intelligenceen
Θεματική ΚατηγορίαThinking, Artificialen
Θεματική Κατηγορίαartificial intelligenceen
Θεματική Κατηγορίαai artificial intelligenceen
Θεματική Κατηγορίαartificial thinkingen
Θεματική Κατηγορίαelectronic brainsen
Θεματική Κατηγορίαintellectronicsen
Θεματική Κατηγορίαintelligence artificialen
Θεματική Κατηγορίαintelligent machinesen
Θεματική Κατηγορίαmachine intelligenceen
Θεματική Κατηγορίαthinking artificialen
Βιβλιογραφική ΑναφοράKonstantinos Panousis, "Real-time planning and learning in the "Settlers of Catan" strategy game", Diploma Work, School of Electronic and Computer Engineering, Technical University of Crete, Chania, Greece, 2014en
Βιβλιογραφική ΑναφοράΚωνσταντίνος-Παναγιώτης Πανούσης, "Σχεδιασμός και μάθηση σε πραγματικό χρόνο για το παιχνίδι στρατηγικής "Άποικοι του Κατάν"", Διπλωματική Εργασία, Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2014el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά