Building My First AI Project: Tic Tac Toe with Minimax (No ML Libraries)

#ai #machinelearning #algorithms #python

I recently started exploring AI through Harvard CS50’s AI course, and I decided to implement my first AI project from scratch in Python: a Tic Tac Toe AI using the Minimax algorithm.

The goal wasn’t just to make a working game—but to understand AI concepts deeply by implementing them myself. Here’s a breakdown of what I learned and applied.

What I Learned from CS50 AI

The course covers a broad spectrum of AI topics:

Search – How to find solutions to problems, like navigating from point A to B or making optimal moves in a game.
Knowledge & Inference – Representing information and drawing conclusions from it.
Uncertainty – Using probability to make decisions under uncertain conditions.
Optimization – Not just finding any solution, but the best solution.
Learning – Improving performance from experience, like distinguishing spam emails.
Neural Networks & Language Processing – For more complex AI tasks beyond search and strategy.

I focused on search and adversarial search, which are foundational for game AI.

Core Concepts Applied

Before coding, I had to understand a few key AI concepts:

Agent – The “decision-maker” in the system (our AI player).
State – A snapshot of the environment (board configuration).
Actions – Possible moves from a state.
Transition Model – What happens when an action is applied.
State Space – All possible states reachable from the initial state.
Goal Test & Utility – Checking if the game is over and assigning value (+1 win, -1 loss, 0 tie).

This framework helped me reason about the game in a structured, AI-centric way rather than just coding moves randomly.

Why Minimax?

Tic Tac Toe is a small, adversarial game, which makes it perfect to experiment with Minimax:

Maximizer vs Minimizer – The AI tries to maximize its score while assuming the opponent tries to minimize it.
Recursion – For each move, the algorithm simulates all possible future moves to decide the best one.
Depth-Limited Search – Useful for bigger games (like Chess) to avoid exploring an intractable number of states.
Alpha-Beta Pruning – Skips obviously bad moves to optimize computation.

By implementing Minimax, I could see firsthand how the AI anticipates every possible opponent move—something that reading theory alone can’t fully convey.

Implementation Insights

I built functions like:

Actions(state) – Returns all valid moves.
Result(state, action) – Returns the board after a move.
Terminal(state) – Checks if the game is over.
Utility(state) – Evaluates the outcome of terminal states.

Then, using recursive Max-Value and Min-Value functions, the AI evaluates each move:

def max_value(state):
    if terminal(state):
        return utility(state)
    v = -float('inf')
    for action in actions(state):
        v = max(v, min_value(result(state, action)))
    return v

The minimizing player works similarly, ensuring optimal play from both sides. The result? An AI that never loses.

Lessons Learned

Minimax is ideal for small, perfect-information games.
Real-world games require heuristics and pruning strategies to handle enormous state spaces.
Coding the algorithm reinforced my understanding of state spaces, goal tests, and recursive evaluation far better than studying theory alone.

This project gave me a solid foundation in adversarial search, and I’m now excited to tackle larger games and explore heuristic-based AI.