Building a perfect tic-tac-toe variant AI: exact solver plus Q-learning

In TekTacTok each player has only three pieces. After placing all three you move one of your pieces to an empty square instead of adding a new one. The game continues until someone makes a line, and that simple rule creates a neat problem: play can go on forever.

First: this is not an LLM

The AI in TekTacTok is not a large language model. It neither reads nor writes text. It combines an exact mathematical solver and a tabular Q-learning model trained by playing against itself.

Part one: the exact solver

The game is small. Accounting for board symmetry (rotations and reflections) there are about 43,390 distinct reachable states (about 347 thousand raw states), and all of them can be solved in advance as win, loss or draw (infinite play counts as a draw). The method is retrograde analysis: start from terminal states and propagate values backwards. The resulting table says, for each state, the outcome and the number of moves to it. When winning, pick the fastest; when losing is unavoidable, the slowest.

With the default rules the first player wins with correct play, so as the second player against the "perfect" AI you cannot win.

Part two: Q-learning with self-play

When several moves are equally good, which to pick? A Q-learning model, a state-action value table trained through self-play and a curriculum of opponents, breaks ties. The solver guarantees no mistakes; the model adds taste between correct moves.

How good is it?

In our evaluation the learned model scored 200 wins and 0 losses in 200 games against a random player. Honest caveat: the same model without the solver made 3 non-optimal moves in about 690 decisions against random play. Q-learning alone is nearly perfect, not perfect, which is why the solver stays.

In "easy" mode the AI plays a random move 60% of the time so people can win.

Play the demo; the trained model and full source can be downloaded from the same page.