← All games

How machines learned to play

Six steps, and why each one began by giving up the idea before it

Six steps and six refusals

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.

1

Brute force

count everything that can be counted, all the way to the end
What it can do

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 breaks

The 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.

What it gave upNothing to refuse yet: this is the starting idea that the other five rungs were each built by giving up.
Where this is on the siteNim is the limiting case: the tree is understood so completely that walking it is unnecessary, and the answer collapses into Bouton's formula. In Bulls and Cows the enumeration is visible — five thousand and forty codes exist as a list, crossed off as answers arrive.
E. Zermelo, Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, Proceedings of the Fifth International Congress of Mathematicians, 1913. C. Shannon, Programming a Computer for Playing Chess, Philosophical Magazine 41(314), 1950 — the source of the 10120 estimate. C. Bouton, Nim, a Game with a Complete Mathematical Theory, Annals of Mathematics 3, 1901. Game sizes as on our own Solved games page.
2

Minimax

assume the opponent never makes a mistake
What it can do

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 breaks

The 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.

What it gave upIt gives up the idea that positions are alike. Half the tree now belongs to a will working against you, and the two halves are read by opposite rules.
Where this is on the siteAtaxx on hard builds precisely this three-ply tree — my move, your reply, my move — and takes the minimum at your nodes because it assumes you play well. Evil 2048 shows the rule stripped bare: the opponent is the tile spawn, and the tile lands wherever your best reply turns out worst.
J. von Neumann, Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 100, 1928. C. Shannon, Philosophical Magazine 41(314), 1950. A. Turing, Digital Computers Applied to Games, in Faster Than Thought, ed. B. Bowden, 1953.
3

Alpha-beta pruning

refuse to look where the answer can no longer change
What it can do

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 breaks

Everything 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.

What it gave upIt gives up completeness. The program no longer knows what is inside the branches it cut — it knows only that knowing was unnecessary.
Where this is on the siteReversi, Ataxx and Connect Four are all built on it. Connect Four also shows what ordering is worth: columns are tried from the centre outwards, and searching from the centre reaches about twice the depth of searching left to right — same time, same answer.
A. Newell, J. Shaw, H. Simon, Chess-Playing Programs and the Problem of Complexity, IBM Journal of Research and Development 2(4), 1958. D. Knuth, R. Moore, An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6(4), 1975 — the source of the bd/2 figure. Move ordering in our own engines as described in the How the computer thinks block on the draughts and Connect Four pages.
4

The evaluation function is an admission of defeat

stop counting and replace the rest of the game with one number
What it can do

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 breaks

The 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.

What it gave upIt gives up correctness. For the first time the program's answer stops being a claim about the game and becomes a claim about its own scoring.
Where this is on the siteReversi on expert weighs corners, the squares next to them, and mobility. Draughts scores material with positional corrections and plays captures out first, so no position with a capture pending is ever evaluated. Gomoku scores not stones but six-cell windows with prices fixed in advance.
C. Shannon, Philosophical Magazine 41(314), 1950 — the piece weights and the formula. A. Samuel, Some Studies in Machine Learning Using the Game of Checkers, IBM Journal of Research and Development 3(3), 1959 — material and advancement. P. Rosenbloom, A World-Championship-Level Othello Program, Artificial Intelligence 19, 1982 — positional weights in Othello. H. Berliner, Chess as Problem Solving, PhD thesis, Carnegie Mellon University, 1974 — the horizon effect. M. Campbell, A. J. Hoane, F.-h. Hsu, Deep Blue, Artificial Intelligence 134(1–2), 2002 — about eight thousand evaluation features. The weights in our own engines are our own; see How the computer thinks on each game page.
5

Endgame databases and Monte Carlo

count backwards — or stop counting and start sampling
What it can do

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 breaks

A 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.

What it gave upIt gives up the direction of the search — and then the idea that a position has to be understood before it can be scored. The first trick counts from the end; the second does not count, it votes.
Where this is on the siteNo engine here uses Monte Carlo, and saying so is better than pretending. The nearest relative is Battleship, which does not hunt for ships but counts every fleet placement still consistent with the board and fires where the count is highest. Dots and Boxes builds an endgame database in miniature: once fourteen lines or fewer remain, an exact memoised search takes over and the game is settled. And draughts is the game that the thirty-nine-trillion-position database closed.
K. Thompson, Retrograde Analysis of Certain Endgames, ICCA Journal 9(3), 1986. V. Makhnichev, V. Zakharov, the Lomonosov seven-piece tablebases, Moscow State University, 2012. J. Schaeffer et al., Checkers Is Solved, Science 317(5844), 2007 — the 39-trillion-position database and the eighteen years. B. Brügmann, Monte Carlo Go, 1993. R. Coulom, Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search, Computers and Games, 2006. L. Kocsis, C. Szepesvári, Bandit Based Monte-Carlo Planning, ECML, 2006. T. Wang et al., Adversarial Policies Beat Superhuman Go AIs, ICML, 2023 — and Pelrine's fourteen games out of fifteen.
6

Self-play learning

stop assigning the numbers and extract them from playing yourself
What it can do

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 breaks

Learning 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.

What it gave upIt gives up human knowledge as an input: first the books and the games people played, then the very features a person thought were the ones that mattered.
Where this is on the siteThis rung is absent from the site, and there is no point pretending otherwise: no engine here learns or remembers you between games. The only thing that changes with experience is the Mind Reader, which keeps a table of what you did after each recent run of presses. And backgammon is the game where self-play first worked — though the opponent here runs expectimax over hand-written weights, which leaves it on rung four.
A. Samuel, IBM Journal of Research and Development 3(3), 1959. R. Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning 3, 1988. G. Tesauro, Practical Issues in Temporal Difference Learning, Machine Learning 8, 1992 — the three hundred thousand self-play games. G. Tesauro, Temporal Difference Learning and TD-Gammon, Communications of the ACM 38(3), 1995 — on the revision of opening theory. D. Silver et al., Mastering the Game of Go without Human Knowledge, Nature 550, 2017 — the 100-0 score. D. Silver et al., Science 362(6419), 2018 — AlphaZero and the order-of-magnitude gap in positions searched.

Why the next rung will not be a continuation of this one

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.
Where to go from here
To cite this page: “How machines learned to play”, You vs Computer, https://youvscomputer.com/games/how-machines-play.html