Introduction

When I had a programming exercise at the university a few weeks ago, the task assignments where not as clear as they had to be and I had a lot of free time while I was in the computer room. It was then that I discovered gataxx, the ataxx game for gnome. After a few tries I was able to win of the computer, even with the highest level. A friend of me suggested that I looked into a better algorithm for ataxx, so I did and this document is the result of that.

First I will briefly describe what kind of game ataxx is, and what kind of variations there exist. Secondly I will explain some heuristics, which are important for the algorithms that I will discuss next. The state space of ataxx is big and I will talk about how big it is and about some optimizations after this. Then I refer to some implementations of the game and how they handled the computer player. Finally I will conclude with a recommendation that will improve the computer player in gataxx.

Gataxx
Gataxx, where white is me and black is the computer player.