Informed Monte Carlo tree search for board games

Developing artificial intelligence (AI) agents for adversarial game-playing using search-based methods presents the challenge of creating a robust utility function, which demands significant effort and specialized knowledge. Conversely, hastily devised simple utility functions often produce unsatisfactory outcomes. Monte Carlo Tree Search (MCTS) has emerged as a modern approach that avoids the need for such a strong utility function. Nevertheless, MCTS relies on a substantial number of game simulations to deliver accurate results, incurring notable computational expenses. This study introduces an inventive hybrid approach that leverages MCTS's strengths while seamlessly integrating a modified Upper Confidence Bound for Trees (UCB1) algorithm. This hybridization enhances MCTS's ability to exploit opportunities by including a basic utility function, reducing its reliance on a complex utility function. We conducted a series of experiments, applying this approach to classic board games like Tic-Tac-Toe, Mangala, and English Checkers. These experiments were compared to traditional Minimax and Alpha-Beta Pruning algorithms, along with the pure MCTS method.