Ανάπτυξη αλγορίθμου τεχνητής ευφυίας αυτόματης εκμάθησης της στρατηγικής παίκτη στο επιτραπέζιο παιχνίδι Dominion

Αγγελόπουλος, Γεώργιος

Development of an artificial intelligence algorithm for auto-learning the player strategy for the Dominion board game

Μεταπτυχιακή διπλωματική εργασία

Author

Αγγελόπουλος, Γεώργιος

Date

2021-02-05

Advisor

Μετάφας, Δημήτριος

Μεταπτυχιακή εργασία (1.758Mb)

Keywords

Επιτραπέζια παιχνίδια ; Εξαναγκασμένη μάθηση ; Μέθοδος επιλογής ενεργειών ; Τεχνητή νοημοσύνη ; Dominion ; Q-learning

Abstract

Κατά τα προηγούμενα χρόνια, αρκετά επιτραπέζια παιχνίδια έχουν χρησιμοποιηθεί σαν χώρος ανάπτυξης και δοκιμής, διαφόρων τεχνικών τεχνητής νοημοσύνης. Τα επιτραπέζια παιχνίδια είναι ιδανικά για αυτό το ρόλο, καθώς προσφέρουν ένα περιβάλλον με αυστηρά καθορισμένους κανόνες, που δεν επιδέχονται εξαιρέσεις, και τα αποτελέσματα δεν παρουσιάζουν σφάλματα ή «θορύβους». Είναι ένας ιδεατός κόσμος, στον οποίο μπορούν να δοκιμαστούν θεωρίες και τεχνικές, και να εκτιμηθεί η αποτελεσματικότητα τους, πριν την επέκταση τους στο «χάος» του πραγματικού κόσμου. Στόχος της παρούσης εργασίας ήταν η δημιουργία αλγόριθμου τεχνητής νοημοσύνης, βασισμένου στη μέθοδο της εξαναγκασμένης μάθησης, και πιο συγκεκριμένα στην τεχνική Q Learning, ικανού να αναπτύξει στρατηγική με προοπτικές νίκης, για ένα επιτραπέζιο παιχνίδι. Το ερώτημα που προσπαθούμε να απαντήσουμε, είναι το κατά πόσο η συγκεκριμένη τεχνική, είναι ικανή να ανταποκριθεί με ικανοποιητικό τρόπο, σε ένα πολύπλοκο περιβάλλον, και να εκπαιδεύσει έναν πράκτορα, ώστε να παίρνει την καλύτερη δυνατή απόφαση, όταν ο αριθμός των επιλογών είναι μεγάλος. Στην πορεία της εργασίας ανέκυψε και ένα νέο ερώτημα, κατά πόσο είναι δυνατό επιφέροντας κάποιες αλλαγές στην μέθοδο επιλογής ενεργειών του πράκτορα, να επιταχύνουμε την εκπαίδευση, χωρίς να μειώσουμε την αποτελεσματικότητά του. Επιλέξαμε το επιτραπέζιο παιχνίδι καρτών Dominion (Κυρίαρχος) για τις δοκιμές μας, καθώς έχει αρκετά απλούς κανόνες, αλλά ο αριθμός των διαφορετικών καρτών που χρησιμοποιούνται, δημιουργεί ένα μεγάλο φάσμα διαφορετικών επιλογών, και καθιστά το στόχο της εκπαίδευσης του πράκτορα αρκετά προκλητικό. Επίσης κατά το παρελθόν, άλλες τεχνικές εξαναγκασμένης μάθησης, όπως τα νευρωνικά δίκτυα και τα Monte Carlo Trees, έχουν δοκιμαστεί πάνω στο συγκεκριμένο παιχνίδι, οπότε μπορούν να εξαχθούν χρήσιμα συμπεράσματα, από τα αποτελέσματα της κάθε τεχνικής.

Abstract

In recent years, several board games have been used as a test field for the development of various artificial intelligence techniques. Board games are ideal for this role, as they offer an environment with strict rules, no exceptions, and the results are error-free and without “noise”. It is an imaginary world, in which theories and techniques can be tested, and their effectiveness evaluated, before extending to the "chaos" of the real world. The aim of this paper was to create an artificial intelligence algorithm for a board game, based on the method of reinforcement learning, and more specifically on the Q Learning technique, capable of developing a strategy with the prospect of winning. The question we are trying to answer is whether this particular technique is capable of responding satisfactorily, in a complex environment, and training an agent which makes the best possible decisions when the number of options is quite large. In the course of the work, a new question arose, whether it is possible, by making some changes in the action selection method of the agent, to accelerate the training, without reducing its effectiveness. We chose the Dominion card game for our tests, as it has quite simple rules, but the number of different cards used, creates a huge range of different options, and makes the goal of agent training quite challenging. Also in the past, other reinforcement learning techniques, such as neural networks and Monte Carlo Trees, have been tested on this game, so useful conclusions can be drawn from the results of each technique.