This repository contains C++ code that implements a Monte Carlo Tree Search (MCTS) algorithm for playing Tic Tac Toe.
- Implementation of MCTS algorithm
- Tic Tac Toe game logic
- Command-line interface for playing against the AI
Monte Carlo Tree Search (MCTS) is a heuristic search algorithm used for decision-making processes, particularly in game playing. It combines the precision of tree search with the generality of random sampling. The algorithm consists of four main steps:
-
Selection: Starting from the root node, select successive child nodes until a leaf node is reached. The selection is based on a policy, often the Upper Confidence Bound (UCB1).
-
Expansion: If the leaf node is not a terminal state, one or more child nodes are generated and added to the tree.
-
Simulation: A simulation (or playout) is run from the newly added node to a terminal state using a default policy, typically random moves.
-
Backpropagation: The result of the simulation is propagated back through the tree, updating the nodes' statistics.
MCTS is particularly effective for games with large state spaces and has been successfully applied to various games, including Go, Chess, and Tic Tac Toe.
Below is a visualization of the Monte Carlo Tree showing different options and their impact:
In this implementation we try to apply modern C++ language features e.g. concepts.
- C++ compiler (e.g., g++)
- CMake (optional, for building)
To build the project, you can use the following commands:
mkdir build
cd build
cmake ..
makeAfter building the project, you can run the executable:
./tic_tac_toe -X human -O ai -i 100Where the larger i, the higher the difficulty, set -d to draw intermediate mcts trees (only applicable with ai players).
Follow the on-screen instructions to play Tic Tac Toe against the AI powered by the MCTS algorithm.