Τεχνητή νοημοσύνη για παιχνίδια: ανάπτυξη πρακτόρων με χρήση βαθιάς μάθησης

Abstract

Artificial intelligence has been evolving at a rapid pace in the last decade, being part of many scientific fields such as IT, medicine and even education. Its ever-increasing application in different fields contributes on the one hand to the continuous development of modern techniques and algorithms, on the other hand leads to additional requirements and new challenges for the wider field of artificial intelligence. A field of particular interest concerns the application of such algorithms in the context of games, the environments of which offer immediate feedback and at the same time introduce several difficulties and limitations. The aim of this thesis is the development of intelligent agents for video games using artificial intelligence and machine learning techniques. Under this scope, the currently prevailing techniques are examined and new algorithms and methods are proposed in order to deal with the main appearing challenges. In the first stage of the thesis, the implementation of agents based on genetic algorithms was examined. In particular, the possibility of applying a genetic algorithm as a standalone technique for encoding the states of the environment and the final decision-making by the agent was examined. In this context, a novel method for the states' representation was designed in order to reduce the state space and make feasible the implementation of the proposed approach. The representation logic was based on N-groups of blocks in order to encode states using the least possible information. The experiments carried out highlighted the functionality of this particular technique by ranking it higher than corresponding methods of different evolutionary-based approaches. Afterwards the behavior of an intelligent agent in stochastic environments was studied. In this case, the Monte Carlo tree search algorithm was mainly studied as it is the state-of-the-art approach to a large subset of the broader field of artificial intelligence for games. The first section that was considered was the optimization of the stage in which the states which are subsequently used by the algorithm are evaluated. To that end, a gradient boosting classifier trained on a specially designed dataset, was incorporated into the algorithm significantly increasing its accuracy in estimating the states' values. In addition, a stochastic evaluation process of the tree nodes was implemented aiming to better adapt the model to the branching factor. In order to exploit information more efficiently based on the trees' depth, an early simulation technique was also applied in the early stages of the algorithm leading to stronger classifier predictions. The combination of the above methods led to a great increase of the agent's performance which surpassed the optimal algorithm provided by the used framework. Then, the optimization of the selection step of the algorithm was evaluated. In this respect, the above methodology was additionally enhanced with a novel pruning technique based on the use of artificial neural networks, in order to reduce the search space. The goal is to remove the actions with low expected value from the set of possible actions during the execution of the algorithm and utilize the remaining computing resources to more accurately evaluate the remaining actions. To implement this technique, two separate neural networks were trained and used collaboratively. By combining the outputs of the two networks, the optimal pair of iterations and number of actions to be pruned is determined and the search space is being reduced iteratively until the algorithm is finished. The networks were trained on synthetic training data which were derived from a special simulation environment implemented for this purpose. The pruning technique was tested individually as well as in conjunction with the gradient boosting classifier leading to further improvement of the algorithm's performance. In the next section, the enhancement of the selection phase of the Monte Carlo tree search algorithm without domain knowledge was examined. In this case, the core idea is to match similar nodes in order to use – during the selection phase – statistics of nodes located at a higher level of the search tree which therefore have more accurate data (as they have been visited more times during the search). In this light, two different state matching methodologies were implemented based on the sequence of actions that preceded. In the first case, the nodes' similarity was based on the length of identical N-grams from which they were derived, while in the second case it was based on a specifically designed representation of the similarity of executed actions. The proposed techniques were applied to general intelligent agents' environments achieving higher performance than relevant approaches concerning the selection phase of the algorithm in the majority of cases. In the last part of the thesis, the field of reinforcement learning was investigated. In particular, the introduction of a data augmentation technique based on generative models for the creation of new, synthetic states was examined, aiming to make the training of the agent more effective. Additionally, a model was designed to predict the action performed between two successive states in order to be able to produce complete samples in the form needed to solve reinforcement learning problems. These models are combined to create synthetic data for cases of high and low immediate rewards, which are encountered less frequently during the agent’s interaction with the environment. The proposed methodology, in which the synthetic samples are mixed with the actually observed data during the training process, was evaluated in different, heterogeneous environments achieving an increase in the agent's total obtained reward compared to traditional image augmentation techniques.

Η τεχνητή νοημοσύνη εξελίσσεται την τελευταία δεκαετία με ραγδαίο ρυθμό, διεισδύοντας σε ολοένα και περισσότερους επιστημονικούς κλάδους όπως η πληροφορική, η ιατρική, ακόμα και η εκπαίδευση. Η συνεχώς αυξανόμενη εφαρμογή της σε διαφορετικούς τομείς, αναμενόμενα συμβάλλει αφενός στη διαρκή ανάπτυξη σύγχρονων τεχνικών και αλγορίθμων, αφετέρου στον προσδιορισμό επιπλέον απαιτήσεων και στη δημιουργία νέων προκλήσεων για τον ευρύτερο κλάδο της τεχνητής νοημοσύνης. Ένα πεδίο το οποίο παρουσιάζει ιδιαίτερο ενδιαφέρον αφορά την εφαρμογή τέτοιων αλγορίθμων στο πλαίσιο των παιχνιδιών, τα περιβάλλοντα των οποίων προσφέρουν άμεση ανατροφοδότηση και συγχρόνως παρουσιάζουν διαφορετικές δυσκολίες και περιορισμούς. Στόχος της παρούσας διατριβής είναι η ανάπτυξη ευφυών πρακτόρων για ηλεκτρονικά παιχνίδια με τη χρήση τεχνητής νοημοσύνης και τεχνικών μηχανικής μάθησης. Υπό αυτό το πρίσμα, εξετάζονται οι επικρατέστερες επί του παρόντος τεχνικές, προτείνονται αλγόριθμοι και παρουσιάζονται μέθοδοι προκειμένου να αντιμετωπιστούν ορισμένες από τις κυριότερες προκλήσεις που εμφανίζονται. Στο πρώτο στάδιο της διατριβής εξετάστηκε η υλοποίηση πρακτόρων με βάση τους γενετικούς αλγορίθμους. Συγκεκριμένα, διερευνήθηκε η δυνατότητα να εφαρμοστούν ως αυτούσια τεχνική για την κωδικοποίηση των καταστάσεων του περιβάλλοντος και την τελική λήψη αποφάσεων από τον πράκτορα. Σε αυτό το πλαίσιο σχεδιάστηκε και μία νέα μέθοδος αναπαράστασης των καταστάσεων προκειμένου να μειωθεί ο χώρος καταστάσεων και να είναι εφικτή η υλοποίηση της προτεινόμενης προσέγγισης. Η λογική της αναπαράστασης βασίστηκε σε ένα μοτίβο Ν-πλειάδων από συντεταγμένες του χώρου προκειμένου να κωδικοποιηθούν οι καταστάσεις χρησιμοποιώντας τη λιγότερη δυνατή πληροφορία. Τα πειράματα που διενεργήθηκαν ανέδειξαν τη λειτουργικότητα της συγκεκριμένης τεχνικής κατατάσσοντάς την υψηλότερα από αντίστοιχες μεθόδους διαφορετικής προσέγγισης των εξελικτικών αλγορίθμων. Στη συνέχεια μελετήθηκε η συμπεριφορά ενός ευφυούς πράκτορα σε στοχαστικά περιβάλλοντα. Σε αυτήν την περίπτωση, ερευνήθηκε κατά κύριο λόγο ο αλγόριθμος δενδρικής αναζήτησης Μόντε Κάρλο που αποτελεί την προσέγγιση αιχμής για ένα μεγάλο υποσύνολο του ευρύτερου πεδίου της τεχνητής νοημοσύνης για παιχνίδια. Το πρώτο τμήμα που εξετάστηκε ήταν η βελτιστοποίηση του σταδίου κατά το οποίο γίνεται η αξιολόγηση των καταστάσεων που χρησιμοποιούνται στη συνέχεια από τον αλγόριθμο. Για το σκοπό αυτό, ένας ταξινομητής ακραίας ενίσχυσης κλίσης εκπαιδευμένος σε ειδικά σχεδιασμένο σύνολο δεδομένων, ενσωματώθηκε στον αλγόριθμο αυξάνοντας σε σημαντικό βαθμό την ακρίβεια αποτίμησης της αξίας καταστάσεων. Επιπλέον υλοποιήθηκε μία διαδικασία στοχαστικής αξιολόγησης των κόμβων του δέντρου αναζήτησης με στόχο την προσαρμογή του μοντέλου ανάλογα με το συντελεστή διακλάδωσης. Για την αποδοτικότερη εκμετάλλευση της πληροφορίας με βάση το βάθος των δέντρων, εφαρμόστηκε και μία τεχνική πρώιμης προσομοίωσης στα αρχικό στάδιο του αλγορίθμου που οδήγησε σε ισχυρότερες προβλέψεις του ταξινομητή. Ο συνδυασμός των παραπάνω μεθόδων οδήγησε σε μεγάλη αύξηση της απόδοσης του πράκτορα, που ξεπέρασε τον βέλτιστο αλγόριθμο που παρέχεται από το περιβάλλον στο οποίο δοκιμάστηκε. Έπειτα, αξιολογήθηκε η βελτιστοποίηση του σταδίου επιλογής του αλγορίθμου. Σε αυτό το πλαίσιο, η παραπάνω μεθοδολογία ενισχύθηκε επιπλέον με μία πρωτότυπη τεχνική κλαδέματος βασισμένη σε χρήση τεχνητών νευρωνικών δικτύων, προκειμένου να μειωθεί ο χώρος αναζήτησης. Στόχος είναι κατά τη διάρκεια του αλγορίθμου να αφαιρούνται από το σύνολο των ενεργειών προς εξέταση οι ενέργειες που δεν αναμένεται να έχουν υψηλή αξία και οι εναπομείναντες υπολογιστικοί πόροι να αξιοποιούνται για την ακριβέστερη αξιολόγηση των υπόλοιπων ενεργειών. Για την υλοποίηση αυτής της μεθόδου εκπαιδεύτηκαν δύο διαφορετικά νευρωνικά δίκτυα τα οποία χρησιμοποιήθηκαν συνεργατικά. Με το συνδυασμό των εξόδων των δύο δικτύων προσδιορίζεται το βέλτιστο ζεύγος επαναλήψεων και πλήθους ενεργειών προς αφαίρεση και μειώνεται επαναληπτικά ο χώρος αναζήτησης μέχρι την ολοκλήρωση του αλγορίθμου. Η εκπαίδευση των δικτύων έγινε σε συνθετικά δεδομένα εκπαίδευσης τα οποία προέκυψαν από ειδικό περιβάλλον προσομοίωσης που υλοποιήθηκε για αυτό το σκοπό. Η τεχνική κλαδέματος χρησιμοποιήθηκε τόσο αυτούσια όσο και σε συνδυασμό με τον ταξινομητή ενίσχυσης κλίσης οδηγώντας σε περαιτέρω βελτίωση της απόδοσης του αλγορίθμου. Στο επόμενο μέρος, εξετάστηκε η ενίσχυση της φάσης επιλογής στη δενδρική αναζήτηση Μόντε Κάρλο χωρίς την εισαγωγή γνώσης πεδίου. Η βασική ιδέα σε αυτή την περίπτωση αφορά στην αντιστοίχιση παρόμοιων κόμβων προκειμένου να γίνεται – κατά τη διαδικασία της επιλογής – χρήση στατιστικών των κόμβων που βρίσκονται σε υψηλότερο επίπεδο του δέντρου αναζήτησης και συνεπώς έχουν ακριβέστερα δεδομένα (καθώς έχουν επισκεφθεί περισσότερες φορές κατά τη διάρκεια της αναζήτησης). Υπό αυτό το πρίσμα υλοποιήθηκαν δύο διαφορετικές μεθοδολογίες αντιστοίχισης καταστάσεων με βάση την ακολουθία των ενεργειών που προηγήθηκαν. Στην πρώτη περίπτωση ο προσδιορισμός της ομοιότητας των κόμβων έγινε με κριτήριο το μήκος των πανομοιότυπων Ν-γράμμων από τα οποία προέκυψαν ενώ στη δεύτερη έγινε με βάση μία ειδικά σχεδιασμένη αναπαράσταση της ομοιότητας των ενεργειών που εκτελέστηκαν. Οι προτεινόμενες τεχνικές εφαρμόστηκαν σε περιβάλλοντα γενικών ευφυών πρακτόρων, πετυχαίνοντας υψηλότερη απόδοση από τις αντίστοιχες προσεγγίσεις που αφορούν το στάδιο επιλογής του αλγορίθμου στην πλειοψηφία των περιπτώσεων. Στο τελευταίο σκέλος της διατριβής, διερευνήθηκε το πεδίο της ενισχυτικής μάθησης. Ιδιαίτερα, εξετάστηκε η εισαγωγή μίας τεχνικής επαύξησης δεδομένων με γεννητικά μοντέλα για τη δημιουργία νέων, συνθετικών καταστάσεων με στόχο την αποτελεσματικότερη εκπαίδευση του πράκτορα. Συμπληρωματικά, σχεδιάστηκε ένα μοντέλο για την πρόβλεψη της ενέργειας που εκτελείται μεταξύ δύο διαδοχικών καταστάσεων προκειμένου να είναι εφικτή η σύνθεση ολοκληρωμένων δειγμάτων στη μορφή που απαιτείται για την επίλυση προβλημάτων ενισχυτικής μάθησης. Τα επιμέρους μοντέλα χρησιμοποιήθηκαν συνδυαστικά για τη δημιουργία συνθετικών δεδομένων με υψηλή και χαμηλή άμεση ανταμοιβή, τα οποία συναντώνται λιγότερο συχνά κατά τη διάρκεια της αλληλεπίδρασης του πράκτορα με το περιβάλλον. Η προτεινόμενη μεθοδολογία, στην οποία τα συνθετικά δείγματα αναμειγνύονται με τα πραγματικά δεδομένα κατά τη διαδικασία της εκπαίδευσης, αξιολογήθηκε σε διαφορετικά, ετερογενή περιβάλλοντα επιτυγχάνοντας αύξηση της συνολικής ανταμοιβής του πράκτορα συγκριτικά με αντίστοιχες κλασσικές τεχνικές επαύξησης εικόνας.