Tic-Tac-Toe AI - Sander Heyndrickx

Zero to Superhuman: project 1

What does it take to go from zero to superhuman? That's the question I explore in this video series on Youtube, documenting my journey learning to build AI systems that can outperform humans. For the first episode, I chose Tic-Tac-Toe as the perfect sandbox—simple enough to understand, yet complex enough to challenge us.

The goal was to build an unbeatable bot for the classic 3×3 game that could also scale to larger board sizes with different win conditions. The journey took me through multiple AI paradigms, from simple rule-based expert systems to sophisticated algorithms like minimax with alpha-beta pruning and Monte Carlo Tree Search.

The video walks through the entire development process, from implementing the basic game interface to optimizing advanced algorithms for computational efficiency. You'll see how each AI system performs, their strengths and limitations, and how they compare when battling against each other on increasingly challenging board configurations. Sit back and enjoy the video!

Each algorithm demonstrates different approaches to artificial intelligence: expert systems showcase classical rule-based AI from the 1960s-70s, minimax reveals perfect game tree search with mathematical guarantees, while Monte Carlo Tree Search represents modern probabilistic methods that can handle games too complex for traditional approaches.

Play yourself

Test your skills against different AI opponents, ranging from basic random moves to advanced Monte Carlo Tree Search. Customize the board size and winning conditions to create your ideal challenge. Curious how each AI works? Watch the video above for an in-depth explanation or check the section below for a quick overview.

Player X

Player O

Board Size

Win Length

Player X's turn

X: 0

O: 0

The AI algorithms

This project showcases a progression of AI techniques for playing Tic-Tac-Toe, from simple heuristics to sophisticated search algorithms. Each bot demonstrates different concepts in game AI development.

Random Bot

Selects moves randomly from available positions. Uses Math.random() to pick any empty cell with equal probability. Serves as a baseline - any intelligent strategy should easily defeat this approach.

Rule-Based Bot

Implements a hierarchy of strategic rules: (1) Win immediately if possible, (2) Block opponent's winning move, (3) Take center position, (4) Take corner positions, (5) Take any remaining position. Demonstrates classical heuristic-based AI.

Minimax V0 (Basic)

Pure minimax algorithm that recursively explores the entire game tree up to a fixed depth. Assumes both players play optimally and chooses moves that maximize the bot's minimum guaranteed outcome. Limited by exponential time complexity.

Minimax V1 (Iterative Deepening)

Enhances basic minimax with iterative deepening - progressively searches deeper levels until time runs out. Always returns the best move found so far, making optimal use of available thinking time.

Minimax V2 (Alpha-Beta Pruning)

Optimizes minimax using alpha-beta pruning to eliminate branches that cannot affect the final decision. Maintains the same optimal results as basic minimax but searches significantly fewer nodes, allowing deeper exploration.

Minimax V3 (Alpha-Beta + Iterative)

Combines alpha-beta pruning with iterative deepening and time management. Progressively deepens search while pruning unnecessary branches, stopping when time limit is reached. Represents the gold standard for perfect-information games.

Minimax V4 (V3 + Transposition Table)

Adds a transposition table (hash map) to store and reuse results from previously evaluated board positions. Prevents redundant calculations when the same position is reached through different move sequences, further improving efficiency.

Monte Carlo Tree Search (MCTS)

Uses statistical sampling instead of exhaustive search. Builds a search tree by repeatedly: (1) Selecting promising nodes using UCT formula, (2) Expanding the tree, (3) Simulating random games, (4) Backpropagating results. Particularly effective for larger boards where minimax becomes impractical.

Technical Implementation

Originally developed in Python with a Tkinter GUI, this web version faithfully recreates all the AI algorithms in JavaScript. The bots use the same decision-making logic, adapted for real-time browser gameplay.

Key features include customizable board sizes (3×3 to 10×10), adjustable win conditions, and performance optimizations for smooth gameplay. The minimax implementations showcase classic game tree search techniques, while MCTS demonstrates modern probabilistic approaches.

Each bot can play as either X or O, allowing for bot-vs-bot matches to compare strategies. The modular design makes it easy to add new AI implementations or adjust existing ones.

View Source Code