An Analysis of Heuristics for a Mathematically Incomplete Variant of TicTacToe

We attempt to produce a game-winning heuristic for the mathematically incomplete game Ultimate Tic Tac Toe (UTT). There are several game AI that use Monte Carlo Tree Search to decide moves, however, heuristics offer a faster and computationally cheaper alternative. The mathematical analysis of UTT has not been actively pursued, so we attempt to prove a posteriori. We have decided on a few strategies for playing, and assign different strategies to each player. We play several automated games of UTT, and statistically analyse which games end quickest, and use that data to find optimal strategies for playing. This can be used to produce game heuristics for more complicated games, and produce insight about strategies. The first objective is to specify a framework that can compare heuristics for UTT, and decide an optimal strategy for both players. The second objective is to test the framework with a large amount of data, and produce demonstrable results for UTT. Lastly, to aid further research in this topic, we release our dataset into the public domain.