Building a chess engine with Negamax and alpha-beta pruning

In August 2023 I built a chess engine from scratch in Python with Pygame. It supports two-player and single-player games and handles the awkward rules (castling, en passant, promotion). The bot uses classical search rather than a neural network, and reached roughly 1800 when I played it against Stockfish. Code is on GitHub.

Classical engines search the game tree to a fixed depth, score the positions they reach with a hand-written evaluation function, and choose the move that does best against the opponent’s best reply. That is a different approach from neural engines, which learn their evaluation.

How the engine works

Board representation. The board is an 8×8 array of integers. White pieces are 1 to 6, black pieces −1 to −6, and empty squares 0.

Move generation. For each piece on the board, a piece-specific function generates its moves. Pins and checks are tracked while generating, so a pinned piece can only move along the pin line. Pawn moves cover double steps, captures, promotion and en passant; the king’s moves include castling.

Move validation. A move is legal if it appears in the list of valid moves for the current position. When the king is in check, that list is cut down to moves that block the check, capture the checking piece, or move the king.

Evaluation. The evaluation checks each position for threats, pins and checks.

Move selection. The bot can pick moves four ways: at random, or with Minimax, Negamax, or Negamax with alpha-beta pruning.

The search algorithms

Minimax

Minimax assumes both sides play their best. It runs a depth-first search to a fixed depth, scores the leaf positions with the evaluation function, and backs the scores up the tree: the side to move takes the maximum, the opponent the minimum. The search is exhaustive, so the cost grows exponentially with depth.

Negamax

Chess is zero-sum, so a position’s value for one player is the negative of its value for the other. Negamax uses this to fold the maximising and minimising branches of Minimax into a single recursive function. It searches the same tree, with less code and fewer places for bugs.

Alpha-beta pruning

Alpha-beta keeps two bounds during the search: alpha, the score the maximising side is already guaranteed, and beta, the most the minimising side will allow. Once a branch can’t change the final decision, the engine stops searching it. The result is identical to plain Minimax, but far fewer nodes are evaluated, so the engine can search deeper in the same time.