Monte Carlo Tree Search for Gopher

Description

Gopher is a strategy game where two players compete on a grid, aiming to capture as many cells as possible. Players move in four directions (up, down, left, right) to control territory while trying to block their opponent’s moves. The goal is to capture the most cells and restrict the opponent's movement. In this project, I developed a Monte Carlo Tree Search (MCTS) strategy for the Gopher game. The algorithm was built from scratch and incorporates dynamic simulations, filtering of non-promising moves, and reusing evaluations of previously explored positions.

The game features :

• Dynamic Simulations: The number of simulations increases as the game progresses to explore more deeply in later stages.
• Move Filtering: Only "promising" moves are explored to reduce unnecessary simulations and focus on potential winning strategies.
• Reusing Previous Evaluations: A dictionary stores cumulative scores and the number of simulations, avoiding recalculating known positions.
• Early Simulation Termination: Simulations stop if a clearly bad move is detected, saving computation time.
• Upper Confidence Bound (UCT) Formula: The algorithm balances exploration and exploitation using the UCT formula with an exploration coefficient of sqrt(2).

Results

The algorithm achieved 2 wins and 2 losses in a tournament. Key areas for improvement include time management, opening strategies, and better resource allocation in simulations.

Future Improvements

• Optimize for different time constraints (e.g., 10s, 1min).
• Refine the opening strategy to avoid quick defeats.
• Implement logarithmic growth for simulations to enhance performance.

Resources

Course materials from IA02 and Gopher Ludii AI were used during development.