A machine that knew one theorem

One of the first machines built to play a game against the public played Nim. It was built at Westinghouse by Edward Condon with two engineers, Gerald Tawney and Willard Derr, patented in 1940, and shown that year at the New York World’s Fair, where visitors sat down in front of four rows of lamps and took turns with it putting lamps out. Its builders reported that it played around a hundred thousand games there and won about nine in ten. It is remembered as a curiosity, a large cabinet of relays doing arithmetic in public eight years before anybody ran a program on a stored-program computer.

It is also a complete object, which almost nothing else in the history of this subject is. Four rows of up to seven lamps is 4,096 positions, and every one of them can be looked at. So the machine’s knowledge, its record and the decisions its builders had to make without any theorem to help them can all be measured rather than described, and the measurements say something the anecdote does not: the famous number is a fact about the people who sat down to play.

Everything it knew was Bouton #

The game is ordinary Nim. On a turn a player chooses one row and puts out any number of its lamps, from one to all of them, and the player who puts out the last lamp wins — which is the normal-play convention, the one under which the player unable to move loses. Four rows of up to seven lamps is the board every account of the machine describes.

Bouton’s theorem of 1901 settles every position of that game, and the picture his proof leaves behind is the one drawn above: columns of bits, each of which has to cancel. Write each row’s size in binary and add the columns without carrying — the nim-sum. A position is lost for the player about to move exactly when the nim-sum is nought. From any other position there is a move to one where it is nought: find the highest bit set in the sum, pick a row with that bit set, and cut it to its own size exclusive-or the sum, which is smaller because the top bit goes.

That is the whole of what the machine had to know, and the figure above is the whole of what it had to do. For rows of 7, 5, 3 and 2 the columns read 111, 101, 011 and 010; the fours column holds two ones and cancels, the twos column holds three and the units column three, so the sum is 011. The top bit of that sum is the twos, three rows carry it, and each of the three can be cut to a size that makes every column even. Any of the three wins. The machine needed only one — and since every impartial game is a Nim heap, the same one-line decision would have played any impartial game whose rows could be valued. The choice among them turns out not to matter to anything measured here — the visitor’s behaviour depends on the position in front of the visitor, not on how it was reached.

The shape of that computation is what made the machine possible in 1940. It is not a search. There is no look-ahead, no table of positions and no memory of how the board came to be as it is — which is the sense of what a strategy has to remember at its smallest: nothing at all, where some games need one bit of memory and most need far more. Every decision is a fixed function of the twelve bits on the board, computed in the same way whatever they are, and a fixed function of a dozen bits is exactly what a cabinet of relays can compute. A game that needed search would have needed a machine that did not yet exist.

That is the first connection worth drawing, because it runs against the usual story. The machine is often described as a precursor of game-playing programs, and in one sense it is. In the sense that matters it is their opposite. Every program that has played a game well since has done it by searching a tree, pruning it and evaluating what is left, and the cost of that search is the whole engineering problem. The first machine to play well did it by knowing a theorem that made the tree irrelevant, which very few games have ever allowed: Nim is almost alone among games people actually play in having a winning rule that is a fixed function of the board.

One position in eight is lost #

The first thing a complete object allows is a count of what the machine is up against.

The count of 512 needs no search. Choose the first three rows freely — eight sizes each, 512 ways — and the nim-sum of the four rows is nought for exactly one size of the fourth, the exclusive-or of the other three. That size is always a legal row, because the exclusive-or of numbers below eight is below eight. So every choice of three rows extends to exactly one loss, and there are 8 × 8 × 8 of them: one position in eight, on the nose. The census confirms the count and adds the pattern the argument predicts, that no loss has an odd number of lamps lit. A board with an odd total always has a winning move, and whoever sits down to one with the move is ahead.

The unordered count is the figure a visitor would recognise, because a visitor describes a board as “a one, a three, a five and a seven” rather than as an ordered list. There the share is a little higher, 50 of 330 or about fifteen per cent, because a lost position often repeats a row — two equal rows cancel, and a position with a repeated row has fewer orderings to be counted among the 4,096. Either way the arithmetic says the same thing: a board chosen at random is almost always a win for whoever moves first, and the machine’s record cannot be explained by its being handed lost boards to play from.

What a random move is worth #

It can be explained by the opposite: winning positions are extremely easy to throw away.

Two facts combine here. The number of winning moves is tiny and fixed: it is the number of rows carrying the nim-sum’s top bit, which is odd, and with four rows it is one or three — in this board, exactly half the winning positions each. The number of legal moves is large and grows with the board: it is simply the number of lamps lit, since a move is a choice of row and a number of lamps to leave, and every lamp position is one choice. On a board with twenty lamps lit, a visitor facing a winning position has one or three good moves among twenty.

So a visitor who moves at random — which is roughly what a visitor who does not know the theorem does in the middle of a game, when the board is too big to think through — keeps a winning position won about one time in seven. After one such slip the machine is winning, and it never slips back, because from a lost position every move leads to a winning one and the machine always has the winning reply. Nim is a game in which one mistake by the visitor is decisive and no number of mistakes by the machine is possible. The record is built from that asymmetry, and it only needs the visitor to make the mistake once in a long game. Working backwards from the empty board makes the same point in the language of the recursion: every position on the losing side has only winning positions below it, so the machine’s side of the table is a set the visitor can fall into and never climb out of.

The record is a measurement of the visitors #

That turns the reported nine in ten into a question with an answer. What would a visitor have to know for the machine to win only nine games in ten?

The model here is the simplest one that describes how people actually play small games: a visitor who plays perfectly once the board is small enough to think through, and does not before. Precisely, the visitor sees k lamps ahead — plays a winning move whenever one exists and at most k lamps are lit, and otherwise chooses among the legal moves with equal chance. With k at nought the visitor is guessing throughout; with k at twenty-eight the visitor is Bouton. The machine plays the winning move whenever there is one, and from a lost position takes one lamp from its longest row, for reasons the next section measures. Every probability is exact: for each start, the chance the machine wins is computed backwards from the empty board through all 4,096 positions, with no sampling.

The curve is flat for the first few lamps, because an endgame of four or five lamps is short and a guessing visitor has usually lost well before it is reached. It then falls steeply through the middle — each extra lamp of foresight adds a whole class of positions where the visitor stops throwing wins away — and levels out at one in eight, which is the share of starts that are lost for the visitor however well the visitor plays.

Nine in ten is the curve at seven lamps. A crowd whose members could, on average, play out a board of seven lamps or so without error and guessed before that would have produced exactly the record the machine’s builders reported. That is a plausible description of people meeting a game for the first time: the last few moves of Nim are easy to see — two equal rows cancel, a lone row should be taken whole — and the middle game is not.

A second visitor makes the same point from a different direction. Suppose a visitor knows one rule and only one, the rule most people discover within a few games: with two rows left, make them equal. That visitor plays perfectly whenever at most two rows are lit and guesses otherwise. Against that visitor the machine wins 91.1 per cent — nine in ten again. Two quite different models of what visitors knew give the reported record, and the models agree about what it means: the visitors could play the end of the game and not the middle, and the machine’s nine in ten measures the width of that middle.

A rule for losing, which the theorem does not give #

The model above made the machine take one lamp from its longest row whenever it faced a lost position. That rule is not in Bouton’s paper, and the paper cannot supply it. The theorem says a lost position has no winning move — every move leaves a nim-sum that is not nought — and against a perfect opponent that is the end of the matter. Against a visitor it is not, because the visitor may slip, and different losing moves give the visitor different chances to.

The spread is small at the extremes and real in the middle. Against a visitor who guesses throughout, the machine wins whatever it does, since the visitor will slip long before the losing position matters. Against a visitor who sees ten lamps ahead the rules differ by six points, from 77.1 per cent down to 71.2.

The best rule is the one that keeps the game long. Taking a single lamp from the longest row leaves the visitor a board almost as large as before, with as many legal moves to choose among and as few winning ones, and so as many chances to go wrong before the board shrinks to the size the visitor can see through. Clearing the longest row does the reverse: it brings the board down to a visitor’s horizon in a single move and hands over a position the visitor can play perfectly. Taking one lamp from the shortest row is nearly as good against the horizon visitors and noticeably worse against the two-row visitor, 88.4 per cent against 91.1, because shortening a short row is the fastest way to reach a board with two rows left.

The comparison that matters is with the last row. The best possible rule against each visitor was found by searching every legal move from every lost position and keeping the one with the highest chance of the visitor slipping later. It beats “take one from the longest” by less than a tenth of a percentage point against every visitor. The one decision the builders had to make without a theorem is very nearly the optimal one, and the simple reason — keep the board big, because the board’s size is the visitor’s enemy — is all the optimisation there is to do.

That is the site’s second connection, and it links the machine to a question this subject almost never asks. The theory of games is about positions with a known value, and it has nothing to say about how to lose. A program playing people spends a real share of its time in lost positions and has to choose among moves that the theory values identically — the same problem a potential that names every move runs into from the other side, where a rule is needed exactly where the theory declines to rank the options. The machine’s builders met it in 1940 and solved it by the obvious heuristic, and the heuristic is right.

The board the game is set up on #

One board is special because it is the one Nim is usually set up on: rows of one, three, five and seven. Its nim-sum is 1 ⊕ 3 ⊕ 5 ⊕ 7, which is nought.

So the usual board is lost for whoever moves first. A visitor who was offered 1 · 3 · 5 · 7 and the first move could not have beaten the machine at all, because the machine always has the reply that keeps the nim-sum at nought, and nobody at the fair could have noticed the trick unless they already knew the theorem.

Turn the order round and the machine is the one in a lost position — and it hardly matters. From 1 · 3 · 5 · 7 with the machine to move, a visitor seeing six lamps ahead loses 99.98 per cent of games, and must see thirteen of the sixteen lamps before taking even one game in ten. The full board of four sevens is lost for the mover too, and there the visitor needs twenty-five lamps of twenty-eight. The asymmetry of the previous section is at its sharpest on these boards: they are lost for the mover, but lost only to perfect play, and the machine needs the visitor to be imperfect once.

This bears on the record in a way the historical accounts leave open. They do not say, anywhere this essay can check, which boards visitors were given or who moved first. If every game had started from 1 · 3 · 5 · 7 with the visitor moving, the machine would have won every game, not nine in ten. If every game had started there with the machine moving, a nine-in-ten record would imply visitors who could play perfectly from thirteen lamps, which is not a plausible description of a crowd at a fair. The reported record is consistent with neither, and is consistent with boards varied enough that many of them were winnable for the visitor and visitors who could see the last half-dozen lamps. The arithmetic cannot say what the setup was, but it can say which setups the record rules out.

The conventions the numbers depend on #

Every figure above assumes the normal-play ending — the player who puts out the last lamp wins — which is the game Bouton solved and the one the machine is described as playing. Under the opposite ending, misère play, the losses differ on every board whose rows are all nought or one, and every percentage here would move. The board is four rows of up to seven lamps and positions are counted as ordered lists, one per assignment of lamps to rows, except where the unordered count is stated.

The visitor models are models. A visitor who plays perfectly below a threshold and uniformly at random above it is the simplest description of learning a game, and the two-row visitor is the simplest description of a rule people are known to find; neither is a claim about the visitors of 1940, of whom nothing is recorded here. The winning shares average over every non-empty start with equal weight, because the starts actually used are unknown. The machine’s winning move is always the one in the lowest-numbered row carrying the top bit; since the visitor’s behaviour depends only on the position the visitor faces, any other choice among winning moves gives the same shares.

What the arithmetic cannot recover #

The figures settle what the machine could do, what a random visitor faced and what kinds of visitor are consistent with the record. They do not settle what happened at the fair. The reported count of games and the reported share won are the builders’ own figures, and nothing here tests them; the setup — which boards, who moved first, whether visitors could choose — is not in any source this essay relies on. The internal circuit is drawn as the logic a relay machine has to implement, not as a reconstruction of the machine’s wiring, which the essay does not attempt.

What the arithmetic does recover is the direction of explanation. The number usually quoted as evidence of the machine’s skill cannot be evidence of that, because the machine’s skill is total and fixed — it plays Bouton’s theorem, and Bouton’s theorem cannot be played better. Whatever the record measures, it measures on the other side of the table.

Still open: the machine that did not know the theorem #

Nim was the right game for 1940 precisely because it needed no search, and that is also why the machine taught its builders nothing about playing games in general. The next machines to play in public did play games without a theorem. The most instructive of them played Hex, a game in which the first player is known to win and nobody can say how, and it chose its moves by measuring an electrical network wired in the shape of the board. A theorem that names no move is what such a machine was up against, and the question it poses is the same one this essay asked of the Nim machine turned inside out: when a machine plays by a rule that is not a theorem, how often is the rule right, and where does it go wrong?