This GitHub Organization contains all repositories that were made by me in the course of my bachelor thesis/project. The task was to implement the game Carcassonne in the existing SGE environment (https://gitlab.com/StrategyGameEngine/strategy-game-engine) and implement a heuristic-guided MCTS agent for that. The twist being that the agents were not playing against each other but collaborating. The goal of both agents is to maximize the sum of the points of both players.
- Carcassonne-Environment
- AgentNaiveMCTS
- AgentAdaptiveV5
- AgentHeuristicMCTS
- Abstract-Agent
- EasyBitPacking
- VerificationHelper
In order to evaluate the performance of the resulting agents, I performed a tournament where the agents played with each other. In order to evaluate their adaptiveness, a random agent was also introduced into the mix.
I implemented 7 different agents. Each agent had a computational budget of 10 seconds and each matchup was played 3 times. The results showed that all agents collaborated and that the MCTS approach was indeed working. Unsurprisingly, the ensemble methods performed stronger compared to their non-ensemble counterparts.
The most surprising finding was that the naive approach seems to be quite robust against all kinds of opponents. All approaches that tried to do better than the AgentNaiveHeuristicEnsemble ultimately failed. AgentAdaptiveV5 was the latest and newest approach, but it is in general worse than the AgentNaiveHeuristicEnsemble.
The performance results were that the AgentNaive performs 55,000 MCTS iterations in 10 seconds, where each iteration performs 5 simulations. The heuristic agents get to do far fewer iterations due to the expensive calculation of the heuristic.
| Agent | AgentAdaptiveV5 | AgentGreedyHeuristic | AgentNaive | AgentNaiveEnsemble | AgentNaiveEnsembleNormalized | AgentNaiveHeuristic | AgentNaiveHeuristicEnsemble | RandomAgent | row avg |
|---|---|---|---|---|---|---|---|---|---|
| AgentAdaptiveV5 | 346,00 | 297,33 | 321,33 | 320,00 | 304,33 | 314,00 | 327,67 | 181,33 | 301,50 |
| AgentGreedyHeuristic | 296,33 | 224,00 | 224,00 | 255,67 | 274,00 | 315,67 | 319,33 | 137,67 | 255,83 |
| AgentNaive | 306,33 | 244,33 | 247,67 | 262,33 | 270,67 | 284,00 | 301,33 | 167,00 | 260,46 |
| AgentNaiveEnsemble | 313,67 | 290,67 | 263,00 | 286,33 | 279,33 | 293,67 | 322,67 | 160,33 | 276,21 |
| AgentNaiveEnsembleNormalized | 311,67 | 235,00 | 280,33 | 191,33 | 303,67 | 313,33 | 360,33 | 155,33 | 268,88 |
| AgentNaiveHeuristic | 329,00 | 332,67 | 307,33 | 333,00 | 346,33 | 321,33 | 334,33 | 138,67 | 305,33 |
| AgentNaiveHeuristicEnsemble | 356,67 | 322,67 | 334,67 | 118,33 | 341,00 | 330,00 | 378,33 | 184,33 | 295,75 |
| RandomAgent | 175,00 | 150,00 | 156,00 | 164,00 | 117,00 | 154,00 | 188,67 | 44,33 | 143,63 |
| col avg | 304,33 | 262,08 | 266,79 | 241,37 | 279,54 | 290,75 | 316,58 | 146,13 |
| rank | agent | self avg |
|---|---|---|
| 1 | AgentNaiveHeuristicEnsemble | 378,33 |
| 2 | AgentAdaptiveV5 | 346,00 |
| 3 | AgentNaiveHeuristic | 321,33 |
| 4 | AgentNaiveEnsembleNormalized | 303,67 |
| 5 | AgentNaiveEnsemble | 286,33 |
| 6 | AgentNaive | 247,67 |
| 7 | AgentGreedyHeuristic | 224,00 |
| 8 | RandomAgent | 44,33 |
| rank | agent | overall avg |
|---|---|---|
| 1 | AgentNaiveHeuristicEnsemble | 306,17 |
| 2 | AgentAdaptiveV5 | 302,92 |
| 3 | AgentNaiveHeuristic | 298,04 |
| 4 | AgentNaiveEnsembleNormalized | 274,21 |
| 5 | AgentNaive | 263,63 |
| 6 | AgentGreedyHeuristic | 258,96 |
| 7 | AgentNaiveEnsemble | 258,79 |
| 8 | RandomAgent | 144,88 |
Iterations in 10 seconds (Ensemble sum of all subagents)
| Agent | Iterations | Rollouts/Iter |
|---|---|---|
| AgentNaive | 44.222 | 5 |
| AgentNaiveEnsemble | 33.351 | 5 |
| AgentNaiveHeuristic | 1.483 | 5 |
| AgentNaiveHeuristicEnsemble | 1.467 | 10 |
| AgentNaiveEnsembleNormalized | 1.454 | 100 |
| AgentAdaptiveV5 | 836 | 20 |
