This is a belated update to my most recent post (which is not at all recent!). If you recall, we were discussing simple playground protocols for assigning players to teams. In one case the captains of teams A and B choose players in the order ABAB…; the alternative order is ABBA…. I presented some simulation results showing that the ABBA algorithm gives more evenly matched teams, at least for a certain range of parameters. Soon after that article appeared, my friend Leonardo Maffi wrote to say that he had re-implemented my program. His results agreed with mine in the ABAB case, but they were different for ABBA. Knowing from experience that Leonardo usually gets things right, I went looking for a bug in my code.

At this point the story gets a little twisted. It turns out that Leonardo had interpreted the problem differently and had therefore implemented a different algorithm; no surprise, then, that our results diverged. But that doesn’t mean my results were correct! On looking closely at my code I found that I had indeed made a clumsy mistake, which led to bogus output for the ABBA simulation. The ABBA protocol is still superior to ABAB, but by a smaller margin. For the record, here’s a corrected version of the table from the earlier post. I’ve also added results for the one remaining four-turn protocol, AABB.

                             discrepancy

   n        m       ABAB       ABBA       AABB     exact
   4        4        1.4        0.9        3.0       0.7
   6        8        3.3        1.7        9.0       0.9
   8       16        7.0        2.7       14.1       1.2
  10       32       14.5        5.5       33.0       1.7
  12       64       29.5        9.3       59.0       2.3
  14      128       59.7       18.7      129.0       3.6
  16      256      120.4       33.0      240.9       5.7
  18      512      242.5       66.3      513.1       8.4
  20     1024      487.7      120.0      975.2      14.2
  22     2048      979.4      240.8     2049.0
  24     4096     1966.1      442.8     3932.4
  26     8192     3944.2      889.9     8194.7
  28    16384     7909.3     1654.7    15821.0
  30    32768    15853.9     3317.9    32774.0
  32    65536    31768.5     6245.8    63554.1

And here is the corresponding graph:

A while ago I wrote about the playground ritual of choosing teams for a ball game. The simplest algorithm has two captains, A and B, who take turns choosing players until everyone is assigned to one team or the other. Call this the ABAB algorithm. Donald B. Aulenbach suggested a very easy modification that produces more closely matched teams. Aulenbach’s proposal is the ABBA algorithm, where A gets the first pick in the first round but B goes first in the second round, and they continue alternating in successive rounds. (Another way of describing the same process is that A begins with a single turn and thereafter both captains take two turns in a row.)

For a quantitative model of this process, let’s suppose each player’s ability is represented by an integer chosen uniformly at random from the interval 1 through m. We’ll let the total number of players, n, always be even, so that the two teams will be of the same size. After we have divvied up all the players, we sum the strengths of the two teams and calculate the discrepancy—the absolute value of the difference. Stephan Mertens of the the Otto von Guericke Universität in Magdeburg (who put me onto this problem in the first place) has shown that the expected discrepancy for the ABAB algorithm is m/2 × (n–1)/n; thus as n becomes large the discrepancy approaches m/2.

What about the ABBA algorithm? Here are some numerical results:

                         discrepancy

  n        m       ABAB     ABBA     exact

  4        4        1.4      0.7       0.7
  6        8        3.4      1.4       0.9
  8       16        7.0      2.3       1.2
 10       32       14.7      4.2       1.7
 12       64       29.2      7.2       2.3
 14      128       59.5     13.7       3.6
 16      256      122.4     23.9       5.7
 18      512      244.6     47.6       8.4
 20     1024      490.6     90.6      14.2
 22     2048      970.4    168.9
 24     4096     1944.9    315.7
 26     8192     3972.5    621.5
 28    16384     7907.9   1177.9
 30    32768    15892.6   2291.4
 32    65536    31877.2   4520.0

For each line of this table I ran the ABAB and ABBA algorithms on 1,000 randomly generated sets of numbers with the indicated values of n and m, then averaged the results. Up to n=20 I also found the optimum partitioning of each set, by a brute-force enumeration. The values of m are chosen so that log₂m = n/2. Most sets with these values of m and n have many perfect partitions, with discrepancy zero—but of course neither the ABAB nor the ABBA algorithm is guaranteed to find these ideal solutions.

Here are the same data in graphic form:

Clearly, ABBA is superior to ABAB, just as one might expect.

Questions:

1. What is the expected discrepancy of the ABBA algorithm, as a function of n and m?
2. Is ABBA the optimal algorithm of its type? Of course it is not the best of all algorithms; brute-force enumeration is better, at the cost of exponential computing time. There are also superior heuristics, but they cannot be implemented with a fixed sequence of choices, determined in advance. ABBA is a “blind” algorithm: It applies the same sequence of operations to all sets of data. Is there any other blind algorithm that outperforms it?
3. The uniform random distribution of abilities is probably not very realistic; a normal distribution would be more plausible. Would this make any difference in the performance of the algorithms?
4. Surely someone has worked on this problem before?

Going back to my own childhood, I don’t think the kids in my neighborhood ever discovered the ABBA algorithm. We did recognize the inherent advantage of choosing first, and we compensated by adopting a separate ritual to decide who got the first pick. In baseball, this involved a hand-over-hand struggle for a grip on the bat. Sometimes I think the preliminaries were more fun than the game.

A few weeks ago I commented on the discovery of some curious precursors of Sudoku, drawn up in the 1950s as designs for agricultural experiments. Now even earlier antecedants of the puzzle have been discovered by Christian Boyer, a specialist in recreational mathematics. Writing in the French magazine Pour la Science, Boyer describes and reproduces several puzzles originally published in French newspapers and magazines in the 1890s. None of these puzzles is a genuine Sudoku, but the family resemblance is striking. Several of them have nine-by-nine grids to be filled in with numbers, and a few of the nine-by-nine grids are subdivided into three-by-three blocks.

Among the many near misses, Boyer cites the puzzle shown at right as the closest known approach to a pre-invention of the Sudoku. (Image source: Christian Boyer.)

It was composed by B. Meyniel and published on 6 July 1895 in the daily newspaper La France. The instructions present the problem as a magic square, to be filled with the numbers from 1 through 9 so that all rows, all columns and all diagonals have the same sum (namely, 45). The three-by-three subgrids familiar to Sudoku players are not mentioned in the instructions or distinguished in the diagram. Nevertheless, if you try to solve the puzzle as if it were a Sudoku, you’ll find that it works: Each number from 1 through 9 appears exactly once in each subgrid. Actually, there are two such Sudoku solutions. (Meyniel’s rules exclude one of these solutions by requiring a “diabolical” magic square, in which the broken diagonals also yield the magic sum.)

Boyer presents several more fin de siecle puzzles that are Sudoku-like in one way or another. The text of his article (but not the illustrations) is available online from Pour la Science, and a supplementary document with more details and newspaper clippings is at Boyer’s web site.

The invention of the puzzle we now call Sudoku is generally credited to Howard Garns, an architect from Indianapolis. His first puzzles, which were known then as Number Place, were published in 1979. But now a curious precedent has turned up. More than 20 years earlier, in the 1950s, W. U. Behrens of Hannover, Germany, discussed very similar grids filled with numbers—not as a game or a puzzle for the amusement of newspaper readers but as a design for agricultural experiments. The connection is pointed out in a new paper (PDF) by R. A. Bailey and Peter J. Cameron of the University of London and Robert Connelly of Cornell University.

Both Sudoku and the Behrens designs trace their heritage back to Latin squares, studied by the 18th-century mathematician Leonhard Euler. In an n-by-n Latin square, each of the numbers from 1 through n appears exactly once in each column and row. A standard Sudoku puzzle is a 9-by-9 Latin square with the additional constraint that each number from 1 through 9 also appears exactly once in each of nine 3-by-3 blocks, or regions, into which the grid is subdivided.

What could this possibly have to do with agriculture? Suppose you’re testing several new seed varieties to see which ones produce the best yield. When you lay out test plots in a field, you need to be careful to avoid biases, such as putting all the samples of one variety in the area that has the most water or the richest soil. A Latin-square arrangement is a good start on such a design. With n crop varieties, an n-by-n Latin square assures that each plant type is equally represented in every column and every row, compensating for many common patterns of variation, such as a field that gets steadily moister from one side to the other. But a Latin-square arrangement cannot guarantee fairness in the presence of other patterns, such as compact patches of better or worse soil. And so Behrens proposed choosing designs from a subclass of all Latin squares, namely those in which numbers are distributed evenly not only among the columns and rows but also in predefined blocks. This subclass of Latin squares he called gerechte designs, meaning fair or impartial.

The blocks in Behrens’s designs are not always squares (obviously, an n-by-n array can be subdivided into smaller squares only if n itself is a perfect square). Here is a pattern he proposed for the case of n = 5. I have erased some of the numbers, in order to turn the diagram into an easy mini-pseudo-Sudoku puzzle:

Behrens did go on to consider the case of a 9-by-9 grid with 3-by-3 blocks, and so the following figure may well represent the first published Sudoku solutions:

The figure is taken from: Behrens, W. U. 1956. Feldversuchsanordnungen mit verbessertem Ausgleich der Bodenunterscheide. Zeitschrift für Landwirtschaftliches Versuchsund Untersuchsungswesen 2:176–193. (Scanned copy courtesy of Robert Connelly.) For the case of 4-by-4 grids, Bailey, Cameron and Connelly note an even earlier precedent: Yates, F. 1939. The comparative advantages of systematic and randomized arrangements in the design of agricultural and biological experiments. Biometrika 30:440–466.

Apart from illuminating the prehistory of Sudoku, Bailey, Cameron and Connelly also investigate a number of variations where additional symmetry conditions are imposed. For example, can you create a puzzle (on the standard Sudoku grid) where no number appears in the same relative location within any two of the nine blocks? Connelly also gives further examples and discussion at his web site. Some similar variations have also appeared on Ed Pegg’s marvelous MathPuzzle site.

In the game of Chomp, the player who moves first always has a guaranteed winning strategy. This fact might seem to take all the suspense out of the game, but it doesn’t. Except in the smallest and simplest games, no one knows which first move will lead to the guaranteed victory. For me, this situation makes playing Chomp doubly frustrating. When I go first, I have no excuse for losing—but lose I do, even to mindless players like this Java applet by Andries E. Brouwer. Some recent work has taken a new approach to understanding the difficulty of Chomp. The results won’t necessarily help you win, but they may help you understand why finding a winning move can be hard.

Chomp is played on a rectangular field divided into east-west rows and north-south columns. Initially, all the cells of this array are filled with markers such as checkers or cookies. A move consists of choosing a cell and removing the marker there as well as all the markers to the north and east of it—thus taking a rectangular bite out of the array from the northeast corner. On each turn you are required to remove at least one marker. The object is to avoid taking the last, “poisoned” marker, in the southwest corner, thereby forcing your opponent to swallow it. The game was invented in the 1970s by David Gale of the University of California at Berkeley. The name was coined by Martin Gardner.

How do we know that the first player can always win in Chomp? It’s beguilingly simple. Suppose you go first and take just the smallest legal bite—the single marker in the northeast corner. Then I respond with a countermove that turns out to be a winner—a move so good that no matter what you do in reply, you are inevitably stuck with the poison pill at the end of the game. Well, if my move is so unanswerably brilliant, why didn’t you choose it as your own? You could have won by making my move at the outset. This argument hinges on a property of Chomp that sets it apart from many other games of strategy, such as chess: If a move is legal at any time during a game of Chomp, then it is legal as an opening move.

For a few special geometries it’s easy to find a winning strategy in Chomp. For square arrays and for shallow rectangles with just one or two rows, there are simple rules for choosing a move. Long rectangles with three or more rows, however, have resisted comprehensive analysis. Computational methods have identified the winning first move for thousands of specific array shapes, but they have failed to reduce the game to any simple formula. Below are the winning first bites in a few three-row games.

Note that the shape of the chewed-off rectangle varies from case to case.

In the past few years, three-row Chomp has been studied in detail by Doron Zeilberger and his students at Rutgers University. They have found no concise magic formula for winning the game, and yet the distribution of winning and losing moves is not random, either; there are strong regularities.

Any configuration of a three-row game can be mapped to a point in a three-dimensional space. The (x, y, z) coordinates of the point represent the number of columns occupied by three, two and one markers respectively, and each point in the space can be labeled as a winner or a loser. If the game had no ordering principle whatever, then winning and losing positions would be scattered completely at random within this volume. If there were some simple rule for winning (e.g., always choose y and z so that they are prime numbers), then obvious patterns would show up in the distribution of winning points. The truth lies somewhere between these extremes.

Zeilberger and his student Xinyu Sun defined sets of points they called “instant winner” positions. These are (x, y, z) points from which you can legally move to another point with a smaller value of x that turns out to be a loser. Zeilberger and Sun discovered that along certain lines within the space—lines where x and z are held constant but y increases—the distribution of instant-winner points starts out looking random but then seems to become “ultimately periodic,” with either a constant value or a simple repetitive pattern. The ultimate periodicity of the sequences was later proved by Steven Byrnes. (Byrnes was a high school student at the time. His proof won a $100,000 science fair prize, which is a lot more than most theorems earn for their authors. Byrnes is now an undergraduate at Harvard.)

Recently, the patterns observed in the (x, y, z) space of Chomp moves have been explored further by Eric J. Friedman of Cornell University and Adam Scott Landsberg of the Claremont Colleges. Their approach is quite different from the usual methods of game theory, number theory and combinatorics. They look upon the game as if it were a problem in physics, such as trying to understand the onset of magnetization in a metal or the growth of a crystal. Although the game itself is strictly deterministic—there is no rolling of dice in Chomp—Friedman and Landsberg are led to make probabilistic predictions about the winning chances of moves in various parts of the grid. In a physical system, it’s seldom possible to know all the details about the states of individual atoms, but one can nonetheless make reliable estimates of macroscopic properties. Likewise in Chomp, the exact location of winning and losing squares varies unpredictably with any small change in the initial configuration of the array, but the overall, large-scale geometry is highly consistent.

The diagrams reproduced here (courtesy of Friedman and Landsberg) show instant-winner positions for certain three-row games. Blue points are instant winners, tan points are not. The diagrams are slices through the (x, y, z) volume, the larger panel along the plane where x=700 and the smaller at x=350. What’s notable is the similarity of the two patterns—the solid wedge at the lower left, the salt-and-pepper cone at the upper left, the series of horizontal stripes (which correspond to Zeilberger’s ultimately periodic sequences). But the similarities are only present at large scale; the detailed distribution of the various stripes and other features changes totally from one diagram to the other. Friedman and Landsberg derive a “renormalization” procedure—an idea borrowed directly from physics—that can account for this persistence of large-scale structures even as all microscopic configuration becomes thoroughly mixed up. And they give a probabilistic prediction of where a winning play is most likely to be found.

For all the statistical flavor of Friedman and Landsberg’s analysis, they have one result that is not at all probabilistic. They prove that in three-row Chomp the winning strategy is unique; for any configuration of the game, there is one and only one move guaranteed to produce a victory.

Links::

• Friedman and Landsberg (PDF via ftp)
• Zeilberger 2001 and Zeilberger 2004
• Byrnes
• Andries E. Brouwer on Chomp

Deep Background:

• Gale, David. 1974. A Curious Nim-type game. American Mathematical Monthly 81:876-879.
• Gardner, Martin. 1973. Mathematical games: Sim, Chomp and Race Track: New games for the intellect (and not for Lady Luck). Scientific American 228(1):108-115.

Finally, thanks to Steve Strogatz of Cornell for alerting me to the work of Friedman and Landsberg.