Hex Board Game AI
Monte Carlo Tree Search Agent for the Hex Strategy Game
Built for the University of Manchester AI module. Hex is a two-player connection game on an 11×11 rhombus grid where the first player to form an unbroken chain across the board wins. The challenge is that Hex has no draws and is PSPACE-complete, making brute-force search infeasible.
Classical minimax search is impractical for Hex due to the enormous branching factor and absence of a reliable heuristic evaluation function for intermediate positions.
Implemented Monte Carlo Tree Search (MCTS) with a tuned exploration constant to balance exploration and exploitation within a fixed time budget per move. Adjusted simulation rollout policy and tree expansion strategy iteratively. Used virtual connections to guide rollout bias toward promising bridge formations.
Submitted a working MCTS agent to the COMP34111 tournament, competing correctly against all other student groups within the fixed time budget per move. A solid first encounter with adversarial tree search in a provably hard combinatorial game.
