Making the Chess Engine

by Davis Liu, Sept 2026

At it's core, a chess engine is a minimax algorithm - a type of algorithm that uses decision trees to play zero-sum turn-based games.

In this category of games, a player attempts to maximize a score relative to all other opponents. This can be done by storing a vector of scores $[s_1, \dots, s_n]$ where each player $i$ tries to maximize $s_i - \max(\{s_j \mid j \ne i\})$ on their turn. In chess, there are two players, so the score can be simplified to a single value $s = s_1-s_2$.

It's often impractical to evaluate the entire game tree, which grows exponentially. So, we can use a heuristic function to estimate the score after playing up to a certain depth.

The general minimax algorithm (not necessarily optimzied):

using score_t = array<double, N_PLAYERS>;

pair<score_t, move_t> get_best_move(int player, int depth) {
    pair<score_t, move_t> best = {WORST_SCORE(player), INVALID};
    for (move_t m: get_moves(player)) {
        try_move(m);
        if (depth == 1) {
            score_t score = evaluate();
            if (advantage(score, player) > advantage(best.first, player)) {
                best = {score, m};
            }
        } else {
            pair<double, move_t> result = get_best_move((player+1) % N_PLAYERS, depth-1);
            if (advantage(result.first, player) > advantage(best.first, player)) {
                best = result;
            }
        }
        undo_move(m);
    }
    return best;
}

The Evaluation Function

Since the evaluation function is a heuristic, we would like to pick one that is fast to compute and good enough to represent an objective score.

For chess specifically, we can use a combination of the following:

• If the player has lost, $s_i = -\infty$
• Material: Assign each piece a material value based on its usefulness
• Positioning: Some combination of various aspects:

  Suppose you and your opponent have $N_0$ and $N_1$ pieces and $M_0$ and $M_1$ availible moves respectively.

  • Being in check is generally worse - $O(M_1)$
  • Having more moves available compared to the opponent generally better - $O(M_0+M_1)$ if it does not account for whose turn it is
  • Specific rules for specific pieces, such as pawns being closer to the end compared the the opponent's pawns being better - at least $O(N_0+N_1)$

Parallel Evaluation

Modern CPUs typically have multiple cores, but a single threaded algorithm only uses one. The score of all moves starting from a given state can be evaluated in parallel, which makes use of hardware concurrency. This can be done using a thread pool, or more simply by allocating a fraction of the moves for each thread. Each thread can receive a copy of the board state to operate on independently.