# 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.

```cpp
#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.

```cpp
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:

```cpp
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.