MinMax (Game Theory)
Game theory in its simplest form — always the best move, against an opponent who also gives nothing away.
What is the MinMax Algorithm?
Imagine playing chess against a friend and thinking several moves ahead: "If I move here, they'll probably move there, and then I can..." - that's exactly how the MinMax algorithm thinks!
The AI simulates all possible game outcomes in a decision tree. It assumes the opponent always makes the best move for themselves (minimizes your advantage), while maximizing its own advantage.
The special thing: With perfect play from both sides, Tic-Tac-Toe can never be won - it always ends in a draw!
Analogy:
Imagine playing chess against a friend and thinking several moves ahead: "If I move here, they'll probably move there, and then I can..." - that's exactly how the MinMax algorithm thinks!
The AI simulates all possible game outcomes in a decision tree. It assumes the opponent always makes the best move for themselves (minimizes your advantage), while maximizing its own advantage.
The special thing: With perfect play from both sides, Tic-Tac-Toe can never be won - it always ends in a draw!
Definition:
The MinMax algorithm is a recursive decision-making algorithm for two-player zero-sum games. It traverses the game tree up to a maximum depth and evaluates terminal positions. MAX nodes maximize the value (AI moves), MIN nodes minimize it (opponent moves). Alpha-Beta pruning can drastically improve efficiency by cutting off irrelevant branches.
How This Demo Works
This demo lets you play against an AI opponent. You can choose different games and watch how the AI thinks and calculates the best move.
The Different Games
Choose between Tic-Tac-Toe, Connect Four, Nim, Reversi, and Gomoku. Each game has different complexity and requires different strategies.
Difficulty Levels
In easy mode, the AI makes intentional mistakes. In hard mode, it plays optimally and calculates many moves ahead. Watch how the number of evaluated moves changes.
The Game Tree
The AI thinks in a game tree: It simulates all possible moves and counter-moves. MAX nodes (AI) maximize the value, MIN nodes (player) minimize it. This is how it finds the best possible move.
Interactive Demo: Play Against MinMax
⚪ Gomoku (5 in a Row)
Place 5 stones in a row on the 9x9 board. Click an intersection.
Gomoku on a 9x9 board: The AI focuses on areas near existing stones and evaluates line potential for 5-in-a-row patterns.
Select Game
⭐⭐ Medium - Large game tree
Game Settings
Click on the board to start
Display Options
Statistics
The Algorithm in Detail
When playing against the AI, you might wonder: "Why can't I ever win at Tic-Tac-Toe?" The answer lies in the MinMax algorithm – an elegant concept that mathematically guarantees optimal play.
The Core Idea: Thinking Like Your Opponent
Imagine playing chess and thinking: "If I move here, my opponent will probably move there, and then I can..." That's exactly how MinMax thinks! The algorithm simulates all possible game sequences, assuming both players play optimally.
The special part: The AI assumes you'll always make your best move. It prepares for the worst case – which is why it's so hard to beat.
Maximizing and Minimizing
The name "MinMax" describes the two roles in the game:
- Maximizer (AI): Wants to maximize the score. Searches for the move with the highest value.
- Minimizer (You): Wants to minimize the score. The AI assumes you'll play the worst move for it.
This interplay continues throughout the entire game tree. In Tic-Tac-Toe, the AI can search the complete tree and play unbeatable!
Why Is Tic-Tac-Toe Always a Draw?
With perfect play from both sides, Tic-Tac-Toe always ends in a draw. That's because MinMax has analyzed all 255,168 possible game sequences and knows: there's no move that forces a win if the opponent responds optimally.
If you win against the AI, it deliberately made a suboptimal move (easy difficulty) or you found a position the AI undervalued.
Alpha-Beta Pruning: Smart Cutting
For more complex games like Connect Four or Reversi, searching all possibilities would be too slow. This is where Alpha-Beta Pruning comes in:
- Alpha: The best value the maximizer has found so far
- Beta: The best value the minimizer has found so far
- When Beta ≤ Alpha, remaining moves can be ignored – they won't change the result
This optimization can drastically reduce the number of positions to examine – sometimes by up to 99%!
Play and Understand
Watch in the demo above how many moves the AI analyzes. In Tic-Tac-Toe, it's thousands initially; in Connect Four, it can be millions. Enable "Animate AI thinking" and watch the AI play through different moves.
Experiment: Try to beat the AI on "Hard" in different games. You'll notice: the more complex the game, the harder it gets – but also the more interesting the strategic possibilities!
1
# MinMax Algorithm with Alpha-Beta Pruning
2
function minmax(game_state, depth, is_maximizer):
3
# Base case: Game is over or maximum depth reached
4
if game_state.is_terminal() or depth == 0:
5
return evaluate_position(game_state)
6
7
# Maximizer: AI searches for the highest value
8
if is_maximizer:
9
best_value = -INFINITY
10
for each move in game_state.possible_moves():
11
game_state.make_move(move)
12
value = minmax(game_state, depth - 1, FALSE)
13
game_state.undo_move(move)
14
best_value = max(best_value, value)
15
return best_value
16
17
# Minimizer: Opponent searches for the lowest value
18
else:
19
best_value = +INFINITY
20
for each move in game_state.possible_moves():
21
game_state.make_move(move)
22
value = minmax(game_state, depth - 1, TRUE)
23
game_state.undo_move(move)
24
best_value = min(best_value, value)
25
return best_value
26
27
# Optimization: Alpha-Beta Pruning
28
function alphabeta(game_state, depth, alpha, beta, is_max):
29
# Cut off branches that cannot affect the result anymore
30
if beta <= alpha:
31
break # Pruning: This branch is irrelevant
Check Base Case
First, the algorithm checks if the game is over (win, loss, draw) or the maximum search depth has been reached. Terminal positions directly return their value.
# Base case: Game is over or maximum depth reached
if game_state.is_terminal() or depth == 0:
return evaluate_position(game_state)
Build Game Tree
The algorithm views the game as a tree: each node is a game state, each edge is a possible move. The tree grows exponentially with depth.
MAX Node: AI's Turn
The AI wants to maximize the game value. It examines all child nodes and picks the one with the highest value.
MIN Node: Opponent's Turn
The opponent wants to minimize the game value. They choose the move that is worst for the AI.
Evaluate Leaves
Terminal positions or nodes at search limit are evaluated with a scoring function: Win = +∞, Loss = -∞, other positions get heuristic values.
Propagate Values Upward
Evaluations are passed from leaves to root. Each node receives the best/worst value of its children.
Choose Optimal Move
At the root, the move leading to the best value is selected. With perfect play, this is guaranteed to be the optimal move.
Test Your Knowledge
What does 'MinMax' mean in the MinMax algorithm?
1. What does 'MinMax' mean in the MinMax algorithm?
- ☐ A) Maximize your own advantage, minimize your opponent's
- ☐ B) Minimize moves, maximize speed
- ☐ C) Find the minimum and maximum game score
- ☐ D) Minimize errors, maximize randomness
2. What does MinMax assume about the opponent?
- ☐ A) The opponent makes random moves
- ☐ B) The opponent always plays optimally
- ☐ C) The opponent sometimes makes mistakes
- ☐ D) The opponent copies your moves
3. What happens in Tic-Tac-Toe with perfect play from both sides?
- ☐ A) The first player always wins
- ☐ B) The second player always wins
- ☐ C) It always ends in a draw
- ☐ D) The result is random
4. What does Alpha-Beta Pruning do?
- ☐ A) It makes the AI smarter
- ☐ B) It finds better moves
- ☐ C) It remembers previous games
- ☐ D) It cuts off irrelevant branches and saves time
5. What is a game tree?
- ☐ A) A structure representing all possible game moves
- ☐ B) A random generator for moves
- ☐ C) A list of won games
- ☐ D) An algorithm for move evaluation
6. What does a MAX node do in the game tree?
- ☐ A) It minimizes the value
- ☐ B) It maximizes the value (AI seeks best move)
- ☐ C) It calculates the average
- ☐ D) It chooses randomly
7. Why is Connect Four more complex than Tic-Tac-Toe?
- ☐ A) The board is more colorful
- ☐ B) The rules are more complicated
- ☐ C) There are many more possible positions
- ☐ D) You need more players
8. What happens when the AI searches deeper in the game tree?
- ☐ A) It always plays perfectly
- ☐ B) It takes more time but finds better moves
- ☐ C) It makes more mistakes
- ☐ D) It forgets earlier moves
9. What is a heuristic in game AI?
- ☐ A) A rule for quickly evaluating game positions
- ☐ B) A random generator for moves
- ☐ C) A memory for old games
- ☐ D) A method for cheating
10. What is a zero-sum game?
- ☐ A) A game without points
- ☐ B) What one player wins, the other loses
- ☐ C) A game that always ends in a draw
- ☐ D) A game with zero moves
Related Content
Article
Algorithmic Complexity
The lesson that an elegant algorithm beats any supercomputer — provided n is large enough.
Control Structures
Control structures: everything that decides between "do this" and "do that".
Data Structures II (Hierarchical & Networked)
Trees, search trees, and graphs — data structures with family relationships.
Rules & Logic: Expert Systems
AI before it learned from data: asked experts, wrote down rules, hoped.
Agents in Conflict — Game Theory
What a second rational player changes about an optimization — everything.
Graph Search — The Beginnings
Graph search: the first thing AI could actually do — and still useful today.
Heuristics & Pathfinding: From Dijkstra to A*
How A* works — and why Dijkstra gets boring without a heuristic.
MinMax & Pruning
MinMax in practice: think backwards, assume the worst opponent, shortcut where possible.
Recursion
Recursion: the programming technique that looks simple until you understand it. And then too.
What Is an Algorithm?
What Euclid, IKEA instructions, and Google search have in common — all three are algorithms.
Demo
Pathfinding (Graph Search)
Interactive visualization of pathfinding algorithms like A*, Dijkstra and more
Q-Learning
Interactive demonstration of the Q-Learning algorithm with an intelligent agent in the Temple of Learning
Rule-Based AI
Collect clues and solve criminal cases through systematic application of rule-based logic. This interactive demo shows how AI systems reach solutions step by step.
Travelling Salesman: Algorithms in Competition
Place cities, draw your own route, and pit Greedy, Simulated Annealing and a Genetic Algorithm against you.