This project is an object-oriented implementation of the Monte Carlo Tree Search algorithm in C++. Check the examples to see how to use this library for your own games.
Monte Carlo Tree Search (MCTS) is an algorithm used for decision-making in game playing. It combines the exploration of possible moves, done by random simulations, with the exploitation of the most promising moves, found by evaluating their potential outcomes.
The algorithm builds a tree structure of possible game states, where each node represents a game state, and the edges are the moves that can be made.
The algorithm iteratively performs four steps: selection, expansion, simulation, and backpropagation. It starts by selecting the most promising node in the tree, then expand it by adding a new child node representing a new game state. Then, it simulates random playouts from the new node to estimate the potential outcome of that move. Finally, it backpropagates the results of the playout to the parent nodes, updating their statistics. This process is repeated until the algorithm finds the best move to make.
This project uses CMake. To build the repository, run the following commands:
git clone https://github.com/Quentin18/mcts-cpp.git
cd mcts-cpp
cmake -S. -Bbuild
cmake --build build
Then, you can run the examples:
| Game | Executable |
|---|---|
| Connect Four | connect4 |
| Tic-tac-toe | tictactoe |
| Ultimate tic-tac-toe | uttt |
For example, to run the Tic-tac-toe game:
cd build/bin
./tictactoe
The project contains unit tests using Google Test.
You can run the tests either using ctest:
cd build
ctest
Or directly using unit_tests:
cd build/bin
./unit_tests
You can generate the documentation using doxygen:
doxygen Doxyfile