För att ta reda på hur väl en Multi-Agent-Systems-bot kan stå sig mot andra, icke-MAS-bottar, så har vi implementerat en bot till brädspelet Arimaa. Botten är implementerad i C++ och den kan spela mot andra bottar, eller människor, genom Arimaas officiella hemsida. Syftet har varit att skapa en fullfjädrad bot som både klarar av att spela korrekt, och att spela bra. För att ta reda på om MAS är en bra designfilosofi för Arimaa så har vi utmanat ett antal av de bottar som andra människor skapat och lagt upp på hemsidan. Alla bottarna har under tiden de legat uppe blivit rankade genom tävlingar och utmaningar och flera av dessa har tävlat om stora pengar, vilket betyder att människor har lagt mycket tid på dem. Efter ett stort antal matcher mot andra bottar så har vi kommit fram till att Arimaa är ett väldigt svårt spel att koda bottar till. Vi lyckades bara slå några av de sämsta bottarna på hemsidan men MAS visar stor potential och vi tror att man kan göra väldigt avancerade bottar med det. Jämfört med de bästa bottarna så är vår väldigt snabb och minneseffektiv. Man borde absolut experimentera mer.

Arimaa is a strategic board game for two players. It was designed with the aim that it will be hard to create a computer program that could defeat the best human players. In this thesis, we focus on the design of the static evaluation function for Arimaa. The purpose of a static evaluation function is to determine which player is leading in a given position and how significant the lead is. We have divided the problem into a few parts, which were solved separately. We paid most attention to the efficient recognition of important patterns on the board, such as goal threats. The basic element of the proposed evaluation function is mobility. For each piece, the number of steps that the piece would need to get to other places on the board is estimated. We also examined machine learning. We developed a new algorithm for learning a static evaluation function from expert games. An implementation of an Arimaa playing program, which demonstrates the proposed methods, is part of the thesis. Powered by TCPDF (www.tcpdf.org)

Agents being able to play board games such as Tic Tac Toe, Chess, Go and Arimaa has been, and still is, a major difficulty in Artificial Intelligence. For the mentioned board games, there is a certain amount of legal moves a player can do in a specific board state. Tic Tac Toe have in average around 4-5 legal moves, with a total amount of 255168 possible games. Both Chess, Go and Arimaa have an increased amount of possible legal moves to do, and an almost infinite amount of possible games, making it impossible to have complete knowledge of the outcome. This thesis work have created various Neural Networks, with the purpose of evaluating the likelihood of winning a game given a certain board state. An improved evaluation function would compensate for the inability of doing a deeper tree search in Arimaa, and the anticipation is to compete on equal skills against another well-performing agent (meijin) having one less search depth. The results shows great potential. From a mere one hundred games against meijin, the network manages to separate good from bad positions, and after another one hundred games able to beat meijin with equal search depth. It seems promising that by improving the training and by testing different sizes for the neural network that a neural network could win even with one less search depth. The huge branching factor of Arimaa makes such an improvement of the evaluation beneficial, even if the evaluation would be 10 000 times more slow.

Arimaa is a strategic board game for two players. It was designed to be simple for human players and difficult for computers. The aim of this thesis is to design and implement the program with features of the artificial intelligence, which would be able to defeat human players. The implementation was realized in the three key parts: evaluation position, generation of moves and search. The program was run on the game server and defeated many bots as well as human players.