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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Δενδρική αναζήτηση Monte Carlo στο παιχνίδι στρατηγικής "Άποικοι του Κατάν"

Karamalegos Emmanouil

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/1CCC4417-B1AA-4C2E-B33B-0F6BEFDED36E-
Αναγνωριστικόhttps://drive.google.com/drive/folders/0B9pKS-Z7bpHxWEotSUxFbGhFUWM-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.66891-
Γλώσσαen-
Μέγεθος1,17 megabytesel
ΤίτλοςMonte Carlo tree search in the "Settlers of Catan" strategy gameen
ΤίτλοςΔενδρική αναζήτηση Monte Carlo στο παιχνίδι στρατηγικής "Άποικοι του Κατάν"el
ΔημιουργόςKaramalegos Emmanouilen
ΔημιουργόςΚαραμαλεγκος Εμμανουηλel
Συντελεστής [Επιβλέπων Καθηγητής]Chalkiadakis Georgiosen
Συντελεστής [Επιβλέπων Καθηγητής]Χαλκιαδακης Γεωργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Lagoudakis Michaelen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Λαγουδακης Μιχαηλel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Deligiannakis Antoniosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Δεληγιαννακης Αντωνιοςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Περίληψη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-turnedweb- 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.en
ΤύποςΔιπλωματική Εργασίαel
ΤύποςDiploma Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2016-11-03-
Ημερομηνία Δημοσίευσης2016-
Θεματική ΚατηγορίαArtificial intelligenceen
Βιβλιογραφική ΑναφοράEmmanouil Karamalegos, "Monte Carlo tree search in the "Settlers of Catan" strategy game", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2016en
Βιβλιογραφική ΑναφοράΕμμανουήλ Καραμαλέγκος, "Δενδρική αναζήτηση Monte Carlo στο παιχνίδι στρατηγικής "Άποικοι του Κατάν"", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2016el

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

Υπηρεσίες

Στατιστικά