Κατάλογος Εκδηλώσεων

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

Διαμαντή - Ραφαήλ Παπαδάμ

με θέμα

Μηχανική Μάθηση στο Στρατηγικό Παίγνιο “Άποικοι του Κατάν”
Machine Learning in the “Settlers of Catan” Strategic Board Game

Εξεταστική Επιτροπή

Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Καθηγητής Μιχαήλ Λαγουδάκης
Καθηγητής Θρασύβουλος Σπυρόπουλος

Περίληψη

Παρά το γεγονός ότι προσφάτως μια σειρά από αλγορίθμους στηριζόμενους στη χρήση βαθέων νευρωνικών δικτύων έχουν κατορθώσει να πετύχουν επιδόσεις ανώτερες των ανθρωπίνων σε πολλά στρατηγικά παίγνια, όπως το Σκάκι ή το Go, δεν υπάρχει ακόμη κάποιος αλγόριθμος που να νικάει επαγγελματίες ανθρώπους στο πολυπρακτορικό στρατηγικό παίγνιο ”΄Αποικοι του Κατάν”. Στην παρούσα διπλωματική, παρουσιάζουμε έναν συνδυασμό σύγχρονης μηχανικής μάθησης με κλασικές μεθόδους δενδρικής αναζήτησης υπό αντιπαλότητα και πετυχαίνουμε απόδοση λίγο χαμηλότερη από την καλύτερη που υπάρχει στην βιβλιογραφία. Συγκεκριμένα, χρησιμοποιούμε μία γενίκευση του κλασικού αλγορίθμου Minimax, με την επονομασία Maxn , όπου η συνάρτηση αξιολόγησης που εφαρμόζεται στα φύλλα του δένδρου είναι ένα εκπαιδευμένο συνελικτικό νευρωνικό δίκτυο. Η εργασία μας αποτελείται από δύο μέρη τα οποία δύνανται να λειτουργήσουν αυτόνομα. Το πρώτο μέρος είναι η υλοποίηση του αλγορίθμου Maxn , ο οποίος μπορεί να χρησιμοποιήσει οποιαδήποτε συνάρτηση αξιολόγησης ορίσουμε. Το δεύτερο μέρος είναι το νευρωνικό δίκτυο, το οποίο δρα ως συνάρτηση αξιολόγησης και θα μπορούσε να ενσωματωθεί σε οποιονδήποτε αλγόριθμο αναζήτησης υπό αντιπαλότητα για να προσφέρει την πληροφορία της αξιολόγησης τερματικών καταστάσεων. ΄Επειτα από 10000 προσομοιωμένα παιχνίδια, που αποτελούν ένα ικανό πλήθος για την εξαγωγή εμπειρικών αποτελεσμάτων στο στρατηγικό παίγνιο ”΄Αποικοι του Κατάν”, πετυχαίνουμε επίδοση κοντά στην καλύτερη που υπάρχει στην βιβλιογραφία, με το πλεονέκτημα ότι σε αντίθεση με τη μέθοδο που πετυχαίνει αυτήν την επίδοση, εμείς δεν κάνουμε χρήση συλλογής δεδομένων που παράχθηκαν από παιχνίδια μεταξύ ανθρώπων.

Abstract 

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-theart in initial settlement placement. In particular, we use a generalization of the classic Minimax search algorithm, known as Maxn , 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 Maxn 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 does not make use of a human-generated corpus of data.