# Computer Science Project - MCTS
A little game where you play against 1-3 AIplayers.
Made in the Unity game engine, the focus of this project is the implementation of a simple board game called 'Shut The Box' and the heuristic search algorithm Monte Carlo Tree Search.
MCTS algorithm is used to solve the game tree and permits to the AI to play the best move possible.
# Shut The Box rules
Here the wikipedia page of Shut The Box rules:
https://en.wikipedia.org/wiki/Shut_the_box
# Useful docs about MCTS
Useful introduction to MCTS algorithm: https://towardsdatascience.com/monte-carlo-tree-search-an-introduction-503d8c04e168
Wikipedia MCTS page: https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
Good paper about MCTS methods:
https://www.researchgate.net/publication/235985858_A_Survey_of_Monte_Carlo_Tree_Search_Methods
# Testbench
*Sum of percentages != 100% because a match could end in a draw*
### AI vs RandomPlayer (100 matches, 9 tiles, MCTS 20k iterations)
| Agent | Wins | Average score |
|:-----:|:-----:|:-----:|
| RandomPlayer | 31% | 23/45 |
| AI | 62% | 28/45 |
### AI vs RandomPlayer (200 matches, 12 tiles, MCTS 50k iterations)
| Agent | Wins | Average score |
|:-----:|:-----:|:-----:|
| RandomPlayer | 20%| 25/78 |
| AI | 77% | 36/78 |
### AI vs RandomPlayer (20 matches, 12 tiles,MCTS 500k iterations)
| Agent | Wins | Average score |
|:-----:|:-----:|:-----:|
| RandomPlayer | 11%| 23/78 |
| AI | 88% | 42/78 |
Introduction of a Strategy Player: a player who always plays the combination which involves as few tiles as possible.
### Strategy vs Random (1000 matches, 12 tiles)
| Agent | Wins | Average score |
|:-----:|:-----:|:-----:|
| RandomPlayer | 14%| 25/78 |
| StrategyPlayer | 83% | 42/78 |
### Strategy vs AI (100 matches, 12 tiles, MCTS 100k iterations)
| Agent | Wins | Average score |
|:--------------:|:-----:|:-----:|
| AI | 42% | 38/78 |
| StrategyPlayer | 57% | 42/78 |
### Strategy vs AI (50 matches, 12 tiles, MCTS 1 million iterations)
| Agent | Wins | Average score |
|:-----:|:-----:|:-----:|
| AI | 47% | 41/78 |
| StrategyPlayer | 44% | 41/78 |