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

Search

Browse

My Space

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

Tsigdinos Stylianos

Full record


URI: http://purl.tuc.gr/dl/dias/5C411346-85BC-401A-B86D-5A8FDA432ED8
Year 2014
Type of Item Diploma Work
License
Details
Bibliographic Citation Στυλιανός Τσιγδινός, "Συστηματική αναζήτηση και ενισχυτική μάθηση για το επιτραπέζιο παιχνίδι Backgammon", Διπλωματική Εργασία, Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2014 https://doi.org/10.26233/heallink.tuc.20717
Appears in Collections

Summary

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.

Available Files

Services

Statistics