Minimax vs. Monte Carlo : A Comparative Case Study on the Use of Minimax with Alpha-Beta Pruning versus Monte Carlo Tree Search as Decision-Making Algorithms in an Android Chess Application

Sammanfattning

This thesis presents a comparative analysis of two prominent decision-making algorithms: Minimax with Alpha-Beta Pruning and Monte Carlo Tree Search (MCTS), applied within an Android-based chess application. The research stems from the challenge of improving Artificial Intelligence(AI) performance and game play, particularly in resource-constrained environments such as a mobile device. The study explores the area of balancing computational efficiency and strategic depth. Minimax with Alpha-Beta pruning is traditionally favored for its exhaustive search approach, which provides a methodical and tactical advantage in game play. However, its deterministic nature can limit game play diversity and adaptability. These are traits that MCTS could enhance due to its probabilistic and explorative approach. The study methodically compared these algorithms by implementing them within a deployed chess application (Chess Rumble) to then evaluate them based on several performance metrics including decision time, win and draw rates, and strategic diversity. The experiments conducted revealed that while Minimax performs efficiently under stringent computational limits, MCTS offers a more dynamic and engaging game play experience as it scales with increased computational resources. The findings indicate that both algorithms have unique strengths without a clear overall winner in all scenarios. This highlights a potential for their complementary application depending on specific needs. MCTS excels in creating a dynamic and unpredictable gaming experience, pointing to valuable future applications in AI-driven games and other interactive environments. This study provides valuable insights in comparing the two algorithms in performance and strategic diversity. It also offers insights into the practical applications of AI in game development, particularly for mobile platforms.