Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/40CF0910-13EF-4D6F-8165-3F2BEDC938C6 | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.99217 | - |
| Language | en | - |
| Extent | 10.3 megabytes | en |
| Extent | 92 pages | en |
| Title | Machine learning in the “Settlers of Catan” strategic board game | en |
| Title | Μηχανική μάθηση στο στρατηγικό παίγνιο «΄Αποικοι του Κατάν» | el |
| Creator | Papadam Diamantis-Rafail | en |
| Creator | Παπαδαμ Διαμαντης-Ραφαηλ | el |
| Contributor [Thesis Supervisor] | Chalkiadakis Georgios | en |
| Contributor [Thesis Supervisor] | Χαλκιαδακης Γεωργιος | el |
| Contributor [Committee Member] | Spyropoulos Thrasyvoulos | en |
| Contributor [Committee Member] | Σπυροπουλος Θρασυβουλος | el |
| Contributor [Committee Member] | Lagoudakis Michail | en |
| Contributor [Committee Member] | Λαγουδακης Μιχαηλ | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content Summary | 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 |
| Content Summary | Παρά το γεγονός ότι προσφάτως πολλοί αλγόριθμοι στηριζόμενοι στη χρήση βαθέων νευρωνικών δικτύων έχουν κατορθώσει να πετύχουν επιδόσεις ανώτερες των ανθρωπίνων σε πολλά στρατηγικά παίγνια, όπως το Σκάκι ή το Go, δεν υπάρχει ακόμη κάποιος αλγόριθμος που να νικάει επαγγελματίες ανθρώπους στο πολυπρακτορικό στρατηγικό παίγνιο «΄Αποικοι του Κατάν». Στην παρούσα διπλωματική εργασία, παρουσιάζουμε έναν συνδυασμό σύγχρονης μηχανικής μάθησης με κλασικές μεθόδους δενδρικής αναζήτησης υπό αντιπαλότητα και πετυχαίνουμε απόδοση λίγο χαμηλότερη από την καλύτερη που υπάρχει στην βιβλιογραφία. Συγκεκριμένα, χρησιμοποιούμε μία γενίκευση του κλασικού αλγορίθμου Minimax, με την επονομασία Max^n , όπου η συνάρτηση αξιολόγησης που εφαρμόζεται στα φύλλα του δένδρου είναι ένα εκπαιδευμένο συνελικτικό νευρωνικό δίκτυο. Η εργασία μας αποτελείται από δύο μέρη, τα οποία δύνανται να λειτουργήσουν ανεξάρτητα το ένα από το άλλο. Το πρώτο μέρος είναι η υλοποίηση του αλγορίθμου Max^n, ο οποίος μπορεί να χρησιμοποιήσει οποιαδήποτε συνάρτηση αξιολόγησης ορίσουμε. Το δεύτερο μέρος είναι το νευρωνικό δίκτυο, το οποίο δρα ως συνάρτηση αξιολόγησης και θα μπορούσε να ενσωματωθεί σε οποιονδήποτε αλγόριθμο αναζήτησης υπό αντιπαλότητα για να προσφέρει την πληροφορία της αξιολόγησης τερματικών καταστάσεων. ΄Επειτα από 10000 προσομοιωμένα παιχνίδια, που αποτελούν ένα ικανό πλήθος για την εξαγωγή εμπειρικών αποτελεσμάτων στο στρατηγικό παίγνιο «΄Αποικοι του Κατάν», πετυχαίνουμε επίδοση κοντά στην καλύτερη που υπάρχει στην βιβλιογραφία, με το πλεονέκτημα ότι σε αντίθεση με τη μέθοδο που πετυχαίνει αυτήν την επίδοση, η δική μας μέθοδος έχει χρόνο εκτέλεσης που είναι αποδεκτός από ανθρώπους. | el |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2024-03-19 | - |
| Date of Publication | 2024 | - |
| Subject | Supervised learning | en |
| Subject | Strategy | en |
| Subject | Strategic board games | en |
| Subject | Settlers of Catan | en |
| Subject | Neural networks | en |
| Subject | Multiplayer | en |
| Subject | Minimax | en |
| Subject | Max^n | en |
| Subject | Maxn | en |
| Subject | Machine Learning | en |
| Subject | Convolutional neural network | en |
| Subject | CNN | en |
| Subject | Catan | en |
| Subject | Adversarial search | en |
| Bibliographic Citation | 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 |
| Bibliographic Citation | Διαμαντής-Ραφαήλ Παπαδάμ, "Μηχανική μάθηση στο στρατηγικό παίγνιο «΄Αποικοι του Κατάν»", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2024 | el |
Copyright © DIAS 2013
