Chess AI using Minimax

A chess engine built on the minimax algorithm with alpha-beta pruning, alongside a full implementation of chess itself, documented in a write-up of over 150 pages.

Search

Minimax explores the game tree recursively, assuming the opponent plays their best available move at every level. Alpha-beta pruning then discards branches that cannot affect the final decision, which makes a meaningful search depth achievable: the algorithm is identical in its result but explores a fraction of the nodes.

Evaluation and rules

The engine needs a position evaluation function to score leaf nodes, and legal move generation and validation to know what the tree even contains. I wrote the game itself in Pygame from scratch, which meant implementing the rules properly, including the awkward ones that are easy to overlook.