Don Elgee, a retired teacher of mathematics and computer science from Ottawa, sends the following inquiry:

In hockey, when a team is down by a goal with about one minute to go, the goalie is pulled in favor of another offensive player. This illustrates a key point in the strategy of most games.

The object is not to maximize points for, and minimize points against; rather, it is to win or tie the game. As the game nears its conclusion the winning team plays more conservatively and the losing team more radically. But when—and to what extent—should a team change its style of play? 

To clarify the problem I tried to conceive the simplest possible example. It turned out to be much more complex than I expected.

Consider the following simple game: Two players toss a die on alternate turns. The first one to reach 100 is the winner. Players have a choice of two dice—one is normal (6, 5, 4, 3, 2, 1) and the other has faces with 6, 6, 5, 1, 1, 1. When should the losing player switch to the second die?

Is there a mathematical solution? Could you determine this by experimental computer simulation? Does the best strategy depend on the strategy the opponent is likely to choose next?

This simple problem is difficult enough, but the sports situation could better be simulated by adding a third die with 4, 4, 3, 3, 3, 3.

Has this issue been subject to mathematical study? With all the statistics used in professional sport has anyone tried to include this factor? Has it ever been incorporated in computer simulations?

Hockey is not my sport, but these are interesting questions. Inspired by Elgee’s letter, I’ve run a few of the obvious simulations. For the time being, however, I’m not going to say much about the results. What I’ve learned so far does not lead to any simple, pithy rule of thumb that a hockey coach could use to decide when to pull the goalie. Nor do I have a clear grasp of how best to play the dice game. I’m hoping someone else will offer a sharper analysis. Toward that end I have some further notes and observations.

Under the stated rules—alternating turns, with victory going to the first player who reaches 100—the privilege of moving first brings a substantial advantage. In a 100-point game with standard dice, the first player can expect to win about 55 percent of the time. If two players are tied at 99, the first to roll is definitely going to win, regardless of which die is chosen. Because of this bias, we probably need to consider different strategies for the first and second players (like white and black in a chess game). An alternative is to add a further element of randomness to the game: In each round, the player to move is determined by the toss of a fair coin.

Elgee’s two nonstandard dice have faces that sum to 20, less than the standard die’s 21. As a model of hockey tactics, this bias makes sense: It reflects the risk of leaving the goal untended. But if we ignore hockey and just consider the dice game on its own merits, it might be more interesting to explore a symmetrical contest with dice marked 6, 6, 6, 1, 1, 1 and 4, 4, 4, 3, 3, 3. Then we’d be looking at three distributions that have the same mean but different shapes.

Generalizing further, we could allow dice marked with any six non-negative integers that sum to 21. What would happen to the game if we allowed dice such as 100, -16, -16, -16, -16, -15? Or, we could allow the players to choose continuous probability density functions.

It’s easy to imagine circumstances where a “high-risk” die should be advantageous. If the score is 99 to 94, then the trailing player should be willing to accept any trade-off that improves the odds of rolling a 6; even a 6, 6, 0, 0, 0, 0 die is preferable to the standard die. Conversely, if you’re ahead near the end of the game, the “low-risk” die seems favorable. All this suggests there ought to be some fairly simple guidelines for choosing the best die in any situation. But, as Elgee noted, it’s more complicated than you might expect.

In my simulations I found that with the score tied at 94, switching to the 6, 6, 5, 1, 1, 1 die (while your opponent continues to play the standard die) yields an advantage of 2.9 percent. But when the score is 96 to 96, making the same switch produces a deficit of 3.7 percent. Interestingly, choosing the 4, 4, 3, 3, 3, 3 die brings similar results: a gain at 94 to 94 but a loss at 96 to 96. (The simulations used the coin-flip protocol, but the same kind of anomalies appear under other rules.)

It gets even more complicated. The results cited above are for players who always choose the same die, no matter what the circumstances. But Elgee’s rules allow a player to choose a different die on each roll. Presumably, players who adapt or learn will do better than any player with a fixed strategy. I find that a very simple adaptive strategy—use 6, 6, 5, 1, 1, 1 when behind, 4, 4, 3, 3, 3, 3 when ahead, and 6, 5, 4, 3, 2, 1 when the score is even—gives mostly but uniformly good results in end-game situations.

I echo Elgee’s questions about whether this problem has been analyzed previously. As it happens, I’ve been able to find a bit of literature on the original hockey issue. Tom Benjamin’s NHL Weblog has pointers to three papers published in the 1980s in Interfaces, an operations research journal. In those papers several authors—fans of rival teams—derive a formula for the optimal time to pull the goalie. (They find that coaches almost always wait too long.)

I would have thought that Elgee’s nonstandard dice would also have been investigated before. Some years ago Bradley Efron invented a wonderful set of nontransitive dice, which Martin Gardner wrote about (Scientific American, December 1970, pp. 110–114). Gardner also had a column on various kinds of rigged and trick dice (Scientific American, November 1968, pp. 140–146). A game called Piggy has certain elements reminiscent of Elgee’s game, but those elements don’t include dice that differ in variance.

Perhaps I’ve just failed to find the right search term on Google or MathSciNet, and a reader will supply a reference.

Update: Minutes after posting the above, I discovered an article by B. De Schuymera, H. De Meyera and B. De Baetsb, “Optimal strategies for equal-sum dice games” (Discrete Applied Mathematics 154 (2006) 2565–2576), that covers some of the territory. They analyze a game in which players can choose any die whose n faces have the same sum σ. But they consider only games in which players bet independently on each throw of the dice. Under these conditions, they show that with six-sided dice summing to 21, the optimal die is the standard one, with faces marked 6, 5, 4, 3, 2, 1. Again, however, if I understand correctly, this result applies only to individual throws of the die.

Among the 250 million Rubik’s cubes manufactured since 1980, how many lie abandoned in a scrambled state, having never regained their original configuration since being taken out of the box? Most of them, I would guess. Now comes word that those cubes might be restored to pristinity with a little less effort. The upper bound on the number of moves required to solve any state of Rubik’s cube has been lowered from 27 to 26. The result is reported by Daniel Kunkle and Gene Cooperman of Northeastern University in a preprint available here.

It’s well-known that Rubik’s cube isn’t really a toy or a puzzle but rather a group-theory machine in disguise. Each possible move, or twiddle—rotating a face by some multiple of 90 degrees—is a transformation that permutes the positions and orientations of the 26 “cubies.” From any position there are just 18 distinct nontrivial moves, but in various combinations they generate a total of 43,252,003,274,489,856,000 permutations. What is the maximum number of moves needed to transform any one state of the cube into any other? That’s the question Kunkle and Cooperman are addressing. In other words, they are looking for the longest shortest path.

In principle we could get the answer by exhaustive search. It would be done by constructing the “Cayley graph” for the Rubik group: a graph in which each possible configuration of the cube is represented by a node, and two nodes x and y are connected by an edge if some single move allows configuration x to be transformed into y. The most efficient solution for any state is the shortest path (i.e., sequence of edges) leading from that state to the node representing the solved state. The worst-case solution length for the entire puzzle is the maximum of the shortest solution paths for all the nodes. The Cayley graph approach was used by Cooperman and two colleagues to find the worst-case path for the 2 × 2 × 2 version of Rubik’s cube. The Cayley graph for this device has 88,179,840 nodes, and it turns out the longest paths within it have 11 steps. For the 3 × 3 × 3 cube, however, exhaustive search is just too exhausting.

To make the search feasible, Cubists have had to scale back their ambitions and accept an upper bound rather than a true maximum. First it was shown that the worst-case solution path cannot require more than 52 moves; then the bound was lowered to 30, and then 29; a year ago Silviu Radu got the number down to 27.

Kunkle and Cooperman’s strategy is to factor the problem into two pieces by segregating half-turn (180-degree) and quarter-turn (±90-degree) moves. The subgroup of states reachable by half-turn moves is quite small by Rubik group standards, with just 663,552 elements, and the number is further reduced to only 15,752 after various symmetries are eliminated. Calculating the best solution for each of these states took only about a day on an ordinary PC. The longest such paths have 13 steps.

The second phase of the analysis tackles the “cosets” of the half-turn subgroup. For each of the 663,552 positions reachable by making half-turns only, there are 65,182,537,728,000 additional positions reachable by making quarter-turn moves. Kunkle and Cooperman had to search for the longest shortest path connecting any two elements of this set. They exploited various symmetries to reduce the scope of the problem and devised fast algorithms for some of the basic steps in the calculation. Even so, they wound up running their computer program for 63 hours on 128 processors at the San Diego Supercomputer Center. At one point the data store for intermediate results ballooned to seven terabytes. At the end of the run, they found that the longest shortest path consisted of 16 moves.

Combining the two phases of this solution yields 13 moves for the half-turn part of the path and 16 moves for the coset part, for a total of 29 moves. This is not an improvement over the best existing result of 27. However, Kunkle and Cooperman found that the two-stage algorithm reports path lengths greater than 26 only for a comparative handful of states—about 14,000. By a brute-force search they were able to find solutions of length 26 or less for each of these states, and thereby established the 26-move bound overall. It’s possible that further brute-force searching will lower the limit further to 25 moves.

Other experiments done by Herbert Kociemba, Richard Korf and others have shown that most randomly selected cube states can be solved in 18 moves or less. Korf has conjectured that all configurations are solvable in about 20 steps. We’ll see whether this is true—but probably not soon.

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.