MinMax (Game Theory)
Game theory in its simplest form — always the best move, against an opponent who also gives nothing away.
Connect Four
Drop chips and form 4 in a row. Click ▼ above a column.
Connect Four has over 4 trillion possible positions! The AI uses heuristics and Alpha-Beta pruning to find good moves.
Definition
What is the MinMax Algorithm?
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.
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 looks only a few moves ahead and so misses traps. In hard mode it calculates much further – in Tic-Tac-Toe to the end of the game, where it plays perfectly. 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.
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.
Check
Test Your Knowledge
What does 'MinMax' mean in the MinMax algorithm?
Select one answer
1. What does 'MinMax' mean in the MinMax algorithm?
2. What does MinMax assume about the opponent?
3. What happens in Tic-Tac-Toe with perfect play from both sides?
4. What does Alpha-Beta Pruning do?
5. What is a game tree?
6. What does a MAX node do in the game tree?
7. Why is Connect Four more complex than Tic-Tac-Toe?
8. What happens when the AI searches deeper in the game tree?
9. What is a heuristic in game AI?
10. What is a zero-sum game?