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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Konstantakis Georgios

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/F6CCE2BB-554D-4944-8E06-5F9EC32D9694-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.68543-
Γλώσσαel-
Μέγεθος62 σελίδεςel
ΤίτλοςΣυστηματική αναζήτηση και ενισχυτική μάθηση για το επιτραπέζιο παιχνίδι "Amazons"el
ΤίτλοςSystematic search and reinforcement learning for the "Amazons" board gameen
ΔημιουργόςKonstantakis Georgiosen
ΔημιουργόςΚωνσταντακης Γεωργιοςel
Συντελεστής [Επιβλέπων Καθηγητής]Lagoudakis Michaelen
Συντελεστής [Επιβλέπων Καθηγητής]Λαγουδακης Μιχαηλel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Deligiannakis Antoniosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Δεληγιαννακης Αντωνιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Chalkiadakis Georgiosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Χαλκιαδακης Γεωργιοςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
ΠερίληψηΤα παιχνίδια αποτελούσαν πάντα ένα πολύτιμο κομμάτι της έρευνας στον τομέα της Τεχνητής Νοημοσύνης και της Μηχανικής Μάθησης λόγω των υψηλών δεξιοτήτων που απαιτούν. Η παρούσα διπλωματική εργασία επικεντρώνεται στο επιτραπέζιο παιχνίδι Amazons, το οποίο τα τελευταία χρόνια έχει αρχίσει να προσελκύει ερευνητές του τομέα της Τεχνητής Νοημοσύνης και της Μηχανικής Μάθησης. Το Amazons είναι ένα παιχνίδι σκακιέρας που παίζεται από δύο παίκτες με εναλλασσόμενες κινήσεις. Κάθε παίκτης χειρίζεται 4 πούλια που κινούνται όπως οι βασίλισσες στο σκάκι, αλλά μετά από κάθε κίνηση πρέπει να τοποθετηθεί κάποιο μόνιμο εμπόδιο σε κάποια θέση στην σκακιέρα βάσει των κανόνων του παιχνιδιού. Νικητής είναι ο παίκτης που θα παγιδεύσει τον αντίπαλό του, ώστε να μην μπορεί να κινηθεί. Χαρακτηριστικό του παιχνιδιού είναι ο μεγάλος αριθμός επιλογών σε κάθε κίνηση. Στόχος της εργασίας είναι ο σχεδιασμός ενός αυτόνομου πράκτορα, ο οποίος θα είναι ικανός να παίξει ανταγωνιστικά το παιχνίδι, αλλά και ένα παραμετροποιήσιμο γραφικό περιβάλλον, μέσω του οποίου μπορούν οπτικοποιηθούν και να διεξαχθούν παιχνίδια μεταξύ διαφόρων παικτών (πρακτόρων ή ανθρώπων). Η στρατηγική του πράκτορά μας για την επιλογή κινήσεων βασίζεται στον αλγόριθμο αναζήτησης MiniMax με α-β Pruning σε συνδυασμό με μια προσθήκη εμπνευσμένη από τον αλγόριθμο Monte Carlo Tree Search. Σημαντικό ρόλο στην αξιολόγηση κινήσεων έχει η συνάρτηση αξιολόγησης που σχεδιάστηκε, τα βάρη της οποίας προσαρμόζονται μέσω του αλγορίθμου ενισχυτικής μάθησης TD-Learning κατά την εκτέλεση πολλών επαναλήψεων του παιχνιδιού. Ο συνδυασμός των παραπάνω οδήγησε στην δημιουργία διάφορων αποδοτικών παικτών, οι οποίοι αξιολογήθηκαν στα πλαίσια ενός τουρνουά.el
ΠερίληψηGames have always been a valuable subject of research in the fields of Artificial Intelligence and Machine Learning, because of the high level of sophistication they require. This thesis focuses on a board game called “Amazons”, which during the recent years has started attracting researchers from the field of Artificial Intelligence and Machine Learning. Amazons is a chess-board game played by two players taking alternating turns. Each player handles 4 checkers, whose movements are similar to the queen in chess, but after each move a permanent obstacle must be also placed on a chessboard position, according to the rules of the game. The player who will trap his opponent and will make him unable to move is the winner. Central feature of the game is the large number of choices that each player has at each turn. The goal of this thesis is to create an autonomous agent, which will be able to play this game competitively, but also to create a graphical environment, through which many games among different players (agents or people) can take place. Our agent’s strategy for choosing moves is based on the MiniMax search algorithm with alpha-beta Pruning, combined with an addition inspired by the Monte Carlo Tree Search Algorithm. An important role for the movements’ evaluation is the proposed evaluation function designed for the game, the weights of which are adapted through the reinforcement learning algorithm TD-Learning by repeatedly playing many games. The combination of the techniques mentioned above led to the creation of several efficient players who were evaluated through a tournament.en
ΤύποςΔιπλωματική Εργασίαel
ΤύποςDiploma Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2017-07-06-
Ημερομηνία Δημοσίευσης2017-
Θεματική ΚατηγορίαArtificial intelligenceen
Θεματική ΚατηγορίαΤεχνητή νοημοσύνηel
Βιβλιογραφική ΑναφοράGeorgios Konstantakis, "Systematic search and reinforcement learning for the "Amazons" board game", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2017en
Βιβλιογραφική ΑναφοράΓεώργιος Κωνσταντάκης, "Συστηματική αναζήτηση και ενισχυτική μάθηση για το επιτραπέζιο παιχνίδι "Amazons"", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2017el

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

Υπηρεσίες

Στατιστικά