Combinatorial Game Theory
who wins, and by how much
Series

Machines — the series

2 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Four rows of lamps and three winning cuts. A Nim board of four rows of up to seven lamps, lit 7, 5, 3 and 2, with each row's binary beside it. The columns add without carrying to 011, a nim-sum of 3; the three rows carrying the middle bit each have a winning cut, to 4, to 0 and to 1, and the lamps each cut would put out are shaded.

    A machine that knew one theorem

    In 1940 a machine of relays played Nim against the public at the New York World's Fair, on four rows of up to seven lamps, and is reported to have won about nine games in ten. Everything it knew was Bouton's theorem, which is three column parities and one test per row. The record is the interesting number, and it is a measurement of the visitors rather than of the machine: against a visitor choosing at random the machine wins 98.5 per cent, and nine in ten is what a visitor earns by playing perfectly once seven lamps or fewer are lit. On the board the game is usually set up on, a visitor handed the first move cannot win at all.

    part 1 · history
  2. A Hex board read as a circuit. A three-by-four Hex board with Down to move, one Down stone and two Across stones. Each empty cell carries a disc whose area is the current through it when both players' edges are held at a unit voltage; the busiest cell is the current rule's move. The three cells that actually win for Down are shaded, and the busiest cell is not among them.

    A current through the board

    In the early 1950s Shannon and Moore built a machine that played Hex by wiring the board as a network of resistors and reading its move off the electrical potential. There is no theorem behind that rule, and on every Hex board small enough to solve it can be scored against perfect play. On boards to twelve cells it takes a winning cell on more than 98 per cent of the positions where one exists, far above chance. And it loses: every board of three rows or more it has to defend, and four by four moving first, because an opponent needs only one of the two per cent and can steer the game to it.

    part 2 · history

All series