Minimax Algorithm: How Chess Engines Choose the Best Move

When a chess engine looks at a position, it does not rely on intuition or experience. Instead, it assumes two things:

1. It will always try to play the best possible move

2. Its opponent will also always try to play the best possible move

The Minimax algorithm is built entirely on these assumptions. It is the foundation of classical chess engines and many other game-playing programs.

---

What Problem Does Minimax Solve?

In chess, every move leads to multiple responses, and each response leads to more moves. This creates a game tree.

The goal of Minimax is to:

• Explore this game tree up to a certain depth

• Evaluate the resulting positions

• Choose the move that leads to the best guaranteed outcome

---

Max and Min Players

• Max player: the chess engine (tries to maximize the score)

• Min player: the opponent (tries to minimize the score)

At each level of the tree:

• Max chooses the move with the highest value

• Min chooses the move with the lowest value

---

Why We Need an Evaluation Function

It is impossible to search until checkmate in most positions.
So, Minimax searches to a fixed depth and then evaluates the board.

Example evaluation logic:

• Material advantage

• Piece activity

• King safety

• Pawn structure

The evaluation function converts a board position into a numeric score.

---

Minimax Algorithm (Conceptual Flow)

1. Generate all legal moves

2. Apply a move to get a new position

3. Recursively evaluate future positions

4. Choose the best score based on whose turn it is

---

Simple Minimax Implementation in C++

Below is a simplified C++ version of Minimax.
This example focuses on structure, not full chess rules.

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// Placeholder evaluation function
int evaluateBoard() {
    // Positive score = good for engine
    // Negative score = good for opponent
    return rand() % 200 - 100;
}

// Placeholder move generation
vector<int> generateMoves() {
    // Each integer represents a move (simplified)
    return {1, 2, 3};
}

// Minimax function
int minimax(int depth, bool isMaxPlayer) {
    if (depth == 0) {
        return evaluateBoard();
    }

    vector<int> moves = generateMoves();

    if (isMaxPlayer) {
        int bestScore = -INF;

        for (int move : moves) {
            // makeMove(move);
            int score = minimax(depth - 1, false);
            // undoMove(move);

            bestScore = max(bestScore, score);
        }
        return bestScore;
    } else {
        int bestScore = INF;

        for (int move : moves) {
            // makeMove(move);
            int score = minimax(depth - 1, true);
            // undoMove(move);

            bestScore = min(bestScore, score);
        }
        return bestScore;
    }
}

---

Choosing the Best Move

To select the actual move, we evaluate all possible root moves.

int findBestMove(int depth) {
    vector<int> moves = generateMoves();
    int bestMove = -1;
    int bestScore = -INF;

    for (int move : moves) {
        // makeMove(move);
        int score = minimax(depth - 1, false);
        // undoMove(move);

        if (score > bestScore) {
            bestScore = score;
            bestMove = move;
        }
    }

    return bestMove;
}

---

Time Complexity

Let:

• b = branching factor (≈ 35 in chess)

• d = search depth

Time complexity:

O(b^d)

This exponential growth is the biggest limitation of Minimax.

---

Why Minimax Alone Is Not Enough for Chess

Minimax works, but it is too slow on its own.

Problems:

• Explores every possible move

• Cannot search deep enough

• Becomes unusable without optimizations

This is why real chess engines combine Minimax with:

• Alpha–Beta Pruning

• Move ordering

• Transposition tables

• Quiescence search

---

Relationship with Alpha–Beta Pruning

Minimax defines what decision to make.
Alpha–Beta Pruning defines what can be safely ignored.

Alpha–Beta does not replace Minimax.
It makes Minimax practical.

---

Where Minimax Is Used Beyond Chess

• Tic-Tac-Toe

• Checkers

• Connect Four

• Turn-based strategy games

• Game AI in general

Any game with:

• Two players

• Perfect information

• Turn-based moves

---

Final Thoughts

Minimax is simple in idea but powerful in impact.
It models rational decision-making under perfect information.

While modern chess engines use neural networks and massive optimizations, Minimax remains the core decision-making principle underneath it all.

Understanding Minimax is the first real step toward understanding how chess engines think.