An Analysis of Heuristics for a Mathematically Incomplete Variant of TicTacToe

Authors

Feyaz Baker
Department of Computer Science and Engineering National Institute of Technology Karnataka Surathkal, Mangalore, India
Arunava Mukhoti
Department of Computer Science and Engineering National Institute of Technology Karnataka Surathkal, Mangalore, India
B. R. Chandavarkar
Department of Computer Science and Engineering National Institute of Technology Karnataka Surathkal, Mangalore, India

Synopsis

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.

WREC21
Published
September 22, 2021
Online ISSN
2582-3922