MCTS Game Engine

A Monte Carlo Tree Search engine, applied to tic-tac-toe. The core tree search logic is decoupled from game mechanics, with simulation rollouts and heuristics implemented for board play.

Developed in collaboration with Elvina Fahlgren.

Project Structure

alpha-toe/
├── config/
│   └── example.config.json   # experiment parameters
├── docs/                     # project report
├── src/
│   ├── board.py              # Tic-Tac-Toe game state
│   ├── mcts.py               # MCTS engine
│   ├── rollout_strategies.py # simulation policies
│   └── run.py                # experiment runner
├── requirements.txt
└── README.md

How MCTS Works

Monte Carlo Tree Search repeats four phases until the compute budget is exhausted.

1. Selection

Starting from the root, the tree is traversed by repeatedly selecting the child with the highest UCB1 score:

$$\text{UCB1}(v) = \frac{Q(v)}{N(v)} + C \cdot \sqrt{\frac{\ln N(\text{parent}(v))}{N(v)}}$$

Symbol	Meaning
$Q(v)$	Cumulative reward at node $v$
$N(v)$	Visit count at node $v$
$C$	Exploration constant (default $\sqrt{2}$)

The first term exploits high-value nodes; the second explores less-visited ones.

2. Expansion

When a node is not fully expanded (i.e. some legal moves have not yet been tried), one untried move is sampled uniformly at random and added to the tree as a new child node.

3. Simulation (Rollout)

A game is played out from the newly expanded node to a terminal state. Two policies are available:

• heuristic: Prioritises winning moves, then blocking opponent wins, then center (on odd boards); falls back to random.
• random: Selects actions uniformly at random.

4. Backpropagation

The terminal reward propagates back through the tree. Each ancestor's visit count $N$ and cumulative reward $Q$ are updated. The reward sign alternates at each level to reflect the zero-sum turn structure.

Move Selection

After the budget is exhausted the engine returns the robust child: the root's child with the highest visit count $N$. This is statistically more reliable than selecting by highest mean reward alone.

---

Game State Interface

The core MCTS traversal in src/mcts.py interacts with game state through five methods:

class MyGame:
    def available_moves(self) -> list: ...
    def make_move(self, move) -> None:  ...
    def clone(self) -> "MyGame":        ...
    def game_over(self) -> bool:        ...
    def get_winner(self):               ...  # returns player id or None

The bundled rollout policies (heuristic_rollout and random_rollout in src/rollout_strategies.py) are specific to Tic-Tac-Toe: they evaluate rewards from player 'X''s perspective and reference player IDs 'X' and 'O'. The heuristic policy also queries state.current_player, state.is_win(player), and calculates the center cell via (state.size * state.size) // 2 (designed for 3x3 boards). Applying the engine to a new game requires providing game-appropriate rollout logic.

---

Installation

pip install -r requirements.txt

---

Running Experiments

Copy the example config and adjust as needed:

cp config/example.config.json config/config.json
# edit config/config.json
python src/run.py

You can also pass a config path explicitly:

python src/run.py config/example.config.json

Configuration Reference

Key	Type	Description
board_size	int	Board dimension (3 for 3x3)
mcts_iterations	int	MCTS simulations per move
player_type	string	"mcts" or "random" for X
rollout_policy	string	"heuristic" or "random" for X
selection_policy	string	"uct", "greedy", or "epsilon_greedy" for X
opponent_type	string	"mcts" or "random" for O
opponent_rollout_policy	string	Rollout policy for O
opponent_selection_policy	string	Selection policy for O
exploration_constant	float	UCB1 exploration constant $C$
num_games	int	Number of games to run
verbose	bool	Print board and move trace