Ultimate Tic Tac Toe
Ultimate Tic Tac Toe is a desktop game I wrote in Java and JavaFX, and the game AI behind it is a Monte Carlo Tree Search engine that can optionally be steered by neural networks I trained myself. It started as a way to play a game I like against something better than a random opponent, and turned into the biggest software project I have built: a full game engine, a multithreaded search, a training pipeline for two networks, and installers for Windows and Linux.
The game
Ultimate Tic Tac Toe is played on a 3x3 grid of 3x3 boards. Winning a small board claims that cell of the big board, and the cell you play in dictates which small board your opponent has to play in next. Win three small boards in a row and you win the game. That one rule, that your move chooses your opponent's board, is what turns a solved children's game into something with real strategy: every move is a trade between the square you want and the board you are handing over.
How the computer opponent works
The engine is a Monte Carlo Tree Search. Rather than evaluating every position via brute force, MCTS repeats a cheap four-step loop as many times as possible, letting the statistics it collects decide the move. Each iteration selects a promising path down the tree, expands a new node at the bottom of it, evaluates that position, and backpropagates the result up to the root. When time runs out, the engine plays the move leading to the most-visited child of the root.
The algorithmic selection uses the UCB1 formula to balance exploring new moves with further exploring good ones, and evaluation is a random playout to the end of the game. However, mimicing Google's Alpha Go, neural networks can be substituted into those two specific phases. A policy network replaces UCB1 selection: it produces a probability distribution over all 81 cells, and a move is sampled from the result. A value network replaces the random playout with a single forward pass estimating who is winning. Both networks are independently optional and both fall back to the classical behaviour if a network is missing or fails, which is what lets one engine class cover two genuinely different search strategies. The AI part of this is certainly a work in progress and there are bugs to work out, but it is a functioning prototype.
Optimization
Search quality comes down to how many iterations fit in the budget, so a lot of the work went into throughput. The search runs many worker threads against a single shared tree, so every thread's work contributes to the same statistics instead of averaging several weaker independent searches. Work is handed out in batches while an interrupt check after every single iteration keeps the stop button instant.
Locking is graded by how deep in the hot path it sits: per-node locks where threads actually collide structurally, and completely lock-free accumulation on the walk back up to the root, on the reasoning that MCTS statistics are already noisy estimates and locking every ancestor on every iteration would serialize the threads exactly where they overlap most.
The other thing that made deep search possible was memory. Storing a full board object graph at every node made this thing suck up sooo much memory that i had to implement a compact BitSet encoding and decode it on demand. It is a deliberate memory-for-CPU trade, and it is the difference between a tree that fits in RAM at millions of nodes and one that does not.
Demo Video
A walkthrough of the app: playing a game, configuring the two player slots, and watching the engine think.
How the Search Engine Works
A diagram of the engine: the four phases of one iteration on the left, the asymmetric search tree in the middle with the current selection path highlighted, the classical and neural-guided modes on the right with arrows landing on the two phases they substitute into, and the worker threads feeding the one shared tree along the bottom.
Try It Yourself
Installers for version 1.0.0. Each one is self-contained and bundles a Java runtime, so you do not need to install Java first.