Minimax Based Kalaha AI

Abstract: To construct an algorithm which does well in a board game, one must take into account the time spent on each move and the ability to evaluate the state of the board. There are multiple ways to handle these issues, but only a few are covered in this analysis. AIs using the algorithms minimax, minimax with alpha-beta pruning and minimax with knowledge-based alpha-beta pruning are being compared when playing Kalaha with a 30 second time limit per move. Each algorithm is in addition paired up with two different methods of evaluating the games state. The first one only compares the amount of counters in each players store, while the second, knowledge-based method, extends this with an evaluation of the counters in play. A tournament was held between the AIs where each match-up played twelve games against each other. The regular minimax algorithm is appearing to be inferior to the improved variations. The knowledge-based alpha-beta pruning is unexpectedly unsuccessful in outperforming the regular alpha-beta pruning and a discussion covers possible errors with the implementation and possible improvements. The knowledge-based evaluation method is appearing to be slightly more successful than the simple variant, but a discussion questions the real usefulness of it when paired with more advanced search algorithms than the ones covered in this study.