Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/40CF0910-13EF-4D6F-8165-3F2BEDC938C6 | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.99217 | - |
| Γλώσσα | en | - |
| Μέγεθος | 10.3 megabytes | en |
| Μέγεθος | 92 pages | en |
| Τίτλος | Machine learning in the “Settlers of Catan” strategic board game | en |
| Τίτλος | Μηχανική μάθηση στο στρατηγικό παίγνιο «΄Αποικοι του Κατάν» | el |
| Δημιουργός | Papadam Diamantis-Rafail | en |
| Δημιουργός | Παπαδαμ Διαμαντης-Ραφαηλ | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Chalkiadakis Georgios | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Χαλκιαδακης Γεωργιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Spyropoulos Thrasyvoulos | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Σπυροπουλος Θρασυβουλος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Lagoudakis Michail | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Λαγουδακης Μιχαηλ | el |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Εκδότης | Technical University of Crete | en |
| Ακαδημαϊκή Μονάδα | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περίληψη | Despite recent deep neural network superhuman performance in many strategic board games, such as Chess and Go, there does not yet exist an algorithm that beats “Settlers of Catan” professional human players. Towards this direction, we present a combination of modern machine learning with traditional tree-based adversarial search algorithms and achieve performance close to the state-of-the-art in initial settlement placement. In particular, we use a generalization of the classic Minimax search algorithm, known as Max^n , with the novelty that the evaluation function at the leaf nodes is the result of a forward pass in a trained convolutional neural network. Our work consists of two distinct parts that can work independently. The first is the Max^n algorithm implementation that could use any evaluation function. The second is the neural network, which acts as an evaluation function and could be plugged into any adversarial search algorithm. After 10000 simulated games, which is a sufficient number for the demanding strategic board game “Settler of Catan”, we achieve performance close to the state-of-the-art; with the advantage that, in contrast to the state-of-the-art one, our approach’s runtime is acceptable by human players. | en |
| Περίληψη | Παρά το γεγονός ότι προσφάτως πολλοί αλγόριθμοι στηριζόμενοι στη χρήση βαθέων νευρωνικών δικτύων έχουν κατορθώσει να πετύχουν επιδόσεις ανώτερες των ανθρωπίνων σε πολλά στρατηγικά παίγνια, όπως το Σκάκι ή το Go, δεν υπάρχει ακόμη κάποιος αλγόριθμος που να νικάει επαγγελματίες ανθρώπους στο πολυπρακτορικό στρατηγικό παίγνιο «΄Αποικοι του Κατάν». Στην παρούσα διπλωματική εργασία, παρουσιάζουμε έναν συνδυασμό σύγχρονης μηχανικής μάθησης με κλασικές μεθόδους δενδρικής αναζήτησης υπό αντιπαλότητα και πετυχαίνουμε απόδοση λίγο χαμηλότερη από την καλύτερη που υπάρχει στην βιβλιογραφία. Συγκεκριμένα, χρησιμοποιούμε μία γενίκευση του κλασικού αλγορίθμου Minimax, με την επονομασία Max^n , όπου η συνάρτηση αξιολόγησης που εφαρμόζεται στα φύλλα του δένδρου είναι ένα εκπαιδευμένο συνελικτικό νευρωνικό δίκτυο. Η εργασία μας αποτελείται από δύο μέρη, τα οποία δύνανται να λειτουργήσουν ανεξάρτητα το ένα από το άλλο. Το πρώτο μέρος είναι η υλοποίηση του αλγορίθμου Max^n, ο οποίος μπορεί να χρησιμοποιήσει οποιαδήποτε συνάρτηση αξιολόγησης ορίσουμε. Το δεύτερο μέρος είναι το νευρωνικό δίκτυο, το οποίο δρα ως συνάρτηση αξιολόγησης και θα μπορούσε να ενσωματωθεί σε οποιονδήποτε αλγόριθμο αναζήτησης υπό αντιπαλότητα για να προσφέρει την πληροφορία της αξιολόγησης τερματικών καταστάσεων. ΄Επειτα από 10000 προσομοιωμένα παιχνίδια, που αποτελούν ένα ικανό πλήθος για την εξαγωγή εμπειρικών αποτελεσμάτων στο στρατηγικό παίγνιο «΄Αποικοι του Κατάν», πετυχαίνουμε επίδοση κοντά στην καλύτερη που υπάρχει στην βιβλιογραφία, με το πλεονέκτημα ότι σε αντίθεση με τη μέθοδο που πετυχαίνει αυτήν την επίδοση, η δική μας μέθοδος έχει χρόνο εκτέλεσης που είναι αποδεκτός από ανθρώπους. | el |
| Τύπος | Διπλωματική Εργασία | el |
| Τύπος | Diploma Work | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2024-03-19 | - |
| Ημερομηνία Δημοσίευσης | 2024 | - |
| Θεματική Κατηγορία | Supervised learning | en |
| Θεματική Κατηγορία | Strategy | en |
| Θεματική Κατηγορία | Strategic board games | en |
| Θεματική Κατηγορία | Settlers of Catan | en |
| Θεματική Κατηγορία | Neural networks | en |
| Θεματική Κατηγορία | Multiplayer | en |
| Θεματική Κατηγορία | Minimax | en |
| Θεματική Κατηγορία | Max^n | en |
| Θεματική Κατηγορία | Maxn | en |
| Θεματική Κατηγορία | Machine Learning | en |
| Θεματική Κατηγορία | Convolutional neural network | en |
| Θεματική Κατηγορία | CNN | en |
| Θεματική Κατηγορία | Catan | en |
| Θεματική Κατηγορία | Adversarial search | en |
| Βιβλιογραφική Αναφορά | Diamantis-Rafail Papadam, "Machine learning in the “Settlers of Catan” strategic board game", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2024 | en |
| Βιβλιογραφική Αναφορά | Διαμαντής-Ραφαήλ Παπαδάμ, "Μηχανική μάθηση στο στρατηγικό παίγνιο «΄Αποικοι του Κατάν»", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2024 | el |
Copyright © DIAS 2013
