Told quickly, the history of game-playing programs sounds like a history of horsepower: the machines got faster and the games fell over one by one. That story does not survive contact with the dates. Computing power grew smoothly and without interruption for seventy years; the ideas below number six, and each of them is dated by a paper rather than by a generation of hardware.
What the six have in common is the shape of the move. None of them extends the previous idea. Each begins by refusing something the previous one treated as necessary — searching the whole tree, reaching the end of the game, understanding a position before scoring it, knowing anything about the game at all. The ladder is built downwards out of things given up, which is why the next rung will not look like more of this one.
Every rung below says what it buys, where it breaks, what it had to abandon, and which games on this site actually run it. Almost every engine here lives on rungs three and four. Names, dates and figures carry their source in small type; anything we could not source is not on the page.
A game with finitely many positions, no dice and no hidden cards is decidable in principle. Ernst Zermelo showed this in 1913 using chess: either one side has a winning strategy or both can force a draw, and there is no third case. The proof says nothing about how to play — it says the answer is already in the tree. The rest is technique: expand the tree to the leaves where the game has ended and carry the exact result back up. In tic-tac-toe the board fills in 9! = 362,880 orders, less than a processor gets through in a millisecond. No evaluation anywhere: a win, a loss and a draw, computed rather than guessed.
Where it breaksThe tree grows as a power, not as a length: with b continuations per position and a game d plies long there are on the order of bd nodes, and every extra pair of moves multiplies the work. Shannon put the number of chess games at roughly 10120 in 1950. That figure does not shrink for a faster processor, or for a thousand of them: the distance between draughts (1020 positions) and chess (1044) — see Solved games — is not a gap hardware closes. Brute force is not slow. It is impossible.
You cannot walk a tree without deciding what happens at the other side's nodes. Minimax answers that once and for all: take the maximum at your own nodes and the minimum at theirs — assume the opponent picks whatever is worst for you. John von Neumann proved the theorem for zero-sum games in 1928; by 1950 Shannon had written out how it is programmed for chess, and in the early fifties Alan Turing was playing his Turochamp on paper, working positions out by hand for want of a machine. A flawless opponent is not pessimism but the only route to a guarantee: what minimax returns is what you get against the worst the other side can do.
Where it breaksThe guarantee is the weakness. Against a person who does make mistakes, minimax plays not the strongest move but the safest. It will not set a trap, having assumed nobody walks into traps, and will not take the risk that pays off nine times in ten. More importantly, it saves no work at all: this is a rule for scoring a tree, not a way of looking at less of it, and the tree stays as impossible as it was.
Alpha-beta is not a faster search but a refusal to search most of the tree. Once a branch has produced one reply that makes it worse than something already found elsewhere, the whole branch can be dropped: whatever else is inside it cannot change the choice. The result is identical to the full search — not an approximation but a proof of irrelevance. The idea was rediscovered independently several times in the late fifties; a form of it is already in Newell, Shaw and Simon's 1958 chess program, the name stuck to John McCarthy, and the full analysis came from Donald Knuth and Ronald Moore in 1975. Their result is quantitative: with perfect move ordering alpha-beta visits on the order of bd/2 nodes instead of bd. A square root. In the same time, twice the depth.
Where it breaksEverything rests on move ordering. A good first candidate cuts its neighbours away at once; a bad one cuts away nothing, and in the worst case alpha-beta walks the entire tree having saved no node at all. Hence the sorting done before the search — in our draughts, captures first, then promotions, then the rest — which changes the answer not at all and the amount of work decisively. And there is a ceiling it is pleasant to forget: the square root of the impossible is still impossible. 10120 becomes 1060, and nothing is settled.
The leaves are out of reach, so the search stops at a fixed depth, declares the position it arrived at to be the end of the game, and attaches a number to it. Shannon published the first such formula in 1950: a queen is nine, a rook five, a bishop and a knight three each, a pawn one, plus a tenth for each extra legal move available and minus a half for every doubled, isolated or backward pawn. Everything a program "understands" lives in that line. What the numbers look like here: in Reversi a corner is worth the most, the squares beside one carry a penalty because that is how corners are handed over, edges beat the centre, and middlegame mobility outweighs the disc count. In Arthur Samuel's draughts the pair was material and advancement.
Where it breaksThe numbers do not come from the game. A person assigns them — from experience, by analogy, sometimes just to keep the scale consistent — and any position where the meaning and the figure diverge is played wrongly and with total confidence. The best-known form of the failure is the horizon: a disaster one ply past the edge of the search is invisible, and the program postpones it with a run of pointless exchanges, because beyond the horizon there is no disaster. Hans Berliner named the effect in 1974. The remedy is to play captures out until things go quiet — our draughts do exactly that — and it is partial: the horizon moves, it does not go away. Deep Blue carried some eight thousand features in 1997 and still understood a position as a weighted sum. Every "inhuman" mistake comes from here: not a fault, but the place where eight thousand numbers failed to add up to a meaning.
Two different refusals to search forward. The first is to search backwards. Take every position with no more than N pieces, mark the ones where the game is over, and propagate the result back until everything is marked. What comes out is a table the answer is read from rather than derived in. Ken Thompson built such tables for four- and five-piece chess endings in the 1980s; by 2012 all seven-piece endings had been computed, and they hold wins hundreds of moves long. By 2007 Chinook held every position with ten pieces or fewer — thirty-nine trillion of them — and English draughts was declared a draw after eighteen years of computation, the search coming down from the top and the database up from the bottom until they met. The second refusal is more radical. Nobody could score a Go position with a number: there is no material, and every formula lies. Monte Carlo drops the evaluation entirely — play out at random from here many times and count the wins. Bernd Brügmann proposed it in 1993; Rémi Coulom and, independently, Levente Kocsis with Csaba Szepesvári built it into a tree in 2006. A position stops being judged and starts being measured.
Where it breaksA database only knows its own tail. Ten pieces yes, twenty-four no, and a table for the whole game fits on no storage that exists: the same exponent, now pressing against space instead of time. Monte Carlo fails elsewhere. A random playout measures not the position but an average over blunders, and where a win depends on one exact sequence the average sees nothing. The blind spots are also stable. In 2023 researchers found a strategy the strongest Go programs do not understand — encircling a large group along the edge — and the amateur Kellin Pelrine won fourteen of fifteen games playing it, with no computer helping during the games.
If the evaluation weights are the weak point, they need not be set by hand. Arthur Samuel did it first: his draughts program on the IBM 701 adjusted its own coefficients from the games it had played and beat its author in 1956. The result that mattered arrived in 1992, twenty-four years before AlphaGo. Gerald Tesauro's TD-Gammon was a network told nothing but the rules of backgammon; it played three hundred thousand games against itself, learning by Richard Sutton's temporal-difference method, and reached the level of the strongest humans. The level was not the interesting part: some of its opening preferences disagreed with human theory and were judged the better ones, and people revised how several opening rolls are played. The rest is familiar — AlphaGo Zero learned Go in 2017 without a single human game and beat its predecessor 100-0, and AlphaZero took chess and shogi the same way.
Where it breaksLearning replaces none of the earlier rungs; it sits on top of them. AlphaZero still walks a tree, only it scores with a network and chooses branches by Monte Carlo. What changed is not the mechanism but where the numbers come from. The first price is legibility: you could ask Shannon why a queen is nine and get an answer, whereas a network has nobody to ask, and its mistake looks not like a wrong weight but like an unexplained move. The second price is resources. AlphaZero examines roughly a thousandth of the positions per second that Stockfish does and wins anyway — but behind that are millions of self-play games and purpose-built hardware only a handful of organisations have. This rung is the newest and by a wide margin the most expensive.
Read top to bottom the six look like a progression, but the links between neighbours are all negative. Brute force says count everything; minimax adds a hostile will inside the tree; alpha-beta refuses to finish counting; the evaluation function refuses to reach the end at all; databases refuse the direction of the count and Monte Carlo refuses to judge; self-play refuses the numbers a person picked. Not one of these transitions was the same thing, faster.
Which is why "another thousandfold and the next step arrives" is the wrong kind of prediction. Deep Blue searched about two hundred million positions a second and was the last machine of the old kind. AlphaZero searches roughly a thousandth of that and plays better. The quantity moved in one direction and the results moved in another, because what changed was which question was being asked of the tree.
Nothing useful can be said about the seventh rung except that it will be a refusal. What can be pointed at is where the current one leaks: 2023, a large group encircled along the edge, an amateur taking fourteen games of fifteen from a program that beats every professional. That hole was not found by playing better. It was found by a second program trained to look for holes — a different question, which is how these steps have always started.
And one honest note about this site. Nearly every opponent here stands on rungs three and four: alpha-beta plus an evaluation somebody wrote by hand, a few plies deep, no memory between games and no adaptation to you. Beating one of them is beating 1975 running on good hardware. Losing to one is losing to the person who chose the weights.
Deep Blue at about 200 million positions per second: M. Campbell, A. J. Hoane, F.-h. Hsu, Deep Blue, Artificial Intelligence 134(1–2), 2002. AlphaZero's search rate against Stockfish: D. Silver et al., Science 362(6419), 2018. The 2023 Go weakness and Kellin Pelrine's fourteen wins in fifteen games: T. Wang et al., Adversarial Policies Beat Superhuman Go AIs, ICML, 2023. What our own engines do: the How the computer thinks block on each game page.