The subject of my thesis was developing an artificial algorithm for playing a board game. My choice of game was Abalone.
The complexity of Abalone is very similar to the complexity of chess. But this game is not that well known hence there is still a lot of unanswered question in this field.
The first part of my project consisted of the development of a software which offered the area where algorithms and humans could play against each other. To this connected a testing modul that could run multiple tests automatedly.
The second part of my project was the development of the algorithms. The most important question was what kind of heuristics should the algorithms use. Firstly I collected the characteristics from other people’s works and from my experiences that could be useful to evaluate a state of gameplay. Then with different techniques I decided which characteristics and with how much weight should I include in the heuristics.
The algorithms I created are all based on the Minimax algorithm. My goal was to create an algorithm that thinks as much ahead as possible. But because at every turn there is a lot of different possible moves for a player to choose from, it’s very expensive to think ahead too much. So I created two algorithms that doesn’t explore the whole game-tree, but leave some of the nodes unexplored.
In my results I will explain that exploring only the right nodes increased the speed and effectiveness of my algorithms greatly.