Institutional Repository
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Systematic search and reinforcement learning for the "Amazons" board game

Konstantakis Georgios

Full record


URI: http://purl.tuc.gr/dl/dias/F6CCE2BB-554D-4944-8E06-5F9EC32D9694
Year 2017
Type of Item Diploma Work
License
Details
Appears in Collections

Summary

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.

Available Files

Services

Statistics