Συντάχθηκε 22-11-2016 12:51
από Esthir Gelasaki
Email συντάκτη: egelasaki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΣΩΤΗΡΙΟΥ Σ. ΒΑΓΕΝΑ
με θέμα
Συστηματική Αναζήτηση και Ενισχυτική Μάθηση
για το Επιτραπέζιο Παιχνίδι ‘‘Turning Points’’
Systematic Search and Reinforcement Learning
for the Board Game “Turning Points”
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Μιχαήλ Γ. Λαγουδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης
Αναπληρωτής Καθηγητής Αντώνιος Δεληγιαννάκης
Περίληψη
Τα παιχνίδια ήταν ανέκαθεν ένα από τα κυριότερα μέσα ψυχαγωγίας για τους ανθρώπους. Συνδυάζουν τη διασκέδαση, την πνευματική ανάπτυξη και την ανάπτυξη υψηλών δεξιοτήτων. Για τους λόγους αυτούς, τα παιχνίδια αποτελούν έναν από τους σημαντικότερους τομείς έρευνας και εφαρμογής της Τεχνητής Νοημοσύνης και της Μηχανικής Μάθησης. Η παρούσα διπλωματική εργασία εστιάζει στο επιτραπέζιο παιχνίδι “Turning Points”. Πρόκειται για ένα περίπλοκο παιχνίδι τετραγωνικού board 4 x 4 δύο παικτών, στο οποίο κάθε κίνηση αντιστοιχεί στην τοποθέτηση ενός κατευθυνόμενου βέλους σε μία άδεια θέση, πιθανότατα προκαλώντας περιστροφές στα υπάρχοντα βέλη. Στόχος της εργασίας είναι η σχεδίαση ενός πράκτορα για το παιχνίδι Turning Points, ο οποίος θα μαθαίνει να παίζει και θα βελτιώνεται ενάντια σε διάφορους αντιπάλους. Η υλοποίηση του πράκτορα συνδυάζει την τεχνική αναζήτησης Minimax με α-β Pruning, μία συνάρτηση αξιολόγησης και τον αλγόριθμο ενισχυτικής μάθησης TD-Learning. Ο συνδυασμός των παραπάνω στοιχείων οδηγεί στην εξαγωγή πολλών αποδοτικών παικτών, όπως προκύπτει από τη πειραματική διαδικασία αξιολόγησης. Οι παίκτες αυτοί αντιμετωπίζουν τον άνθρωπο με πολύ μεγάλη αποτελεσματικότητα. Ενδιαφέρον, επίσης, παρουσιάζει το γεγονός ότι παραμένουν ανταγωνιστικοί σε boards μεγαλύτερων διαστάσεων από το βασικό στο οποίο έχουν εκπαιδευτεί. Τέλος, υλοποιήθηκε κατάλληλη γραφική διεπαφή για τη διεξαγωγή παιχνιδιών με χρήστες.
Abstract
Games have always been one of the main forms of entertainment for people. They combine fun, spiritual growth and skill development. For these reasons, games constitute one of the most important areas of research and application of Artificial Intelligence and Machine Learning. This thesis focuses on the board game “Turning Points”. This is a challenging two-player 4 x 4 square board game, in which each move corresponds to the placement of a directed arrow to an empty position, possibly causing some rotations of the existing arrows. The goal of the thesis is the design of an agent for the game Turning Points, who will learn to play and improve against various opponents. The implementation of the agent combines the Minimax with alpha-beta Pruning search technique, an evaluation function and the reinforcement learning algorithm TD-Learning. The combination of these elements results in the extraction of several competitive players, as evidenced by the experimental evaluation procedure. These players faced human players competitively and efficiently. Interestingly, they also remain competitive in larger boards compared to the basic one in which they have been trained. Finally, a graphical user interface was implemented to enable game playing with users.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 137Π-39,-38
Έναρξη: 25/11/2016 13:00
Λήξη: 25/11/2016 14:00
