← The six schools

Divination · data and game AI

UTTT

A C++ AI for Ultimate Tic-Tac-Toe, written as a pair to beat our teacher's engine. Best result: 72 wins, 17 losses and 11 draws over 100 games against MEDIUM_2.

Where we started

It was the first time we wrote a program that decides on its own. We came in knowing very little game theory or search algorithms, and learned them while building. Seen from there, 72 % against the medium engine is a result I am glad of.

The game

Nine small grids inside a big one. Where you play inside a small grid sends your opponent to the matching small grid. Win three small grids in a row to win the game. Every move is two decisions at once: the square you take, and where you send the other player.

The engine

  • Minimax with alpha-beta pruning and iterative deepening.
  • A transposition table with Zobrist hashing.
  • Move ordering with killer moves and a history table.
  • A positional evaluation, and an opening book that fills itself from tournament games.
  • About 1,800 lines of C++, plugged into the teacher's engine through a fixed interface.

How it got to 72 %

The first version won between 0 and 20 % against MEDIUM_2, at about 350 ms per move. Going to depth 14 with a 10-second budget and adding the opening book brought it to 72 % over 100 games, with an average depth of 11.3 and 319 moves served by the book.

What I learned

  • Samples of 10 games are noise. Only 100-game runs told us anything.
  • Debug and Release builds play like two different engines; always measure with -O3.
  • Mate scores stored in the table must be corrected by distance, or the engine believes nonsense.
  • An opening book goes wrong as soon as the evaluation changes.
  • Not done: quiescence search, multi-threading, Monte Carlo tree search, which is what wins at this game.
How the engine is organised, redrawn from the class diagram in the repository.
How the engine is organised, redrawn from the class diagram in the repository.
The 100-game run behind the 72 %, drawn from the log kept in the repository (logs/ai_log_20260503_173054.csv).
The 100-game run behind the 72 %, drawn from the log kept in the repository (logs/ai_log_20260503_173054.csv).