Συντάχθηκε 06-11-2026 15:11
Τόπος:
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 10/11/2026 15:00
Λήξη: 10/11/2026 16:00
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Εμμανουέλας Κυριαφίνη
με θέμα
Σχεδίαση και Ανάπτυξη Αυτόνομου Πράκτορα για το Επιτραπέζιο Παιχνίδι “Hive”
Design and Development of an Autonomous Agent for the Board Game “Hive”
Εξεταστική Επιτροπή
Καθηγητής Μιχαήλ Γ. Λαγουδάκης (Σχολή ΗΜΜΥ, Επιβλέπων)
Καθηγητής Θρασύβουλος Σπυρόπουλος (Σχολή ΗΜΜΥ)
Καθηγητής Γεώργιος Χαλκιαδάκης (Σχολή ΗΜΜΥ)
Περίληψη
Τα τελευταία χρόνια, η Τεχνητή Νοημοσύνη εφαρμόζεται ευρέως σε επιτραπέζια παιχνίδια για την επίλυση σύνθετων προβλημάτων ακολουθιακής λήψης αποφάσεων. Η παρούσα διπλωματική εργασία εστιάζει στο επιτραπέζιο παιχνίδι στρατηγικής «Hive». Σε αντίθεση με γνωστά παιχνίδια, όπως το σκάκι και το «Go», το «Hive» διακρίνεται για το μη σταθερό ταμπλώ, τον υψηλό συντελεστή διακλάδωσης και τον μεγάλο χώρο ενεργειών. Οι προκλήσεις αυτές, σε συνδυασμό με την περιορισμένη ακαδημαϊκή βιβλιογραφία γύρω από το παιχνίδι, παρακινούν την ανάπτυξη πρακτόρων ικανών να εξερευνούν αποτελεσματικά στρατηγικές και να επιτυγχάνουν σταθερά υψηλή απόδοση υπό περιορισμένους υπολογιστικούς πόρους. Στο πλαίσιο της εργασίας, αναπτύξαμε αρχικά μια σειρά από ευρετικούς πράκτορες αναφοράς (baselines) –Random, Greedy και LessGreedy– με τους δύο τελευταίους να χρησιμοποιούν προσαρμοσμένες συναρτήσεις αξιολόγησης βάσει διαφόρων μετρικών. Ως έναν πιο εξελιγμένο ευρετικό πράκτορα αναφοράς, υλοποιήσαμε τον αλγόριθμο Monte Carlo Tree Search (MCTS), ο οποίος επίσης χρησιμοποιεί μια προσαρμοσμένη συνάρτηση αξιολόγησης για μη τερματικές καταστάσεις του παιχνιδιού και εκτελεί προσομοιώσεις μέχρι κάποιο καθορισμένο βάθος. Η εισαγωγή μεθόδων βαθιάς ενισχυτικής μάθησης (Deep Reinforcement Learning - DRL) στο «Hive» φάνηκε να είναι απαραίτητη. Συνεπώς, αναπτύξαμε μια αποδοτική παραλλαγή του αλγορίθμου AlphaZero που ονομάζεται Gumbel, η οποία εφαρμόζει την τεχνική Gumbel-Top-k σε συνδυασμό με τη μέθοδο Sequential Halving, βελτιώνοντας την ποιότητα αναζήτησης και μετριάζοντας την ανάγκη για μεγάλο αριθμό προσομοιώσεων. Στη συνέχεια, προσαρμόσαμε τον αλγόριθμο Proximal Policy Optimization (PPO) στο «Hive», αξιοποιώντας την τεχνική της παραγοντοποίησης ενεργειών. Μετά την εκπαίδευση των δύο πρακτόρων μάθησης μέσω προκαταρκτικής εκπαίδευσης με σταδιακά αυξανόμενη δυσκολία (curriculum pre-training) και εκτεταμένων παιχνιδιών του πράκτορα εναντίον του εαυτού του (self-play), διεξαγάγαμε ένα τουρνουά «όλοι εναντίον όλων» (round-robin) μεταξύ των έξι πρακτόρων, με αναμετρήσεις που επέτρεψαν την ακριβή αξιολόγηση της αγωνιστικής τους αποδοτικότητας. Τα πειραματικά αποτελέσματα δείχνουν ότι τόσο ο Gumbel AlphaZero, όσο και ο PPO, επιδεικνύουν σημαντικά ανώτερη απόδοση έναντι των τεσσάρων baselines, επιτυγχάνοντας κυρίαρχα ποσοστά νικών και επιβεβαιώνοντας ότι οι αλγόριθμοι DRL είναι πράγματι αποτελεσματικοί στην επίλυση προβλημάτων υψηλής διάστασης, όπως είναι το «Hive». Τέλος, αναπτύξαμε και μια διαδραστική γραφική διεπαφή χρήστη (GUI) με τη χρήση Pygame, επιτρέποντας την ανθρώπινη αλληλεπίδραση, καθώς και τον εύκολο έλεγχο της λειτουργικότητας των πρακτόρων.
Abstract
In recent years, Artificial Intelligence (AI) has been widely applied to board games in order to solve complex, sequential decision-making tasks. This diploma thesis focuses on the strategy board game “Hive”. Unlike well-known board games, such as Chess and Go, “Hive” is distinguished by a non-fixed board, a high branching factor and a large action space. These challenges, combined with limited academic literature about the game, motivate the development of agents that can explore strategies effectively and achieve consistently high performance under limited computational budgets. As part of the thesis, we first developed a suite of heuristic agents serving as baselines –Random, Greedy, and LessGreedy– with the latter two employing custom evaluation functions using various metrics. As a more sophisticated heuristic baseline, we implemented Monte Carlo Tree Search (MCTS) that also uses a custom evaluation function for non-terminal boards and executes simulations to a certain rollout depth. Introducing deep reinforcement learning (DRL) methods into “Hive” seemed to be essential; thus, we developed an efficient variant of the AlphaZero framework, called Gumbel, which applies the Gumbel-Top-k trick paired with Sequential Halving to improve search quality and mitigate the necessity for a high number of simulations. Finally, we adapted Proximal Policy Optimization (PPO) to “Hive” using action factorization. After training the two learning agents through curriculum pre-training and extensive self-play, we conducted a round-robin tournament including all six agents, with head-to-head matchups that enabled us to measure and accurately evaluate playing strength. Experimental results show that both Gumbel AlphaZero and PPO demonstrate superior performance against the four baselines, achieving dominant win rates and confirming that DRL algorithms are indeed substantially effective in solving high-dimensional problems, such as “Hive”. Finally, we developed an interactive graphical user interface (GUI) using the Pygame framework to enable human interaction and convenient agent functionality testing.
Meeting ID: 91678710251
Password: 364304
