Tic-Tac-Toe & Ultimate Tic-Tac-Toe — Game Tree Search

A collection of three C programs that explore AI search algorithms applied to Tic-Tac-Toe and Ultimate Tic-Tac-Toe (Super Morpion). The project implements Minimax, Negamax, and Alpha-Beta pruning to compute optimal moves and visualize decision trees using Graphviz.

Motivation

This project was built to study and compare classic adversarial search techniques on increasingly complex game boards:

• Tic-Tac-Toe (3x3) — a fully solvable game, ideal for visualizing the complete Minimax tree.
• Ultimate Tic-Tac-Toe (9x9) — an exponentially larger search space that requires pruning heuristics and time management to play competitively.

Key Results

Decision Tree Visualization (tttree)

The tttree program generates a full Minimax decision tree from any board position. Below is an example starting from an empty board (depth-limited to 4 plies):

Each node shows the board state; green = X to move, red = O to move. Edge labels indicate the (row, col) of the move.

Ultimate Tic-Tac-Toe Board (sm-refresh)

The sm-refresh program renders the 9x9 Ultimate board as a Graphviz image, updated live during play:

Architecture

tictactoe-search-tree-algorithm/
├── ttree/              # Tic-Tac-Toe decision tree generator
│   ├── main.c          # CLI entry point (parses FEN, generates DOT)
│   ├── morpion.c/h     # Board structs, win detection, DOT export
│   └── utils.c/h       # Minimax, Negamax, FEN parsing
│
├── sm-bot/             # Ultimate Tic-Tac-Toe competition bot
│   ├── main.c          # CLI entry point (FEN in → best move out)
│   ├── morpion.c/h     # Board logic, move execution, display
│   └── utils.c/h       # Negamax + alpha-beta, heuristic evaluation,
│                        # adaptive depth from time budget
│
├── sm-refresh/         # Interactive Ultimate Tic-Tac-Toe (human vs AI)
│   ├── main.c          # Game loop (AI=x, Human=o)
│   ├── morpion.c/h     # Board logic, move execution, display
│   ├── utils.c/h       # Minimax search, heuristic evaluation
│   └── refresh.html    # Live-reload page for board PNG
│
├── Makefile            # Top-level build (builds all three programs)
├── LICENSE             # MIT License
└── README.md

Installation & Usage

Prerequisites

Tool	Purpose
GCC	C compiler
Make	Build automation
Graphviz (optional)	Renders .dot files to PNG images

Build

# Build all three programs
make

# Or build individually
make ttree
make sm-bot
make sm-refresh

Run

1. tttree — Decision Tree Generator

Generates a Minimax decision tree in Graphviz DOT format from a FEN-like board string.

cd ttree
./tttree "9 x" > g1.dot        # Empty board, X to move
dot -Tpng -o g1.png g1.dot     # Render to PNG

FEN format: digits = consecutive empty cells, x/o = pieces, space then side to move. Example: "xo7 x" = X at (0,0), O at (0,1), 7 empty cells, X to move.

2. sm-refresh — Interactive Game

Play Ultimate Tic-Tac-Toe against the AI in the terminal with live Graphviz board rendering.

cd sm-refresh
./sm_refresh.exe 5              # Search depth = 5

• Set DEBUG=1 for verbose AI output.
• Set SMPATH=/path/to/dir to control where the PNG is written.
• Open refresh.html in a browser to see the board update live.

3. sm-bot — Competition Bot

Compute the best move for a given board state within a time budget (designed for automated tournaments).

cd sm-bot
./sm_bot.exe "6xoxOOOX2xo1ox1oXx2xo4oox4ox 84 o" 300
# Outputs a two-digit move: (morpion_index)(cell_index)

Clean

make clean

Technical Details

Component	Algorithm	Search Strategy	Output
tttree	Minimax / Negamax	Full tree (depth-limited)	DOT graph to PNG
sm-bot	Negamax + Alpha-Beta	Adaptive depth (time-managed)	Best move (stdout)
sm-refresh	Minimax	Fixed depth	Interactive terminal + DOT/PNG

Board encoding: A custom FEN-like notation compresses the 81-cell Ultimate board into a compact string. Won sub-boards are represented as uppercase (X/O), active cells as lowercase (x/o), and consecutive empty cells as digits.

Heuristic evaluation (mcore/score): Scores are computed by analyzing all eight winning triplets per sub-board, weighting two-in-a-row threats, center control, and the macro-board position.

Adaptive depth (sm-bot): The bot dynamically adjusts search depth between turns based on the elapsed time of the previous move relative to the remaining time budget, stored persistently in depth.txt.

References

• Russell, S. & Norvig, P. — Artificial Intelligence: A Modern Approach (Minimax, Alpha-Beta pruning)
• Ultimate Tic-Tac-Toe rules

Author

AstyanM — GitHub

License

This project is licensed under the MIT License — see the LICENSE file for details.