title: Implementation of an intelligent agent for the AIBIRDS competition
title: Ανάπτυξη ευφυούς πράκτορα για τον διαγωνισμό AIBIRDS
Creators: name: Γεμιστος Μιχαηλ
Publisher: name: Technical University of Crete
Year: 2019

description: The broad field of Artificial Intelligence (AI) strives to reproduce
human behavior on machines. Machine Learning, as a subfield, and more
specifically Reinforcement Learning (RL), enables autonomous agents to
take suitable actions under different circumstances through a
trial-and-error learning process, without being programmed for every
possible scenario they may encounter. Since 2013, the International
Joint Conference on Artificial Intelligence (IJCAI) hosts the Angry
Birds AI Competition (AIBIRDS), where various AI agents compete on the
Angry Birds computer game. The agents compete on unknown game levels
without any human intervention. In this thesis, we designed two agents
for AIBIRDS following the principles of two well-known RL algorithms,
namely Q-Learning and Least Squares Policy Iteration (LSPI). Both of
them are model-free RL algorithms, trying to learn the best action at
each step (policy) for any given game scene. Since the action and state
spaces of the game are extremely large and due to the absence of a model
that describes the transition from a state to a next state affected by
an action choice, we used an approximation architecture to represent the
learned Q values, which estimate the quality of each action in each
state. The approximation uses a set of eight basis functions (features)
we designed, which try to describe a game scene effectively, and each
one is weighted by its own parameter (weight). In our experiments, the
Q-Learning agent is trained for 20,000 iterations updating its weights
incrementally during the course of that training, concluding to their
final values, when the iterations are completed. At each iteration, the
Q-Learning agent stores locally each observed sample of interaction with
the game, which includes the current state, the action taken, the new
state and the reward gained. The LSPI agent is then trained using the
stored set of samples to find its own set of weights and thus its own
policy. When the process of training ends for both Q-Learning and LSPI
on the same observed samples, we test each agent on 54 different levels
taken directly from the AIBIRDS competition, 34 of those being the
levels our agents were trained on and 20 levels being completely new to
the agents. The Q-Learning agent is able to complete successfully 68% of
these levels and the LSPI agent 81% of them, occasionally performing
precise shots with amazing results.

description: Το ευρύ πεδίο της Τεχνητής Νοημοσύνης (Artificial Intelligence - AI) προσπαθεί να αναπαράγει την ανθρώπινη συμπεριφορά στις μηχανές. Η Μηχανική Μάθηση, ως υποπεδίο, και πιο συγκεκριμένα η Ενισχυτική Μάθηση (Reinforcement Learning - RL), δίνει τη δυνατότητα σε αυτόνομους πράκτορες να επιλέγουν κατάλληλες ενέργειες κάτω από διαφορετικές συνθήκες μέσω μιας διαδικασίας μάθησης δοκιμών-και-σφαλμάτων, χωρίς να προγραμματίζονται για κάθε πιθανό σενάριο που μπορεί να συναντήσουν. Από το 2013, το συνέδριο International Joint Conference on Artificial Intelligence (IJCAI) φιλοξενεί τον Διαγωνισμό Angry Birds AI (AIBIRDS), όπου διάφοροι AI πράκτορες ανταγωνίζονται στο ηλεκτρονικό παιχνίδι Angry Birds. Οι πράκτορες ανταγωνίζονται σε άγνωστες πίστες παιχνιδιού χωρίς καμία ανθρώπινη παρέμβαση. Στην παρούσα διπλωματική εργασία, σχεδιάσαμε δύο πράκτορες για το AIBIRDS ακολουθώντας τις αρχές δύο γνωστών RL αλγορίθμων, συγκεκριμένα του Q-Learning και του Least Squares Policy Iteration (LSPI). Και οι δύο είναι RL αλγόριθμοι χωρίς μοντέλα και προσπαθούν να μάθουν την καλύτερη ενέργεια σε κάθε βήμα (πολιτική) για κάθε δεδομένη σκηνή του παιχνιδιού. Δεδομένου ότι οι χώροι ενεργειών και καταστάσεων του παιχνιδιού είναι εξαιρετικά μεγάλοι και λόγω της απουσίας ενός μοντέλου που περιγράφει τη μετάβαση από μια κατάσταση σε κάποια επόμενη κατάσταση υπό την επιρροή μιας επιλεγμένης ενέργειας, χρησιμοποιήσαμε μια αρχιτεκτονική προσέγγισης για να αναπαριστούμε τις μαθηματικές τιμές Q, οι οποίες εκτιμούν την ποιότητα κάθε ενέργειας σε κάθε κατάσταση. Η προσέγγιση χρησιμοποιεί ένα σύνολο από οκτώ συναρτήσεις βάσης (χαρακτηριστικά) που σχεδιάσαμε, τα οποία προσπαθούν να περιγράψουν αποτελεσματικά μια σκηνή παιχνιδιού, και κάθε μία σταθμίζεται με τη δική της παράμετρο (βάρος). Στα πειράματά μας, ο πράκτορας Q-Learning εκπαιδεύεται για 20.000 επαναλήψεις για την ενημέρωση των βαρών του σταδιακά κατά τη διάρκεια αυτής της εκπαίδευσης, καταλήγοντας στις τελικές τους τιμές, όταν ολοκληρωθούν οι επαναλήψεις. Σε κάθε επανάληψη, ο πράκτορας Q-Learning αποθηκεύει τοπικά το κάθε παρατηρούμενο δείγμα αλληλεπίδρασης με το παιχνίδι, το οποίο περιλαμβάνει την τρέχουσα κατάσταση, τη ενέργεια που έχει ληφθεί, τη νέα κατάσταση και την ανταμοιβή που αποκτήθηκε. Ο πράκτορας LSPI εκπαιδεύεται στη συνέχεια χρησιμοποιώντας το αποθηκευμένο σύνολο δειγμάτων για να βρει το δικό του σύνολο βαρών και επομένως τη δική του πολιτική. Όταν η διαδικασία εκπαίδευσης τελειώσει τόσο για τον Q-Learning όσο και για τον LSPI πάνω στα ίδια παρατηρούμενα δείγματα, εξετάζουμε κάθε πράκτορα σε 54 διαφορετικές πίστες που ελήφθησαν απευθείας από τον διαγωνισμό AIBIRDS, 34 εκ των οποίων είναι αυτές όπου εκπαιδεύτηκαν οι πράκτορές μας και 20 είναι παντελώς άγνωστες στους πράκτορες. Ο πράκτορας Q-Learning είναι σε θέση να ολοκληρώσει επιτυχώς το 68% και ο πράκτορας LSPI το 81% εξ αυτών, εκτελώντας κατά διαστήματα βολές ακριβείας με εκπληκτικά αποτελέσματα.