This Java-driven Ultimate Tic-Tac-Toe game was a fun exercise in 2D graphics, object-oriented game design, and AI implementation. The motivation for this project came from a fun class I took in Spring 2019, Comp Sci 270: Intro to Artificial Intelligence. One unit of that class was focused on AI for two-player, zero-sum games, like checkers, chess, or Go. I'd always loved the game of Ultimate Tic-Tac-Toe (it's like tic-tac-toe, but recursive: every board contains a second, smaller board. The object of the game is to win three small boards in a row; it makes for a much more interesting and strategic game!), so I thought I'd apply what I'd learned in that class to it!

I started by designing the game itself. My object-oriented implementation involves a series of 'nested' classes: for example, the large, main board (the MainBoard class) contains an array of nine smaller, sub-boards (the CellBoard class). The sub-boards, in turn, contain an array of nine cells (the Cell class). Managing these classes and their complex interactions taught me a lot about variable scope and management, and improved my understanding of object-oriented design. You can see the result of this work below: I successfully constructed a working, two-player game!

My next goal was to add the one-player option: playing against an AI. After reading several research papers on the performance of various AI algorithms on this game, I decided that minimax search with alpha-beta pruning was the way to go. Minimax is an algorithm for two-player, zero-sum games that recursively searches through all possible game states, up to a limited depth, to find the optimal move for a player to make. Alpha-beta pruning is an optimization on this algorithm that limits the search space by ruling out, or 'pruning', moves that are absolutely worse or will never be made.

Implementing this algorithm was a challenge, but a fun one! It took many hours of troubleshooting to work out all of the bugs, but it was well worth it for the satisfying conclusion. Now, I can practice my Ultimate Tic-Tac-Toe skills against a very impressive AI opponent.

You can try it out too! Take a look at the rules here and download the standalone .jar executable below! Note that it requires JDK 7+ to run, but has no other dependencies. Have fun!