This project contains random movement, minimax with alpha-beta pruning, heat mapping, and Monte-Carlo Tree Search agents for Ultimate Tic-Tac-Toe. This project uses the standard U3T ruleset defined on wikipedia. Particularly, it is important to note that after a grid has been won by a player, no moves can be played in the grid.
git clone https://github.com/Leomnz/U3T
cd U3T
wget https://raw.githubusercontent.com/aimacode/aima-python/master/games.py
wget https://raw.githubusercontent.com/aimacode/aima-python/master/games4e.pyAlternatively drop this repository into the https://github.com/aimacode/aima-python directory
This table shows the win rate for each algorithm match up (excluding draws), with blue representing a higher win rate and red representing a lower win rate. So, to see the win rate of alpha-beta pruning against MCTS you would look at the second column, third row to find that it is 0.166. In other words, alpha-beta pruning won approximately 17% of the non-draw games.
A PDF containing a full experimental discussion of the project is attached below.