Εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι Στρατέγκο
Η συγκεκριμένη διπλωματική εργασία εξετάζει την χρήση μεθόδων μηχανικής μάθησης στο επιτραπέζιο στρατέγκο. Η μηχανική μάθηση κυριαρχεί στον τομέα της τεχνητής νοημοσύνης τα τελευταία χρονιά. Μέθοδοι ενισχυτικής αλλά και επιβλεπόμενης μάθησης έχουν πέτυχει υπεράνθρωπη απόδοση σε πολλά διαφορετικά παι...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2021
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/15265 |
| id |
nemertes-10889-15265 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Μηχανική μάθηση Ενισχυτική μάθηση Στρατέγκο Επιβλεπόμενη μάθηση Reinforcement learning Suppervised learning Deep learning Stratego |
| spellingShingle |
Μηχανική μάθηση Ενισχυτική μάθηση Στρατέγκο Επιβλεπόμενη μάθηση Reinforcement learning Suppervised learning Deep learning Stratego Παπασταμούλης, Γεώργιος Εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι Στρατέγκο |
| description |
Η συγκεκριμένη διπλωματική εργασία εξετάζει την χρήση μεθόδων μηχανικής μάθησης στο επιτραπέζιο στρατέγκο. Η μηχανική μάθηση κυριαρχεί στον τομέα της τεχνητής νοημοσύνης τα τελευταία χρονιά. Μέθοδοι ενισχυτικής αλλά και επιβλεπόμενης μάθησης έχουν πέτυχει υπεράνθρωπη απόδοση σε πολλά διαφορετικά παιχνίδια αλλά και άλλες εφαρμογές. Σε περιβάλλοντα περιορισμένης πληροφορίας όπως το στρατέγκο η χρήση μεθόδων μηχανικής μάθησης είναι σημαντικά πιο περιορισμένη καθώς παρουσιάζουν ιδιαίτερους περιορισμούς που δεν είναι παρόντες στις περισσότερες εφαρμογές.
Αρχικά γίνεται μια περιγραφή της συμβατικής στρατηγικής στο στρατέγκο και των ιδιαιτεροτήτων που παρουσιάζει σε σχέση με αλλά παιχνίδια στρατηγικής. Παρουσιάζεται επίσης μια ανάλυση της πολυπλοκότητας του δέντρου παιχνιδιού και της αρχικής κατάστασης και μια σύγκριση με αλλά δημοφιλή παιχνίδια στρατηγικής.
Στη συνέχεια πραγματοποιείται μια σύντομη ανάλυση της πιο πρόσφατης σχετικής ερευνάς σχετικά με την ανάπτυξη προγραμμάτων στρατηγικής στο στρατέγκο. Ιδιαίτερη αναφορά γίνεται σε μεθόδους αναζήτησης που μπορούν να χρησιμοποιηθούν σε παιχνίδια περιορισμένης πληροφορίας οι οποίες έχουν εφαρμοστεί και στο στρατέγκο με σχετική επιτυχία.
Έπειτα παρουσιάζεται η θεωρητική ανάλυση σχετικά με τη βέλτιστη πολιτική σε περιβάλλοντα περιορισμένης πληροφορίας, δηλαδή την εύρεση μιας πολιτικής η οποία ανήκει σε ένα σημείο ισορροπίας Nash, οπού κανένας παίκτης δεν θα επέλεγε να αποκλίνει από την επιλεγμένη στρατηγική.
Για την εφαρμογή επιβλεπόμενης μάθησης στο στρατέγκο, η είσοδος του δικτύου πρέπει να κατασκευαστεί με τέτοιο τρόπο ώστε να διατηρηθούν όλες οι σημαντικές πληροφορίες για την οπτική του παίκτη για το παιχνίδι. Αρχικά περιγράφεται η ιδιαίτερη πολυπλοκότητα της κατάστασης του ταμπλό στο στρατέγκο και στην συνέχεια προτείνεται μια μέθοδος αναπαράστασης της κατάστασης κατάλληλη για μηχανική μάθηση. Η έξοδος του δικτύου διαμορφώνεται ώστε να αντιπροσωπεύει όλες τις πιθανές κινήσεις του παίκτη σε μια κατάσταση του παιχνιδιού.
Ένα συνελικτικό νευρωνικό δίκτυο και ένα δίκτυο Residual αρχιτεκτονικής εκπαιδευτήκαν σε καταστάσεις παιχνιδιών προερχόμενες από παιχνίδια μεταξύ ανθρώπων. Οι αρχιτεκτονικές που επιλέχτηκαν περιγράφονται αναλυτικά όπως και η διαδικασία της εκπαίδευσης. Η απόδοση της πολιτικής καθοδηγουμένης από τα νευρωνικά δίκτυα εξετάστηκε σε παιχνίδια εναντίον βασικών μεθόδων βασισμένων σε αναζήτηση και νευρωνικά δίκτυα εκπαιδευμένα σε διαφορετικά δεδομένα.
Η εφαρμογή μεθόδων ενισχυτικής μάθησης σε παιχνίδια περιορισμένης πληροφορίας δεν είναι διαδεδομένη και περιορίζεται συνήθως σε εφαρμογές με μικρή πολυπλοκότητα. Αρχικά γίνεται μια σύντομη ανάλυση των μαρκοβιανών διαδικασιών αποφάσεων που χρησιμοποιούνται για την μοντελοποίηση του περιβάλλοντος και της βασικής θεωρίας της ενισχυτικής μάθησης. Στην συνέχεια παρουσιάζεται η μέθοδος Neural Fictitious Self-Play η οποία συγκλίνει σε ισορροπία Nash σε παιχνίδια περιορισμένης πληροφορίας μηδενικού αθροίσματος δυο παικτών και η χρήση της εξετάζεται για την περίπτωση του στρατέγκο. Τα αποτελέσματα της μεθόδου αξιολογούνται σε σχέση με την πολιτική που προέκυψε μέσω επιβλεπομένης μάθησης και τις μεθόδους βασισμένες σε αναζήτηση που χρησιμοποιήθηκαν και προηγουμένως. |
| author2 |
Papastamoulis, Georgios |
| author_facet |
Papastamoulis, Georgios Παπασταμούλης, Γεώργιος |
| author |
Παπασταμούλης, Γεώργιος |
| author_sort |
Παπασταμούλης, Γεώργιος |
| title |
Εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι Στρατέγκο |
| title_short |
Εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι Στρατέγκο |
| title_full |
Εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι Στρατέγκο |
| title_fullStr |
Εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι Στρατέγκο |
| title_full_unstemmed |
Εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι Στρατέγκο |
| title_sort |
εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι στρατέγκο |
| publishDate |
2021 |
| url |
http://hdl.handle.net/10889/15265 |
| work_keys_str_mv |
AT papastamoulēsgeōrgios epharmogēmethodōnepiblepomenēskaienischytikēsmathēsēsstopaichnidistratenko AT papastamoulēsgeōrgios applicationofsupervisedandreinforcementlearningmethodsinthegamestratego |
| _version_ |
1771297345026129920 |
| spelling |
nemertes-10889-152652022-09-05T20:15:17Z Εφαρμογή μεθόδων επιβλεπόμενης και ενισχυτικής μάθησης στο παιχνίδι Στρατέγκο Application of supervised and reinforcement learning methods in the game Stratego Παπασταμούλης, Γεώργιος Papastamoulis, Georgios Μηχανική μάθηση Ενισχυτική μάθηση Στρατέγκο Επιβλεπόμενη μάθηση Reinforcement learning Suppervised learning Deep learning Stratego Η συγκεκριμένη διπλωματική εργασία εξετάζει την χρήση μεθόδων μηχανικής μάθησης στο επιτραπέζιο στρατέγκο. Η μηχανική μάθηση κυριαρχεί στον τομέα της τεχνητής νοημοσύνης τα τελευταία χρονιά. Μέθοδοι ενισχυτικής αλλά και επιβλεπόμενης μάθησης έχουν πέτυχει υπεράνθρωπη απόδοση σε πολλά διαφορετικά παιχνίδια αλλά και άλλες εφαρμογές. Σε περιβάλλοντα περιορισμένης πληροφορίας όπως το στρατέγκο η χρήση μεθόδων μηχανικής μάθησης είναι σημαντικά πιο περιορισμένη καθώς παρουσιάζουν ιδιαίτερους περιορισμούς που δεν είναι παρόντες στις περισσότερες εφαρμογές. Αρχικά γίνεται μια περιγραφή της συμβατικής στρατηγικής στο στρατέγκο και των ιδιαιτεροτήτων που παρουσιάζει σε σχέση με αλλά παιχνίδια στρατηγικής. Παρουσιάζεται επίσης μια ανάλυση της πολυπλοκότητας του δέντρου παιχνιδιού και της αρχικής κατάστασης και μια σύγκριση με αλλά δημοφιλή παιχνίδια στρατηγικής. Στη συνέχεια πραγματοποιείται μια σύντομη ανάλυση της πιο πρόσφατης σχετικής ερευνάς σχετικά με την ανάπτυξη προγραμμάτων στρατηγικής στο στρατέγκο. Ιδιαίτερη αναφορά γίνεται σε μεθόδους αναζήτησης που μπορούν να χρησιμοποιηθούν σε παιχνίδια περιορισμένης πληροφορίας οι οποίες έχουν εφαρμοστεί και στο στρατέγκο με σχετική επιτυχία. Έπειτα παρουσιάζεται η θεωρητική ανάλυση σχετικά με τη βέλτιστη πολιτική σε περιβάλλοντα περιορισμένης πληροφορίας, δηλαδή την εύρεση μιας πολιτικής η οποία ανήκει σε ένα σημείο ισορροπίας Nash, οπού κανένας παίκτης δεν θα επέλεγε να αποκλίνει από την επιλεγμένη στρατηγική. Για την εφαρμογή επιβλεπόμενης μάθησης στο στρατέγκο, η είσοδος του δικτύου πρέπει να κατασκευαστεί με τέτοιο τρόπο ώστε να διατηρηθούν όλες οι σημαντικές πληροφορίες για την οπτική του παίκτη για το παιχνίδι. Αρχικά περιγράφεται η ιδιαίτερη πολυπλοκότητα της κατάστασης του ταμπλό στο στρατέγκο και στην συνέχεια προτείνεται μια μέθοδος αναπαράστασης της κατάστασης κατάλληλη για μηχανική μάθηση. Η έξοδος του δικτύου διαμορφώνεται ώστε να αντιπροσωπεύει όλες τις πιθανές κινήσεις του παίκτη σε μια κατάσταση του παιχνιδιού. Ένα συνελικτικό νευρωνικό δίκτυο και ένα δίκτυο Residual αρχιτεκτονικής εκπαιδευτήκαν σε καταστάσεις παιχνιδιών προερχόμενες από παιχνίδια μεταξύ ανθρώπων. Οι αρχιτεκτονικές που επιλέχτηκαν περιγράφονται αναλυτικά όπως και η διαδικασία της εκπαίδευσης. Η απόδοση της πολιτικής καθοδηγουμένης από τα νευρωνικά δίκτυα εξετάστηκε σε παιχνίδια εναντίον βασικών μεθόδων βασισμένων σε αναζήτηση και νευρωνικά δίκτυα εκπαιδευμένα σε διαφορετικά δεδομένα. Η εφαρμογή μεθόδων ενισχυτικής μάθησης σε παιχνίδια περιορισμένης πληροφορίας δεν είναι διαδεδομένη και περιορίζεται συνήθως σε εφαρμογές με μικρή πολυπλοκότητα. Αρχικά γίνεται μια σύντομη ανάλυση των μαρκοβιανών διαδικασιών αποφάσεων που χρησιμοποιούνται για την μοντελοποίηση του περιβάλλοντος και της βασικής θεωρίας της ενισχυτικής μάθησης. Στην συνέχεια παρουσιάζεται η μέθοδος Neural Fictitious Self-Play η οποία συγκλίνει σε ισορροπία Nash σε παιχνίδια περιορισμένης πληροφορίας μηδενικού αθροίσματος δυο παικτών και η χρήση της εξετάζεται για την περίπτωση του στρατέγκο. Τα αποτελέσματα της μεθόδου αξιολογούνται σε σχέση με την πολιτική που προέκυψε μέσω επιβλεπομένης μάθησης και τις μεθόδους βασισμένες σε αναζήτηση που χρησιμοποιήθηκαν και προηγουμένως. This diploma thesis examines the effectiveness of machine learning techniques in the game of Stratego. Deep learning dominates the field of artificial intelligence in recent years. Supervised and reinforcement learning methods have achieved superhuman performance in a variety of games and other tasks. In incomplete information environments the use of machine learning techniques as they pose unique challenges not present in most other tasks. Firstly, the conventional strategy in Stratego is described and some of its particular elements along with an analysis of the complexity of the game tree and starting position comparatively to other popular strategy games. Next, a brief analysis of related research, concerning the development of AI in Stratego, is presented. Special reference is made to search methods that can be used in incomplete information games and have been applied to Stratego with relative success. Next is the theoretical analysis of the optimal policy in incomplete information environments, i.e. finding a policy that belongs to a Nash equilibrium, where no player would choose to deviate from the chosen strategy. For the application of supervised learning techniques to stratego the network input must be constructed in such a way that all the relevant information of the player’s view of the board is retained. The particular complexity of the stratego board is then described and such a representation method, suitable for machine learning, is proposed. A Convolutional Neural Network and a Residual Neural Network are trained on data from states derived from games between human players. The architectures selected are described in detail as is the training process. The performance of the network policy is evaluated from play versus basic search-based methods and other network policies. The use of reinforcement learning methods in incomplete information games much less common and is mostly limited to applications with lower complexity. First a brief analysis of Markov decision processes and the basics of reinforcement learning theory are presented. Next, the Neural Fictitious Self-Play method which converges to a Nash equilibrium in two player incomplete information zero-sum games is described and tested in the case of stratego. The performance of the method is then evaluated relative to policies derived through supervised learning and basic search-based methods. In order to overcome some of the limitations that arose during the implementation of NFSP due to the high complexity of the game, the use of a simpler deep Q-learning algorithm is considered, assuming the opponent policy is static and part of the environment. The opponent’s policy is defined in such a way as to approach the behavior of the average stratego player in a similar situation. To achieve this, the opponent’s policy is defined by a neural network trained through supervised learning to mimic human player moves. The Q-network was then trained to approximate the action-value function in game states that arise from self-play. The implementation was made in python using TensorFlow 2 and Keras for the construction and training of the neural networks. The majority of the code used can be found at: https://github.com/gpapst/StrategoML 2021-10-04T10:34:06Z 2021-10-04T10:34:06Z 2021-10-03 http://hdl.handle.net/10889/15265 gr application/pdf |
