This repo provides an implementation for MCTS algorithm. We provide a solid interface for other perfect-information games too. Although, we believe that for the rollout, domain-specific heuristics could be more useful.
Change the logger level in main.py to DEBUG so that you learn more about how the algorithm works.
MCTS came into prominence after DeepMind's AlphaGo utilized it to beat Lee Sedol, Go's world champion at the time.
main.py plays a game of tic-tac-toe between an MCTS player (P1) and a Minimax player (P2).
Each MCTS move runs the four classic phases for a configurable number of simulations:
- Selection — walk down the tree picking the child with the highest UCT value
win_ratio + c * sqrt(ln(parent_visits) / child_visits), withc = sqrt(2). - Expansion — add one untried move as a new child node.
- Rollout — play the game out with a lightweight heuristic (take a winning move, otherwise block the opponent's winning move, otherwise move randomly).
- Backpropagation — propagate the rollout result back up to the root.
The final move is chosen greedily (c = 0, exploitation only).
Requires Python 3.10+ and numpy.
pip install -r requirements.txt
python main.py # play MCTS (P1) vs Minimax (P2)
python -m unittest tests # run the testsWith perfect play tic-tac-toe is a draw; at 100 simulations per move MCTS usually
draws Minimax and occasionally slips. Bump simulation_count in main.py to make it stronger.
- MCTS wikipedia page
- University of Strathclyde's John Levine's video tutorial
- Stanford's Emma Brunskill on MCTS
- Minimax wikipedia page
- This repo was influenced by int8 mcts
- Add mypy to the build pipeline
- Add Connect 4 and other simple games
- Add NNs: CNNs and RESNET rather than the rollout strategy
- Create a chess-playing api executing this code on AWS Lambda or Azure Functions