Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Συστηματική αναζήτηση και ενισχυτική μάθηση για το επιτραπέζιο παιχνίδι Backgammon

Tsigdinos Stylianos

Απλή Εγγραφή

URIhttp://purl.tuc.gr/dl/dias/5C411346-85BC-401A-B86D-5A8FDA432ED8-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.20717-
Γλώσσαel-
Μέγεθος68 σελίδεςel
ΤίτλοςΣυστηματική αναζήτηση και ενισχυτική μάθηση για το επιτραπέζιο παιχνίδι Backgammonel
ΔημιουργόςTsigdinos Stylianosen
ΔημιουργόςΤσιγδινος Στυλιανοςel
Συντελεστής [Επιβλέπων Καθηγητής]Lagoudakis Michaelen
Συντελεστής [Επιβλέπων Καθηγητής]Λαγουδακης Μιχαηλel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Zervakis Michalisen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Ζερβακης Μιχαληςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Petrakis Evripidisen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Πετρακης Ευριπιδηςel
ΕκδότηςTechnical University of Creteen
ΕκδότηςΠολυτεχνείο Κρήτηςel
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electronic and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστώνel
ΠερίληψηΤα παιχνίδια απασχολούσαν, από τότε που υπάρχει πολιτισμός, τις διανοητικές λειτουργίες του ανθρώπου. Στα πλαίσια της Τεχνητής Νοημοσύνης, η αφηρημένη φύση των παιχνιδιών καθώς και η δυσκολία επίλυσής τους τα καθιστά ένα ενδιαφέρον πεδίο μελέτης. Στην παρούσα διπλωματική εργασία υλοποιούμε ένα πράκτορα για το επιτραπέζιο παιχνίδι Backgammon καθώς και ένα γραφικό περιβάλλον στο οποίο μπορούν να διεξαχθούν παρτίδες του παιχνιδιού αυτού με αντίπαλο τον πράκτορα μας ή κάποιον άνθρωπο-παίκτη. Σκοπός μας είναι η εύρεση μιας καλής στρατηγικής (policy), η οποία θα επιτρέπει στον πράκτορά μας να αυξήσει τις πιθανότητές του, με την κατάλληλη επιλογή κινήσεων, να οδηγηθεί σε μία τερματική κατάσταση νίκης. Η στρατηγική αυτή προσδιορίζει ουσιαστικά την συμπεριφορά του πράκτορα κατά την διάρκεια του παιχνιδιού. Ο μεγάλος παράγοντας διακλάδωσης του δέντρου αναζήτησης για το παιχνίδι αυτό, που πολλές φορές μπορεί να φτάσει μέχρι και κάποιες εκατοντάδες κινήσεις, καθώς και το στοιχείο της τύχης που ενυπάρχει στη φύση του παιχνιδιού, λόγω του ότι χρησιμοποιούνται ζάρια για την υπόδειξη των δυνατών αποστάσεων στις κινήσεις των δύο αντιπάλων, αυξάνει σημαντικά την δυσκολία αναζήτησης και εύρεσης της βέλτιστης αυτής στρατηγικής. Χρησιμοποιώντας ειδικές τεχνικές αναζήτησης, όπως αυτή του αλγόριθμου MiniMax και κάποιες παραλλαγές του όπως αυτή του κλαδέματος Alpha-Beta, πετύχαμε αποδεκτές ταχύτητες αναζήτησης σε ικανοποιητικό βάθος στο δέντρο αναζήτησης του παιχνιδιού. Η συστηματική αναζήτηση σε συνδυασμό με τη χρήση τεχνικών από το πεδίο της ενισχυτικής μάθησης (Reinforcement Learning) για την εκμάθηση μιας κατάλληλης συνάρτησης αξιολόγησης μέσα από δοκιμές σε πολλές παρτίδες, οδήγησαν στην εύρεση μιας στρατηγικής, η οποία επιτρέπει στον πράκτορά μας να ανταγωνιστεί αρκετά καλούς φυσικούς αλλά και τεχνητούς παίκτες στο παιχνίδι Backgammon.el
ΠερίληψηEver since the birth of civilization, games have played an important role in the intellectual abilities of mankind. In the context of Artificial Intelligence, the abstract concept of games, as well as the difficulty of gaining a victory, makes games an interesting field of study. The present thesis studies the design and implementation of an agent for the board game Backgammon and a graphic environment in which Backgammon games can take place having as a competitor either a human or a software agent. The goal of the thesis is the finding of a good strategy (policy), which will allow our agent to maximize its chances, with the appropriate selection of moves, to get to a final state of victory. This strategy essentially defines the performance of the agent during the game. The branching factor of the search tree for this game, which in many cases rises up to hundreds of moves, as well as the factor of chance, given the use of dice for indicating possible distances in the moves of the two opponents, increases substantially the difficulty of search for an optimal strategy. Using specialized search techniques, such as the MiniMax algorithm enhanced with Alpha-Beta pruning, our agent achieves acceptable search times to a satisfactory depth within the search tree of the game. The applied search techniques, combined with machine learning techniques from the field of Reinforcement Learning for learning a good evaluation function by trial and error in numerous games played, led to the finding of a strategy that allows our agent to play at competitive level against several good human players, as well as against other autonomous agents, in the game of Backgammon.en
ΤύποςΔιπλωματική Εργασίαel
ΤύποςDiploma Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2014-09-08-
Ημερομηνία Δημοσίευσης2014-
Θεματική ΚατηγορίαBackgammonel
Θεματική ΚατηγορίαLearning, Machineen
Θεματική Κατηγορίαmachine learningen
Θεματική Κατηγορίαlearning machineen
Θεματική ΚατηγορίαAI (Artificial intelligence)en
Θεματική ΚατηγορίαArtificial thinkingen
Θεματική ΚατηγορίαElectronic brainsen
Θεματική ΚατηγορίαIntellectronicsen
Θεματική ΚατηγορίαIntelligence, Artificialen
Θεματική ΚατηγορίαIntelligent machinesen
Θεματική ΚατηγορίαMachine intelligenceen
Θεματική ΚατηγορίαThinking, Artificialen
Θεματική Κατηγορίαartificial intelligenceen
Θεματική Κατηγορίαai artificial intelligenceen
Θεματική Κατηγορίαartificial thinkingen
Θεματική Κατηγορίαelectronic brainsen
Θεματική Κατηγορίαintellectronicsen
Θεματική Κατηγορίαintelligence artificialen
Θεματική Κατηγορίαintelligent machinesen
Θεματική Κατηγορίαmachine intelligenceen
Θεματική Κατηγορίαthinking artificialen
Βιβλιογραφική ΑναφοράΣτυλιανός Τσιγδινός, "Συστηματική αναζήτηση και ενισχυτική μάθηση για το επιτραπέζιο παιχνίδι Backgammon", Διπλωματική Εργασία, Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2014el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά

 

Copyright © DIAS 2013