Project Overview

Computer vision has often taken a backseat role in games like tic-tac-toe, in which it is used primarily for object detection, whereas a separate minimax algorithm performs the actual evaluation of a given game state. In this study, we implemented three different deep learning models, including a convolutional neural network (CNN) built from scratch and two state-of-the-art pre-trained models (ResNet and EfficientNet) that we transferred to our problem using network surgery. We generated all of our data from scratch, first generating all 5,478 valid tic-tac-toe states and then converting each of those states into a 28x28 image of a tic-tac-toe board, augmented with random shifts based on a distribution and heatmap, as well as random sampling from a set of pre-drawn X’s, O’s, and lines. We also generated all of the labels using a custom-made scoring algorithm. Our goal was to solve the following three-class classification problem: to predict whether X is winning, O is winning, or the position is tied in any given tic-tac-toe state. After training each of our models for 100 epochs, using a validation set to prevent overfitting, our CNN model from scratch achieved an accuracy of 93.87% on the test set; ResNet achieved an accuracy of 96.94%; and EfficientNet achieved an accuracy of 81.97%. The strong predictive performance of our models gives us some assurance that deep learning models can, indeed, be used to evaluate tic-tac-toe boards, even in the absence of a minimax algorithm. Future research should consider experimenting with larger board sizes, introducing even more random noise, and inducing a turn mechanic (with which our models struggled most). This project was my and my partner's final project for Professor Peter Belhumeur's Deep Learning for Computer Vision (COMS W4995) course at Columbia University.