Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

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

Tsigdinos Stylianos

Simple record


URIhttp://purl.tuc.gr/dl/dias/5C411346-85BC-401A-B86D-5A8FDA432ED8-
Identifierhttps://doi.org/10.26233/heallink.tuc.20717-
Languageel-
Extent68 σελίδεςel
TitleΣυστηματική αναζήτηση και ενισχυτική μάθηση για το επιτραπέζιο παιχνίδι Backgammonel
CreatorTsigdinos Stylianosen
CreatorΤσιγδινος Στυλιανοςel
Contributor [Thesis Supervisor]Lagoudakis Michaelen
Contributor [Thesis Supervisor]Λαγουδακης Μιχαηλel
Contributor [Committee Member]Zervakis Michalisen
Contributor [Committee Member]Ζερβακης Μιχαληςel
Contributor [Committee Member]Petrakis Evripidisen
Contributor [Committee Member]Πετρακης Ευριπιδηςel
PublisherTechnical University of Creteen
PublisherΠολυτεχνείο Κρήτηςel
Academic UnitTechnical University of Crete::School of Electronic and Computer Engineeringen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστώνel
Content SummaryΤα παιχνίδια απασχολούσαν, από τότε που υπάρχει πολιτισμός, τις διανοητικές λειτουργίες του ανθρώπου. Στα πλαίσια της Τεχνητής Νοημοσύνης, η αφηρημένη φύση των παιχνιδιών καθώς και η δυσκολία επίλυσής τους τα καθιστά ένα ενδιαφέρον πεδίο μελέτης. Στην παρούσα διπλωματική εργασία υλοποιούμε ένα πράκτορα για το επιτραπέζιο παιχνίδι Backgammon καθώς και ένα γραφικό περιβάλλον στο οποίο μπορούν να διεξαχθούν παρτίδες του παιχνιδιού αυτού με αντίπαλο τον πράκτορα μας ή κάποιον άνθρωπο-παίκτη. Σκοπός μας είναι η εύρεση μιας καλής στρατηγικής (policy), η οποία θα επιτρέπει στον πράκτορά μας να αυξήσει τις πιθανότητές του, με την κατάλληλη επιλογή κινήσεων, να οδηγηθεί σε μία τερματική κατάσταση νίκης. Η στρατηγική αυτή προσδιορίζει ουσιαστικά την συμπεριφορά του πράκτορα κατά την διάρκεια του παιχνιδιού. Ο μεγάλος παράγοντας διακλάδωσης του δέντρου αναζήτησης για το παιχνίδι αυτό, που πολλές φορές μπορεί να φτάσει μέχρι και κάποιες εκατοντάδες κινήσεις, καθώς και το στοιχείο της τύχης που ενυπάρχει στη φύση του παιχνιδιού, λόγω του ότι χρησιμοποιούνται ζάρια για την υπόδειξη των δυνατών αποστάσεων στις κινήσεις των δύο αντιπάλων, αυξάνει σημαντικά την δυσκολία αναζήτησης και εύρεσης της βέλτιστης αυτής στρατηγικής. Χρησιμοποιώντας ειδικές τεχνικές αναζήτησης, όπως αυτή του αλγόριθμου MiniMax και κάποιες παραλλαγές του όπως αυτή του κλαδέματος Alpha-Beta, πετύχαμε αποδεκτές ταχύτητες αναζήτησης σε ικανοποιητικό βάθος στο δέντρο αναζήτησης του παιχνιδιού. Η συστηματική αναζήτηση σε συνδυασμό με τη χρήση τεχνικών από το πεδίο της ενισχυτικής μάθησης (Reinforcement Learning) για την εκμάθηση μιας κατάλληλης συνάρτησης αξιολόγησης μέσα από δοκιμές σε πολλές παρτίδες, οδήγησαν στην εύρεση μιας στρατηγικής, η οποία επιτρέπει στον πράκτορά μας να ανταγωνιστεί αρκετά καλούς φυσικούς αλλά και τεχνητούς παίκτες στο παιχνίδι Backgammon.el
Content SummaryEver 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
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2014-09-08-
Date of Publication2014-
SubjectBackgammonel
SubjectLearning, Machineen
Subjectmachine learningen
Subjectlearning machineen
SubjectAI (Artificial intelligence)en
SubjectArtificial thinkingen
SubjectElectronic brainsen
SubjectIntellectronicsen
SubjectIntelligence, Artificialen
SubjectIntelligent machinesen
SubjectMachine intelligenceen
SubjectThinking, Artificialen
Subjectartificial intelligenceen
Subjectai artificial intelligenceen
Subjectartificial thinkingen
Subjectelectronic brainsen
Subjectintellectronicsen
Subjectintelligence artificialen
Subjectintelligent machinesen
Subjectmachine intelligenceen
Subjectthinking artificialen
Bibliographic CitationΣτυλιανός Τσιγδινός, "Συστηματική αναζήτηση και ενισχυτική μάθηση για το επιτραπέζιο παιχνίδι Backgammon", Διπλωματική Εργασία, Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2014el

Available Files

Services

Statistics