Optimization Areas of the Minimax Algorithm : A study on a look-ahead AI as applied to the Fox game

Abstract: Artificial intelligence has become more prevalent during the last few years, revolutionizing the field of computer game-playing. By incorporating artificial intelligence as a computerized opponent, games can become more engaging and challenging for human players. The minimax algorithm when applied to a two-player turn-based game looks a given number of steps ahead into the future and determines which move leads to the best scenario, given that the opponent plays optimally. The algorithm can be applied to a wide range of different games, the algorithm itself is quite simple and depending on the type of game it is often hard to perform better in the game than an AI using this algorithm. One big disadvantage of the algorithm however is that it is relatively slow since the amount of possible scenarios it has to consider often grows exponentially with each turn. This thesis presents an analysis of various strategies to accelerate the performance of the minimax algorithm, with a particular focus on versions with and without alpha-beta pruning. The study further explores the performance implications of parallelization, examines how the optimal move selection rate is influenced by search depth, and assesses whether dynamic search depth offers a viable means of balancing optimal move selection rate and execution speed. The results derived from the study indicate that alpha-beta pruning is more effective with higher search depths. It also indicated that alpha-beta pruning allowed for one step deeper searches compared to the standard minimax algorithm, for almost no added computational cost. The impact of parallelization varied, proving beneficial for deeper searches in the non-pruning version but had almost no impact on the alpha-beta pruned version. The optimal move selection rate did increase with added depth, but more data is needed for conclusive results. In regards to dynamic search depth, we found it only proved effective for the standard minimax algorithm and that it is better to use alpha-beta pruning.