How Do Computers Play Chess? Searching, Pruning and Then Learning

The classical approach treats chess as a tree. From the current position each legal move leads to a new position, from which the opponent has legal moves, and so on. A program explores that tree several moves deep and evaluates the positions at the bottom with a scoring function, then works backwards assuming each side chooses the line best for itself, which is the minimax principle. The problem is size: with around thirty-five legal moves in a typical position, looking four moves ahead for each side means tens of billions of positions. The technique that makes it tractable is alpha-beta pruning, which recognises that once one reply is found refuting a candidate move, the remaining replies need not be examined, since the move is already known to be bad enough. Alpha-beta cuts the effective work enormously and, with good move ordering, roughly halves the exponent, letting a program search twice as deep in the same time.

Decades of engineering around that core produced the strength that beat Kasparov, and most of the gains came from searching smarter rather than faster:

• •Move ordering, trying the most promising moves first so that pruning happens as early as possible, which is worth more than any other single optimisation
• •Transposition tables, storing evaluated positions in a hash table, since the same position is reached by many different move orders
• •Quiescence search, extending the search past the nominal depth while captures and checks remain, to avoid stopping in the middle of an exchange and misjudging it badly
• •Iterative deepening, searching to depth one, then two, then three, which sounds wasteful and actually helps because the shallow results order the moves for the deeper search and allow stopping cleanly when time runs out
• •Opening books and endgame tablebases, which replace search with lookup, the latter being a complete solved database of every position with a small number of pieces, proving exact results dozens of moves from mate
• •An evaluation function combining material, pawn structure, king safety, mobility and other terms, hand-tuned by strong players over years

Chess was proposed as a test of machine intelligence early, with Shannon publishing on how a computer might play in 1950 and Turing writing a program before hardware existed to run it. Progress was steady and unspectacular for decades. Deep Blue's defeat of Garry Kasparov in 1997 was a landmark and rested largely on custom hardware evaluating around two hundred million positions a second, which is brute force with expert knowledge attached rather than anything resembling understanding. The gap widened afterwards with software rather than hardware, and by the 2000s programs on ordinary computers exceeded any human. The second landmark came in 2017, when AlphaZero, given only the rules and trained by playing itself, reached a level that beat the strongest conventional program after hours of training, using a search that examined a tiny fraction as many positions per second but guided by a neural network that had learned which positions were promising. The lesson was that a learned sense of position could substitute for enormous search.

Engines transformed how the game is studied and played. Opening preparation became a computational exercise, with players arriving at elite tournaments having checked lines twenty or thirty moves deep, and whole variations previously considered sound were refuted overnight. Analysis of one's own games is now routine and instantaneous, which has accelerated improvement among players with no access to a coach and contributed to the falling age at which grandmaster titles are achieved. Engines also revised long-standing positional judgements: several sacrifices and structures once considered dubious turned out to be sound, and machine evaluations have made positions that look ugly to a trained human acceptable. The costs are real too. Online cheating became a structural problem requiring statistical detection, over-the-board events introduced scanning and delayed broadcasts, and the availability of perfect analysis has changed what spectators see, since commentary now displays an evaluation bar that tells the audience who is winning before the players know.

Classical chess programs search a tree of moves, evaluate the leaf positions with a hand-written scoring function and work backwards, using alpha-beta pruning to discard lines already refuted. Move ordering, transposition tables, quiescence search and endgame databases supplied most of the strength, and Deep Blue beat Kasparov in 1997 largely through custom hardware. AlphaZero showed in 2017 that a network trained only by self-play could guide a far smaller search to greater strength.