Open AccessAn Analysis of Heuristics for a Mathematically Incomplete Variant of TicTacToe
Author(s) -
F. J. Baker,
Arunava Mukhoti,
B. R. Chandavarkar
Publication year - 2021
Publication title -
aijr proceedings
Language(s) - English
Resource type - Conference proceedings
ISSN - 2582-3922
DOI - 10.21467/proceedings.114.57
Subject(s) - heuristics , computer science , heuristic , monte carlo tree search , domain (mathematical analysis) , tree (set theory) , a priori and a posteriori , mathematical optimization , game theory , monte carlo method , machine learning , artificial intelligence , mathematical economics , mathematics , mathematical analysis , philosophy , statistics , epistemology , operating system
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.