Chess position evaluation using neural networks
Αξιολόγηση σκακιστικών θέσεων με χρήση νευρωνικών δικτύων
![Thumbnail](/xmlui/bitstream/handle/11400/954/Kagkas_msciot18001.pdf.jpg?sequence=4&isAllowed=y)
Μεταπτυχιακή διπλωματική εργασία
Συγγραφέας
Κάγκας, Δημήτριος
Ημερομηνία
2021-07-22Επιβλέπων
Alexandridis, AlexΛέξεις-κλειδιά
Chess engine ; Chess position evaluation ; Fuzzy means ; Multilayer perceptron ; Radial basis function ; Neural networks ; Νευρωνικά δίκτυα ; Σκακιστική μηχανήΠερίληψη
The game of chess is the most widely examined game in the field of artificial intelligence and machine learning. There are many approaches where implementations attempt to substitute parts, or the whole functionality of a chess engine. In this Thesis we propose a method for obtaining the evaluation of a chess position without using tree search and examining each candidate move separately, like a chess engine does. Instead of exploring the search tree in order to look several moves ahead, we propose to use the much faster and less computationally demanding predictions of a properly trained neural network. Such an approach offers the benefit of having a prediction for the position evaluation in a matter of milliseconds, while a chess engine may need even minutes to achieve the same result. The proposed approach introduces a novel set of input features, in conjunction with models which are based on the radial basis function (RBF) neural network architecture and trained with the fuzzy means algorithm; two different methods of network training are also examined and compared, involving the multilayer perceptron (MLP) network architecture. All methods were based upon the same dataset which was derived by a collection of over 1500 top-level chess games. A Java application was developed for processing the games and extracting certain features from the arising positions in order to construct the training dataset, which contained data from 81967 positions. Various networks were trained and tested as we considered different variations of each method regarding input variable configurations and dataset filtering. Ultimately, the results indicated that the proposed approach using the RBF method was the best in performance. The models produced with the proposed approach are suitable for integration in model-based decision making frameworks, e.g. model predictive control (MPC) schemes, which could form the basis for a fully fledged chess playing software.
Περίληψη
Το σκάκι αποτελεί το πιο συχνά χρησιμοποιούμενο παιχνίδι στο πεδίο της τεχνητής νοημοσύνης και της μηχανικής μάθησης. Πολλές προσεγγίσεις έχουν προταθεί όπου οι υλοποιήσεις επιχειρούν να αντικαταστήσουν μέρη ή και ολόκληρη τη λειτουργικότητα των σκακιστικών μηχανών. Σε αυτή την εργασία προτείνουμε μία μέθοδο για την εύρεση της αξιολόγησης μιας σκακιστικής θέσης χωρίς να γίνεται χρήση αλγορίθμου αναζήτησης δέντρου και εξέταση κάθε πιθανής κίνησης ξεχωριστά, όπως θα έκανε μια σκακιστική μηχανή. Αντί για την επεξεργασία του δέντρου αναζήτησης ώστε να εξεταστεί η θέση σε βάθος αρκετών κινήσεων, προτείνουμε τη χρήση προβλέψεων ενός κατάλληλα εκπαιδευμένου νευρωνικού δικτύου, που εξασφαλίζει πολύ μεγαλύτερη ταχύτητα και μικρότερες απαιτήσεις σε επεξεργαστική ισχύ. Το βασικό πλεονέκτημα αυτής της προσέγγισης είναι η λήψη πρόβλεψης της αξιολόγησης μιας σκακιστικής θέσης σε χρόνους της τάξης των χιλιοστών του δευτερολέπτου ενώ μια σκακιστική μηχανή θα χρειαζόταν εώς και μερικά λεπτά για να επιτύχει το αντίστοιχο αποτέλεσμα. Η προτεινόμενη προσέγγιση περιλαμβάνει ένα νέο σύνολο χαρακτηριστικών ως μεταβλητές εισόδου, σε συνδυασμό με μοντέλα νευρωνικών δικτύων βασισμένα στην αρχιτεκτονική συνάρτησης ακτινικής βάσης (RBF) τα οποία εκπαιδεύονται με τον αλγόριθμο fuzzy means. Δύο διαφορετικές μέθοδοι εκπαίδευσης νευρωνικών δικτύων επίσης εξετάστηκαν και συγκρίθηκαν, οι οποίες αφορούν την αρχιτεκτονική perceptron πολλαπλών στιβάδων. Όλες οι μέθοδοι βασίστηκαν στο ίδιο σύνολο δεδομένων το οποίο προέκυψε μετά από επεξεργασία περισσότερων από 1500 παρτίδων παικτών κορυφαίου επιπέδου. Για το σκοπό αυτό αναπτύχθηκε μια εφαρμογή σε γλώσσα Java για την εξαγωγή συγκεκριμένων χαρακτηριστικών από την κάθε σκακιστική θέση στις παρτίδες αυτές, ώστε να γίνει η κατασκευή του συνόλου των δεδομένων εκπαίδευσης, το οποίο περιείχε δεδομένα από 81967 θέσεις. Πολλαπλά νευρωνικά δίκτυα εκπαιδεύτηκαν με σκοπό την εξέταση διαφορετικών εκδοχών της κάθε μεθόδου, σχετικά με την επιλογή μεταβλητών εισόδου καθώς και φιλτραρίσματος των δεδομένων. Τα αποτελέσματα της διαδικασίας έδειξαν πως η προσέγγιση με την αρχιτεκτονική RBF ήταν η καλύτερη σε απόδοση. Τα μοντέλα που παράχθηκαν με την προτεινόμενη προσέγγιση είναι κατάλληλα για ενσωμάτωση σε δομές λήψης αποφάσεων που βασίζονται σε μοντέλα, π.χ. σε μεθοδολογίες ‘model predictive control’ (MPC), οι οποίες μπορούν να γίνουν η βάση για την ανάπτυξη ενός ολοκληρωμένου σκακιστικού λογισμικού.