Ultimate Tic-Tac-Toe AI

Ultimate Tic-Tac-Toe AI is an open-source Haskell engine that plays competitive Ultimate Tic-Tac-Toe. It combines a fast immutable game-state representation with iterative deepening, alpha-beta pruning, and a custom evaluation function to deliver strong play under tight time budgets.

Features

• Time-aware iterative deepening negamax search with alpha-beta pruning.
• Static ordering and principal variation promotion to reduce branching.
• Heuristic evaluation that tracks macro control, mini-board pressure, and positional features (center/corner/edge occupancy, mobility, forced wins).
• Pure immutable state transitions backed by compact bitsets for efficient move generation and terminal detection.
• Scenario tests, smoke scripts, and match-runner benchmarks to validate behaviour and track performance.

Getting Started

Requirements

• GHC 9.x (tested with GHC 9.4+)
• array and random packages (bundled with GHC's base distribution)
• macOS or Linux shell environment

Build the Engine

mkdir -p build
ghc -package array -outputdir build -hidir build UltimateTicTacToeAI.hs -o build/utt-ai

The resulting executable exposes the think entry point described in UltimateTicTacToeAI.hs. You can also load the module directly in GHCI:

ghci -package array UltimateTicTacToeAI.hs

Run Scenario Tests

mkdir -p build
ghc -package array -outputdir build -hidir build tests/ScenarioTests.hs -o build/scenario-tests
./build/scenario-tests

Benchmark Against Baselines

mkdir -p build
ghc -package array -package random -outputdir build -hidir build benchmarks/MatchRunner.hs -o build/match-runner
./build/match-runner random 25 3   # or use 'greedy'

Extended benchmark summaries live in docs/benchmarks.md.

Project Layout

• UltimateTicTacToe.hs – core game rules, board representation, helper types.
• UltimateTicTacToeAI.hs – search implementation, heuristics, public API.
• tests/ScenarioTests.hs – deterministic regression scenarios.
• benchmarks/MatchRunner.hs – reproducible match-runner harness.
• smoke.md – GHCI-driven smoke checklist.
• docs/ – design notes, heuristics overview, benchmark results.
• images/ – diagrams illustrating macro and mini-board numbering.

Documentation

• docs/README.md outlines the available documentation set, heuristics, and regression workflows.
• docs/design.md details architectural choices and open research threads.
• docs/benchmarks.md records empirical performance runs.
• smoke.md provides an interactive sanity-check script.

Contributing

Contributions are welcome! Feel free to open issues or pull requests for bug fixes, new heuristics, alternative search strategies, or tooling improvements. See docs/design.md and the "Future Work" sections throughout the docs for ideas.

Originally prototyped as a Haskell coursework project, the engine has since grown into an open-source effort—community contributions are encouraged.

License

This project is distributed under the MIT License. See LICENSE for details.

Game Primer

Ultimate Tic-Tac-Toe is played on nine 3×3 tic-tac-toe boards arranged in a macro 3×3 grid. Each field of a mini-board is either empty, marked X, or marked O.

Within every mini-board, fields are numbered 1 through 9 from top-left to bottom-right.

Gameplay starts with an empty macro board. Players alternate turns, with X moving first. A move selects a target mini-board b (1 ≤ b ≤ 9) and an empty field f (1 ≤ f ≤ 9) inside that board. Completing three in a row inside a mini-board captures it for that player.

Except on the opening move, the opponent's previous field choice dictates the mini-board for the next move: if your opponent plays field 3, you must respond inside mini-board 3. If that board is already captured or full, you may play on any open board.

The game ends when a player controls three mini-boards in a row across the macro grid, or when no legal moves remain (resulting in a draw).