AI Origins · Lesson 02

1v1 Game AI: Minimax

Live adversarial search lab: play Tic-Tac-Toe while the engine reveals maximizing/minimizing logic, terminal scoring, and game-tree decisions.

Live Minimax Engine Lab

Play as X (maximizer). The AI plays O (minimizer) and returns best score + best move each turn using the minimax framework tied to von Neumann's 1928 theorem.

Tic-Tac-Toe Board

X turn · Maximizer

Balance of Power Perfect draw

AI choice will appear here after search.

Debug Console Engine events
 

Biography Spotlight

The Architect of the Modern Mind

John von Neumann (1903–1957) was a Hungarian-American mathematician and polymath whose theoretical frameworks provide the literal blueprint for every AI you interact with today.

While he is famously known for the Von Neumann Architecture, the standard design of modern computers that separates processing from memory, his legacy in AI and robotics also comes from his obsession with self-replicating automata.

In 1928, he formalized the Minimax Theorem in game theory, showing how rational players choose the best strategy under opposition. That logic is still at the core of adversarial AI decision-making.

Now test that exact theory in action: play this Tic-Tac-Toe lab using minimax ideas developed by JVN in 1928.

What Minimax Actually Is

Minimax is the decision rule behind many two-player game AIs: it looks ahead through possible moves, scores the endings, and then chooses the move that leads to the best worst-case outcome.

In a game like Tic-Tac-Toe, Minimax assumes that both players are trying to play as intelligently as possible. Instead of asking, "What move looks good right now?" the AI asks, "If I make this move, what will my opponent do next, and what happens after that?"

The algorithm explores the game tree one turn at a time until it reaches terminal states such as a win, loss, or draw. Those endings are given scores, and the scores are then passed back up the tree to evaluate earlier choices.

For X +1

X can force a win.

For Draw 0

Neither side can force victory.

For O -1

O can force a win.

When it is the maximizing player's turn, the algorithm chooses the highest score available. When it is the minimizing player's turn, it chooses the lowest. That back-and-forth is why it is called Minimax: one player maximizes the score, while the other minimizes it.

Under the Hood: The Backend Code

How do we translate this mathematical theory into actual code? The engine relies heavily on a concept called recursion.

At the core of the engine is a recursive function—a function that repeatedly calls itself. When the AI needs to make a move, it calls a minimax() function to evaluate every available spot on the board.

The code logic looks roughly like this:

function minimax(board, isMaximizingPlayer) {
  // 1. Base Case: Is the game over?
  let score = evaluateBoard(board);
  if (score === 1) return score;  // Maximizer won
  if (score === -1) return score; // Minimizer won
  if (isBoardFull(board)) return 0; // Draw

  // 2. Recursive Step
  if (isMaximizingPlayer) {
    let bestVal = -Infinity;
    for (let move of getAvailableMoves(board)) {
      board.makeMove(move, "X");
      let value = minimax(board, false); // Opponent's turn
      board.undoMove(move);
      bestVal = Math.max(bestVal, value);
    }
    return bestVal;
  } else {
    let bestVal = Infinity;
    for (let move of getAvailableMoves(board)) {
      board.makeMove(move, "O");
      let value = minimax(board, true); // Opponent's turn
      board.undoMove(move);
      bestVal = Math.min(bestVal, value);
    }
    return bestVal;
  }
}

Base Case (Terminal State): Before making a move, the function checks if the game is over. If the board has reached a terminal state (win, loss, or draw), it immediately returns a fixed score (+1, -1, or 0) because continuing to search deeper is redundant once the game is decided.

The Recursive Call: When the game is not over, the function simulates a move in its imagination (board.makeMove()), and asks itself, "What will the opponent do next?" Therefore, it calls minimax() recursively with the turn flipped, which means the search descends ply by ply until it hits all terminal leaves.

Backtracking: Crucially, after evaluating a simulated move, the AI must execute undoMove() in order to return the board to its original state so that it can safely explore the next alternative branch without leaving phantom pieces on the board.

Minimizing and Maximizing: The maximizer starts with a baseline of -Infinity and seeks any score that is higher. The minimizer starts at Infinity and seeks anything lower. Consequently, this minimax alternation propagates the optimal worst-case guarantees back to the root, which explains why perfect minimax play never loses in finite zero-sum games.

Worked Example: Step-by-Step Minimax Evaluation

Walk through an adversarial game tree to see exactly how minimax backs up terminal values to make an optimal choice.

Sample Problem: X's Turn on Move 7 (3 Empty Squares)

Suppose the game has progressed to move 7. Player X (the Maximizer) is choosing between three open cells: square 2, square 6, and square 8. O (the Minimizer) will move next if the game does not immediately end. How does Minimax evaluate X's choices?

  1. Step 1: Expand Sub-Tree for Move A (Square 2). Because square 2 immediately completes the top row with three X's in a row, the board reaches a terminal state. The static evaluation returns score = +1 directly without requiring any further recursion.
  2. Step 2: Expand Sub-Tree for Move B (Square 6). Move B does not win immediately. Therefore, the algorithm flips turns to O (the Minimizer) with 2 remaining empty cells. If O plays square 2, O wins (terminal score = -1). If O plays square 8, the game draws (terminal score = 0). Because O is a rational minimizer, O picks \(\min(-1, 0) = -1\). This means backing up Move B assigns a minimax value of -1 to square 6.
  3. Step 3: Expand Sub-Tree for Move C (Square 8). Similar to Move B, playing square 8 allows O to immediately win on the next turn with square 2, which results in a terminal score of -1.
  4. Step 4: Maximizer's Optimal Decision. Player X evaluates the backed-up values of all candidate moves: \(\max(\text{Move A}, \text{Move B}, \text{Move C}) = \max(+1, -1, -1) = +1\). Consequently, X selects square 2. This guarantees a forced win regardless of what O tries to do, which explains why a depth-complete minimax player can never be defeated.

Self-Check Question

If X faces a position where Move 1 leads to backed-up score 0, Move 2 leads to -1, and Move 3 leads to 0, which move(s) will X consider optimal, and what outcome does this guarantee?

Show Answer & Derivation

Answer: X will select either Move 1 or Move 3, guaranteeing at least a draw (score 0). Because X is the maximizer, X chooses \(\max(0, -1, 0) = 0\). Rejecting Move 2 is essential because choosing Move 2 would lead to an outcome where O can force a win (score -1).

Sources & Further Reading

Foundational primary literature on game theory, adversarial search, and computational complexity.

  • 1928 Primary Paper von Neumann, John. “Zur Theorie der Gesellschaftsspiele” (On the Theory of Games of Strategy). Mathematische Annalen, 100, 295–320 (1928). The mathematical proof of the Minimax Theorem for two-player zero-sum games.
  • 1950 Chess Search Shannon, Claude E. “Programming a Computer for Playing Chess.” Philosophical Magazine, 41(314), 256–275 (1950). Introduced the minimax game tree search and heuristic evaluation functions to computing.
  • 1975 Alpha-Beta Pruning Knuth, Donald E., & Moore, Ronald W. “An analysis of alpha-beta pruning.” Artificial Intelligence, 6(4), 293–326 (1975). Mathematical derivation showing alpha-beta search cuts effective branching factor from \(b\) to \(\sqrt{b}\).
  • Textbook Reference Russell, Stuart, & Norvig, Peter. Artificial Intelligence: A Modern Approach. Chapter 5: Adversarial Search and Games. Pearson.

Other von Neumann Projects

  • Universal ConstructorA theoretical machine that can build any machine, including a copy of itself, from symbolic instructions.
  • Kinematic Self-Replicating RobotsMechanical self-replication models that inspired later ideas in robotics, autonomous manufacturing, and artificial life.
  • Stochastic ComputingProbabilistic methods for computation under uncertainty, foundational for noisy real-world AI and robust system design.

What You Are Experimenting With

  • Alternating TurnsObserve maximizing (X) and minimizing (O) behavior in real time.
  • Game Tree ReasoningTrace score propagation from terminal nodes back to current move choice.
  • Search ConstraintsAdjust depth and compare node count + branching factor growth.
  • Heuristic BiasToggle depth preference to compare equal-score move ordering.

Reflection + Publish

Capture what the engine chose and why, then publish a short reflection with your demo link.