Συντάχθηκε 23-02-2010 23:10
από Michail Lagoudakis
Email συντάκτη: lagoudakis<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: ΔΕΠ ΗΜΜΥ.
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΙΩΑΝΝΗ Ε. ΣΚΟΥΛΑΚΗ
Με θέμα:
“Συστηματική Αναζήτηση και Ενισχυτική Μάθηση
για το Επιτραπέζιο Παιχνίδι Neighbours”
Τετάρτη 24 Φεβρουαρίου 2010, Ώρα 9πμ
Πολυτεχνειούπολη, Αίθουσα 141.Α14-2 (Εργαστήριο Ευφυών Συστημάτων ΗΜΜΥ)
Εξεταστική Επιτροπή
Επ. Καθ. Μιχαήλ Γ. Λαγουδάκης (επιβλέπων)
Επ. Καθ. Αντώνιος Δεληγιαννάκης
Επ. Καθ. Νικόλαος Βλάσσης (Τμήμα Μηχανικών Παραγωγής και Διοίκησης)
Περίληψη
Τα παιχνίδια πάντα αποτελούσαν ένα πολύτιμο τομέα έρευνας και πρακτικής εφαρμογής της Τεχνητής Νοημοσύνης και της Μηχανικής Μάθησης λόγω των νοητικών δεξιοτήτων που απαιτούν. Η παρούσα διπλωματική εργασία επικεντρώνεται σε ένα άγνωστο, αλλά και πολύ απρόβλεπτο, παιχνίδι σκακιέρας, το Neighbours, το οποίο χαρακτηρίζεται από μεγάλο αριθμό επιλογών για κάθε παίκτη σε κάθε κίνηση και από μεγάλο βαθμό εξαρτήσεων μεταξύ των πιονιών πάνω στη σκακιέρα. Στα πλαίσια της εργασίας σχεδιάστηκε και αναπτύχθηκε ένας πράκτορας για το Neighbours, αλλά και ένα γραφικό διαδικτυακό περιβάλλον μέσω του οποίου μπορούν να διεξαχθούν παρτίδες Neighbours με οποιοδήποτε συνδυασμό χρηστών και πρακτόρων. Η στρατηγική του πράκτορά μας για την επιλογή κινήσεων βασίζεται στον αλγόριθμο MiniMax σε συνδυασμό με την τεχνική του κλαδέματος άλφα-βήτα, αλλά και εκείνης του Principal Variation Search (PVS). Το πλήθος των επεκτεινόμενων κόμβων μειώνεται αισθητά με την χρήση ενός Hash Table που χρησιμοποιεί Zobrist Hashing, προσφέροντάς σημαντική βελτίωση σε ταχύτητα. Τέλος, χρησιμοποιώντας μια παραλλαγή του αλγορίθμου ενισχυτικής μάθησης Least-Squares Temporal Difference Learning (LSTD), ο πράκτορας μπορεί να βελτιώνεται ως προς τη συνάρτηση αξιολόγησης καταστάσεων, απλά παίζοντας παρτίδες με τον εαυτό του. Οι τεχνικές βελτιστοποίησης που υλοποιούνται σε συνεργασία με την αποτελεσματική μάθηση δημιουργούν έναν πολύ δυνατό και γρήγορο πράκτορα, ο οποίος μπορεί να εξετάσει κινήσεις μέχρι βάθους 8 σε έναν τυπικό υπολογιστή και πολύ δύσκολα μπορεί να αντιμετωπιστεί από τον άνθρωπο.
