Συντάχθηκε 14-02-2014 14:37
από Eleni Stamataki
Email συντάκτη: estamataki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: σύνταξη/αποχώρηση υπάλληλος.
Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΣΟΦΙΑ-ΜΑΡΙΑ ΝΙΚΟΛΑΚΑΚΗ
με θέμα
«Μοντελοποίηση Αλγορίθμων για Υλοποίηση σε Υλικό για το Παιχνίδι Blokus Duo»
“Algorithm Modeling for Hardware Implementation of a Blokus Duo Player”
Δευτέρα 24 Φεβρουαρίου 2014, 13:00μμ
Αίθουσα 137.Π39, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Καθηγητής Απόστολος Δόλλας (επιβλέπων) (Σχολή ΗΜΜΥ)
Καθηγητής Μίνως Γαροφαλάκης (Σχολή ΗΜΜΥ)
Αναπληρωτής Καθηγητής Ιωάννης Παπαευσταθίου (Σχολή ΗΜΜΥ)
Περίληψη
Ο τομέας της Τεχνητής Νοημοσύνης έχει προκαλέσει αισθητό αντίκτυπο σε ένα ευρύ φάσμα επιστημονικών πεδίων και εφαρμόζεται ιδιαίτερα σε παιχνίδια. Μέχρι πρόσφατα, η κυριαρχία του αλγορίθμου Minimax ήταν αδιαμφισβήτητη σε zero-sum παιχνίδια με δύο παίκτες, καθώς εγγυόταν βέλτιστη λύση αρκεί να έφτανε η αναζήτηση σε συγκεκριμένο βάθος του δέντρου. Ωστόσο, προϋπόθετε την ύπαρξη μίας καλής ευριστικής συνάρτησης και ορισμένες φορές απαγορευτικό χρόνο εκτέλεσης. Αυτό οδήγησε στο σχεδιασμό ενός καινούριου και αρκετά πρόσφατου αλγορίθμου, του Monte Carlo Tree Search (MCTS). Ο MCTS φάνηκε από την αρχή πολλά υποσχόμενος καθώς είχε καλύτερη απόδοση από state-of-the-art αλγορίθμους στο τρέχον πιο δύσκολο zero-sum παιχνίδι δύο παιχτών, το Go. Τα τελευταία επτά χρόνια πολλοί προσπάθησαν να κατανοήσουν και να αξιολογήσουν την απόδοση του MCTS, με την εφαρμογή του σε διαφορετικά παιχνίδια και την συλλογή πειραματικών αποτελεσμάτων. Άλλοι έχουν χρησιμοποιήσει διαφορετικές ευριστικές μεθόδους και τεχνικές για να βελτιώσουν την επίδοση του αλγορίθμου, δημιουργώντας έτσι και νέες παραλλαγές του. Ανάμεσα σε αυτές, η πιο γνωστή είναι ο αλγόριθμος Upper Confidence Bound for Trees (UCT). Το κίνητρο για αυτή τη δουλειά προκλήθηκε από τη δυνατότητα σύγκρισης της επίδοσης του MCTS με άλλους αλγορίθμους, μοντελοποίησης του για υλοποίηση σε υλικό και βελτίωσης του ποσοστού νίκης του. Για το λόγο αυτό, εφαρμόσαμε τον MCTS αλγόριθμο στο παιχνίδι Blokus Duo, ένα σχετικά καινούριο παιχνίδι και ανοιχτό για έρευνα, καθώς ανταποκρίνεται στις απαιτήσεις του MCTS και φαίνεται να είναι αρκετά δύσκολο. Ειδικότερα, παρουσιάζουμε τέσσερις ανταγωνιστικούς Blokus Duo παίκτες και δείχνουμε ότι εκείνοι που βασίζονται σε Monte Carlo προσομοιώσεις αποδίδουν καλύτερα σε σχέση με εκείνον που βασίζεται στον Minimax αλγόριθμο. Σύμφωνα με τα όσα γνωρίζουμε, η συγκεκριμένη δουλειά είναι η πρώτη που συγκρίνει για το ίδιο παιχνίδι παίκτες υλοποιημένους σε λογισμικό, που βασίζονται στους αλγορίθμους Minimax, Monte Carlo και MCTS. Για κάθε έναν από αυτούς τους παίκτες, υποδεικνύουμε δυνατότητες για την υλοποίηση τους σε υλικό και αναφέρουμε πιθανά bottlenecks. Επιπλέον, εφαρμόζουμε συγκεκριμένες ευριστικές μεθόδους στον παίκτη που βασίζεται στον MCTS αλγόριθμο, ώστε να καταλάβουμε πώς επηρεάζουν την απόδοση του αλγορίθμου, ειδικά για το παιχνίδι του Blokus Duo.
Abstract
Artificial Intelligence has a profound impact on a wide range of scientific fields and has been well applied especially in game playing. Until recently, the dominance of the Minimax algorithm in two player zero-sum games was indisputable, since it guaranteed an optimal solution as long as the search reached a certain tree depth. However, it required configuration of a good heuristic function and sometimes a prohibitive amount of execution time. This led to the design of a new and quite recent algorithm, the Monte Carlo Tree Search (MCTS) algorithm. MCTS appeared to be promising from the very beginning since it performed better than state-of-the-art algorithms in the currently most challenging two player zero-sum game, Go. Over the last seven years, many have tried to comprehend and evaluate the MCTS algorithm performance by applying it on different games and by gathering experimental results. Others have used a variety of heuristics and techniques to improve the algorithm's efficiency, thus creating different MCTS variations. Among these, the most popular one is the Upper Confidence Bound for Trees algorithm (UCT). The motivation behind the present work was initiated by the potential for comparing the performance of MCTS with other algorithms, modeling it for hardware implementation and improving its efficiency in terms of winning percentage. Therefore, we applied the MCTS algorithm on the game of Blokus Duo, a relatively new game, open for research since it meets the requirements of MCTS and appears to be demanding. More specifically, we present four competitive Blokus Duo players and show that the ones based on Monte Carlo simulations outperform the Minimax-based one. To the best of our knowledge, this is the first work that compares for the same game, software-based Minimax, Monte Carlo and MCTS players. For each of these players we suggest opportunities for hardware implementation and discuss potential bottlenecks. Furthermore, we apply certain heuristics on our MCTS-based player to understand how they affect the efficiency of the algorithm specifically for the game of Blokus Duo.
