Comparative Analysis of Monte Carlo Tree Search and Alpha-Beta Pruning in Chess AI Development

Sammanfattning

This thesis explores the strengths and weaknesses of Alpha-Beta pruning (ABP ) compared to Monte Carlo tree search (MCTS), focusing on their performance as search algorithms for chess engines. It is hypothesized that MCTS, with its probabilistic approach, will achieve greater search depth and broader exploration of nodes. Conversely, ABP is expected to demonstrate superior efficiency through its pruning capabilities, reducing the number of nodes evaluated and enabling faster decision-making, albeit with potentially less search depth. Additionally, ABP also provides more complete searches by evaluating all branches of the game tree, in contrast to MCTS, which selectively skips some paths. The goal of this thesis is to develop and evaluate chess engines based on these algorithms and compare their performance across a variety of conditions. The results show that ABP is generally more effective than MCTS, particularly when advanced evaluation functions are employed. MCTS struggles to detect shallow traps in chess due to its reliance on the Upper Confidence bounds applied to Trees (UCT) algorithm in the selection phase. However, given sufficient think time, MCTS can outperform ABP , leveraging its deeper selective search capabilities. Additionally, MCTS does not require complex evaluation functions to perform strongly at a strategic level and performs with simpler heuristics, showcasing its adaptability to games with minimal prior domain knowledge. These findings highlight the trade-offs between exhaustive search and selective exploration in game-tree search algorithms. While ABP is well- suited for deterministic scenarios with complex evaluation functions, MCTS exhibits potential for broader applications, provided it is enhanced to address its limitations in detecting shallow traps.