The Life of Games

Proud fathers Richard Guy, John Conway, and Elwyn Berlekamp holding their mathematical offspring.

(Note: I wasn’t planning on talking about surreal numbers quite this early in the tour; I thought I’d show you some other sights first, and look at lots of other ways mathematicians have played with the concept of infinity over the centuries, and then finally, five or ten years from now, show you this amazing mix of finite, infinitesimal, and infinite numbers that we call the surreal number system, which grew out Berlekamp, Conway and Guy’s investigations of games. That was my plan. But this turned out to be the summer of Conway, thanks to a new biography, and the summer of Berlekamp-Conway-and-Guy, thanks to a conference that just took place, and I couldn’t resist the opportunity for a tie-in. So here goes: …)

Earlier this month I had the pleasure of attending the MOVES 2015 conference, hosted by the Museum of Mathematics.  Much of my pleasure came from watching my two young kids enjoy the presentations and the museum, and from giving them a taste of the pleasure I get from mathematics.

This year’s MOVES conference was dedicated to mathematicians Elwyn Berlekamp, John Conway, and Richard Guy, whose multi-volume work “Winning Ways for Your Mathematical Plays” was a milestone in both recreational mathematics and the theory of combinatorial games. The theory goes back over a century, to Charles L. Bouton’s theory of a preexisting game he named Nim, and to the generalization of this theory by Roland P. Sprague and P. M. Grundy (a topic I’ll treat another time). But the subject turned in a new direction when Berlekamp, Conway and Guy began talking with one another about games back in the late 1960s. Conway gave a preliminary account of their new approach to games, focusing on those aspects he found most charming, in a short unpublished manuscript called “All Numbers Great and Small”. The 13-page write-up was a far cry from the “Lemma: … Proof: … Lemma: … Proof: … Theorem: … Proof: …” style of a traditional research article; it left lots of gaps for readers to fill in for their own edification, in keeping with the mathematician’s article of faith that the best way to learn something is to reinvent it yourself.

The manuscript inspired computer scientist and mathematician Donald Knuth to do just that, and to dub the new numbers “surreal”. He was also moved to write the novella “Surreal Numbers”, a fictionalized account of his process of reading Conway’s write-up and reconstructing the theory of surreal numbers from Conway’s hints. Knuth’s book, along with Conway’s solo monograph “On Numbers and Games” (“ONAG”) and Berlekamp, Conway and Guy’s “Winning Ways”, came on the scene during my formative years and played a big role in my early work in mathematics.  I was enthralled by Knuth’s book, but now I worry that it could give some readers a misleading sense of what math research is like; I’ll say more about that later.

Now a new book has come out that tells us what went on behind the scenes during those exciting years when the revolution in combinatorial game theory was washing over the mathematical public through Gardner’s columns and the books of Berlekamp, Conway, Guy, and Knuth; it’s Siobhan Roberts’ “Genius at Play”, an enjoyable and well-crafted biography of John Conway. Not only does it paint a vivid portrait of one of the most colorful and influential mathematicians of our day, but it provides peeks into the math that Conway and his collaborators have given us.

I’ve known Conway for over three decades, and sometime I’ll tell you a Conway story or two of my own. A tale I learned from Roberts’ book that I hadn’t heard before (but which fits in well with what I already know about him) was the tale of a vow that Conway took fairly early in his mathematical career, reminiscent of the one physicist Richard Feynman took at Cornell after the Institute for Advanced Study began trying to woo him away.  Both men, finding other people’s high expectations of them (and their own high expectations of themselves) oppressively heavy, threw off this unwanted weight in a dramatic way, by promising themselves that they would not try to do important work, but would instead follow whatever shiny objects of thought arrested their attention. In Feynman’s case, the shiny objects were spinning plates, and thinking about them led to Feynman’s work on the quantum nature of rotation of electrons and thence to quantum electrodynamics; in Conway’s case, the shiny objects were two-player games like Go.

Martin Gardner did a splendid job of describing Berlekamp, Conway and Guy’s work in his essay “Conway’s Surreal Numbers”, rounding out his picture further in the first five pages of his essay “Nothing”.  Polly Shulman covered some points that Gardner didn’t in “Infinity Plus One, and Other Surreal Numbers”, while Siobhan Roberts gives some of the back story in chapter 10 of her new book. And those who want to know even more will find tons of information in the three books I mentioned at the top of this essay, as well as others listed in the Bibliography at the bottom.

So what’s left for me to do? I’m going to take a slightly different tack and describe a simple game called Checker Stacks that illustrates us how numbers can play a role in games.  I like to think that if you traveled back in time and taught this game to mathematicians from a century ago, its inherent strategic structure would have led the mathematicians of that era to come up with surreal numbers considerably earlier. I won’t prove everything I state, but I hope I’ll whet your appetite for books like “Winning Ways” that explain why the magic of combinatorial game theory works.

CHECKERS STACKS

Checker Stacks is due to Carl Lee of the University of Kentucky; it’s his way of presenting the game of Hackenstrings, which is itself a special case of the game of Blue-Red Hackenbush, which you can read about in “Winning Ways”. In Checker Stacks, it turns out that there’s a way to “measure” (or, as we say, evaluate) complicated positions by adding together the values of simpler positions. We’ll also see that a strange notion of one number being “simpler” than another can give us a different way to evaluate positions. A variant of the game that I call Deep Checker Stacks will lead us to contemplate positions that can’t be measured by ordinary numbers. Can we find new kinds of numbers that will measure those seemingly immeasurable games? The answer is a resounding “Yes!”

Before we delve into Checker Stacks, let’s talk about the ordinary game of checkers (also known as draughts). Like most of the two-player games that people actually play, such as chess and Go, checkers doesn’t admit a simple mathematical solution — if it did, most people probably wouldn’t want to play it! Actually, checkers has been solved by computer scientist Jonathan Schaeffer, who showed that if both players play flawlessly, the game must end in a draw; his solution uses intelligently organized brute force, and unless there are hidden patterns in his exhaustive databases describing lines of play, it’s unlikely that there’s a simple algorithm for never losing at checkers. But simple mathematical ideas can still play a role in the game. For instance, one very rough way to estimate how well you’re doing in a game of checkers is to see how many pieces you’ve got on the board in comparison with your opponent. If you’re Black, and the number of Black checkers minus the number of Red checkers is 5 then (all other things being equal) you’re probably in a strong position, whereas if that difference is −5, then you’re probably in trouble. Of course this way of assigning numerical values to positions is simplistic; it ignores WHERE the checkers are on the board.

Figure 1. Making a move in Checker Stacks

Checker Stacks is a game you can play with checkers in which the dream of a complete and simple mathematical theory becomes a reality. I won’t present the full theory, or prove all the assertions I make; some of the proofs are quite subtle. My intent is to sketch the theory in broad outlines, with lots of concrete examples, in the hope of conveying the texture of the subject, with its mixture of elegance and surprise. In conformity with the convention adhered to by Berlekamp, Conway, and Guy, I call the two players Blue and Red. The game involves stackable Blue and Red checkers, and the two players take turns removing checkers from the board until one player has no remaining checkers of her color and loses the game. Unlike checkers, Checker Stacks has no grid; a position of the game is just a bunch of stacks of checkers. It doesn’t even matter how the stacks are arranged on the table. When it’s your turn to move, you remove one of the checkers of your color and, if that checker belongs to a stack and has one or more checkers above it, you remove those other higher checkers as well, regardless of their color. Figure 1 shows a Checker Stacks position involving one Blue checker and two Red checkers (a Red-Blue stack and an isolated Red checker, or RB+R for short) and shows the one possible move that Blue can make and the two possible moves that Red can make. If the game reaches a position in which there are no checkers of your color left to remove, and it’s your turn, the game is over and you lose. So Checker Stacks is essentially a game of attrition, in which you try to deplete your own resources as slowly as possible while depleting your opponent’s resources as quickly as possible.

Figure 2. Two moves, starting from R + BR + BR.

Consider the position shown in the top panel of Figure 2, consisting of an isolated Red checker (which we also think of as a stack of height 1) and two checker stacks of height 2 each containing a Blue checker supporting a Red checker: R+BR+BR. Suppose Blue plays first, and removes the bottom checker of one of the stacks of height 2 (and in the process removes the Red checker above it). Then Blue’s move leaves Red with the position R+BR, as shown in the middle panel. Now it’s Red’s turn. If Red removes the top checker of the remaining stack of type BR, then the resulting position is R+B, as shown in the bottom panel. From this point on, the players have no choices to make; Blue must remove the stack of type B (an isolated Blue checker), and then Red must remove the stack of type R (an isolated Red checker), and then Blue must lose, since no more checkers remain. Notice that I’m not saying that Red must win the game R+BR+BR when Blue goes first; only that she can win. (And indeed Red can lose, if she unwisely takes the isolated Red checker in R+BR on her first move.)

It turns out that the position shown in the top panel of Figure 2 is perfectly balanced between the two players in this war of attrition. If Blue goes first, then Red has a way to win, and vice versa (I won’t prove the second claim but you can easily check it). The two BR stacks give just as much advantage to Blue as the single isolated R checker gives to Red. That is, two BR stacks give as much advantage to Blue as a single B checker. Or putting it differently: a single BR stack is worth half as much as a B checker.

To get an intuitive handle on this surprising claim, it may help to imagine an opening position with lots of BR stacks and lots of isolated checkers of both colors, and nothing else. If both players play intelligently, the early part of the game will involve both players ignoring the isolated checkers and focusing on the BR stacks. When it’s Red’s turn, Red will choose one of those jeopardized top checkers; when it’s Blue’s turn, Blue will choose the bottom checker of a BR stack, causing the stack to disappear. When this phase of the game ends, half of those stacks will be completely gone (obliterated by Blue), while the other half will survive in the form of isolated checkers for Blue. So in the end-game, the number of extra moves Blue derives from those stacks is half the number of stacks that were there at the start. In that sense, each BR stack provides “half a move” of advantage to Blue.

VALUES OF POSITIONS

You won’t see “half moves” and “quarter moves” and so on in isolation, but if you start to combine stacks, these fractional moves can add up to something significant. If you’ve got an opening position that consists of w B stacks, x R stacks, y BR stacks, and z RB stacks, it turns out (though I won’t prove it) that you can predict who has the winning strategy just from knowing the quantity

V = (w)(1) + (x)(−1) + (y)(1/2) + (z)(−1/2).

The nature of the quantity V predicts the behavior of the game by way of what I’ll call the “fundamental trichotomy”:

• Blue has a winning strategy (regardless of whether Blue plays first or second) if V is positive,
• Red has a winning strategy (regardless of whether Red plays first or second) if V is negative, and
• the second player has a winning strategy (regardless of whether that player is Blue or Red) if V is zero.

And what is that winning strategy?  Just this: Blue should consistently choose to leave Red in the position with the largest total value (for Blue), while Red should consistently choose to leave Blue in the position with the smallest total value (for Blue). For instance, starting from the position R + BR shown in the middle panel of Figure 2, if it’s Red’s turn to move, she can either remove the isolated R checker or remove the top checker from the two-checker stack. In the first case, what’s left is the position BR, whose value is 1/2; in the second case, what’s left is the position R+B, whose total value is (−1)+(1) = 0. Since the value of R+B (namely 0) is smaller than the value of BR (namely 1/2), R+B is a worse position for Blue to be in than BR, so it’s the position that Red should choose to put Blue into. (You can check that this conclusion agrees with common sense: since Red has two possible moves, one of which is in jeopardy of being annulled by Blue and the other of which is not, Red should clearly make the jeopardized move while she still can.)

Figure 3. Values of all stacks of height 3 or less

What about stacks consisting of more than 2 checkers? It turns out, though the proof isn’t easy, that every stack can be assigned a value (a rational number whose denominator is a power of 2, in fact) in such a fashion that you can predict which player in any Checker Stacks position has the winning strategy just by adding the value of the stacks, and then invoking the fundamental trichotomy. Figure 3 shows the values of all the stacks containing three or fewer checkers. If you have a Checker Stacks position P in which all of the stacks have three or fewer checkers, then you can add up the values of the stacks to get the value V of the whole position.  If V is positive, P is a win for Blue (that is, Blue wins if Blue plays optimally), regardless of whether she goes first or second; if V is negative, P is a win for Red, regardless of whether she goes first or second; and if V is zero, P is a win for whoever goes second.  If you’re reading this essay with a friend, you might want to pause now to make up a Checker Stacks position involving stacks of height three or less and see if it plays out the way theory predicts. If you want to know the general rule for computing the value of a stack of any height (due to Berlekamp), see the Answers.

At this stage, some readers may be thinking “Okay, there are tables that list values, and there’s Berlekamp’s rule for computing values, but what is the meaning of value?” Value is a measure of Blue’s ability to postpone the moment when she runs out of moves, relative to the moment when her adversary runs out of moves. This can be a subtle issue: if Blue and Red play a game whose starting position is one BR stack in isolation, it’s hard to see Blue’s half-move advantage. It’s only when we start playing positions that involve lots of stacks, and observing which ones are wins for which player, and noticing regularities in our observations, that the notion of value starts to emerge as an organizing principle that lets us predict who’ll have a winning strategy and who won’t.

“SIMPLICITY”

Checker Stacks is an example of what combinatorial game theorists call a “cold” game: it’s a game in which, at every stage in the game, a player would be wise to pass if a genie appeared and offered the player the opportunity to pass at that moment. (It’s not obvious that Checker Stacks is a cold game, but if you let P be your favorite checker-stack, you can check that every Blue move yields a stack with smaller value than P, while every Red move yields a stack with larger value than P.) One of the beautiful things Berlekamp, Conway, and Guy found is a recursive procedure for computing the values of positions in cold games. It applies in broad generality, but we’ll just apply it to Checker Stacks. The BCG recursion gives you a way of extending the table in Figure 3 to compute the values of all the height-4 stacks, and all the height-5 stacks, and so on, as far as you care to go, or to compute values of lots of other cold games. I won’t explain why the BCG recursion works; I’ll just show you how to use it.

Before I explain the procedure in general terms, let’s see how the procedure enables us to evaluate BRRB. Blue has two options: she can take the bottom Blue checker, turning BRRB into the empty stack, or she can take the top Blue checker, turning BRRB into BRR; those two positions — the empty stack and BRR — have respective values 0 and 1/4. Meanwhile, starting from BRRB, Red has two options: she can take the bottom Red checker, yielding B, or she can take the top Red checker, yielding BR, and those two positions — B and BR — have respective values 1 and 1/2. Berlekamp, Conway and Guy now tell us that the value of BRRB is the “simplest” number that’s greater than both 0 and 1/4 but less than both 1 and 1/2, where the notion of simplicity is given by three laws:

THE THREE LAWS OF SIMPLICITY:

0. 0 is the simplest number.
1. If an interval I does not contain 0, but it does contain one or more integers, the simplest element of I is the integer in I closest to 0.
2. If an interval I does not contain any integers, the simplest element of I is the fraction in I whose denominator is the smallest possible power of two.

In our example, the simplest number that’s greater than both 0 and 1/4 and less than both 1 and 1/2 is 3/8 (apply Law #2 to the interval I = (1/4,1/2)), so the value of BRRB is 3/8.

BC&G’s recursive prescription for evaluating a position P in a cold game is: Let A be the set of values of all the positions Blue can get to from P in one move, and let B be the set of values of all the positions Red can get to from P in one move; then the value V of P is the simplest number greater than every number in A and less than every number in B.

This prescription requires some elaboration in the potentially confusing case where A or B is the empty set. To avoid a digression on the proper treatment of the empty set, I’ll just say that when A is the empty set, we should ignore the constraint that V is greater than every number in A, and that when B is the empty set, we should ignore the constraint that V is less than every number in B.

It’s entertaining to apply the BCG recursion to the stack B. The set A now is the singleton set {0} (corresponding to Blue’s move that removes the checker, leaving an empty board), and the set B is the empty set (since Red has no moves at all). So V is the simplest number that is greater than everything in A, that is, the simplest number that is greater than 0. And by Law #1 applied to the interval (0,∞), that number is 1. So the recursion tells us (in case we’ve forgotten!) that a single Blue checker has value 1.

The BCG recursion, properly interpreted, also tells us the value of the empty stack. Neither player has any available moves, so A and B are both empty, and both conditions on V are to be ignored. So V is the simplest number — period! Applying Law #0 to the interval (−∞,∞), we see that the empty stack has value 0.

DEEP CHECKER STACKS

Moving on to Deep Checker Stacks, we’ll introduce three new kinds of checkers, which we’ll call “Deep Blue”, “Deep Red”, and “Deep Purple”. In some ways, they’re like ordinary checkers; when you remove them, they go away, and so does everything above them. But what’s different is that the player who removes one of these Deep checkers can replace it by something else, namely a stack of ordinary checkers.

Red is not permitted to remove a Deep Blue checker; only Blue is. When Blue removes a Deep Blue checker she must of course remove everything that was above it, but after she does so, she has the option (which she need not exercise) of replacing it by a single (ordinary) Blue checker, or a stack of two Blue checkers, or a stack of three Blue checkers, or indeed a stack of any finite number of Blue checkers. That is, after removing the Deep Blue checker, she replaces it by a stack of n ordinary Blue checkers, for any non-negative integer n she likes.

An alternative way to picture a Deep Blue checker is as an infinitely tall stack of Blue checkers: BBBBBB… An infinite stack has no top; if you remove any checker anywhere in it, along with what’s on top of that checker, the infinite stack becomes a finite stack. Likewise, a Deep Red checker can be thought of as an infinite stack of ordinary Red checkers: RRRRRR… If you’re comfortable with this, then you’ll be comfortable with my defining a Deep Purple checker as an infinite BRBRBR… stack. But if this kind of infinity makes you nervous, here’s another way to think of a Deep Purple checker: when Blue takes a Deep Purple checker and everything above it, she must replace it by an empty stack, or a BR stack, or a BRBR stack, etc., up to any finite (even) height; whereas when Red takes a Deep Purple checker and everything above it, she must replace it by a B stack, or a BRB stack, or a BRBRB stack, etc., up to any finite (odd) height.

What can we say about the value of an isolated Deep Purple checker? In this new and unfamiliar setting, BC&G’s simplicity rule can no longer be taken for granted, but let’s see what it predicts. In combination with Berlekamp’s rule for the value of a stack, BC&G’s simplicity rule tells us that the value of the position should be the simplest number that’s greater than all of the numbers
0, 1/2, 5/8, 21/32, …
(that’s 0, 0.1, 0.101, 0.10101, … in binary) and less than all of the numbers
1, 3/4, 11/16, 43/64, …
(that’s 1, 0.11, 0.1011, 0.101011, … in binary). As it happens, there’s exactly one such real number, namely 2/3.  And indeed it can be shown that BRBRBR… + BRBRBR… + BRBRBR… + R + R is a second-player win, consistent with the prediction of the fundamental trichotomy (since (2/3) + (2/3) + (2/3) + (−1) + (−1) = 0).

Figure 4. The Deep position BBBB. . . + R + R + R

What about a Deep Blue checker? If we try to incorporate it into our theory of games and values, we run into trouble: a Deep Blue checker appears to have value bigger than n for every integer n. To see this, restrict to the case where n is positive, and consider a position P consisting of one Deep Blue checker and n Red checkers, having value (1)(ω) + (n)(−1) = ω − n, where ω denotes the value of a Deep Blue checker. (Figure 4 shows this position when n = 3.) There’s a simple winning strategy for Blue: when she makes her first move, she should replace the Deep Blue checker by a stack of n+1 ordinary Blue checkers. Since P is a win for Blue, its value ω − n needs to be positive if we’re going to preserve the fundamental trichotomy. That is, ω − n is positive for every positive integer n; that is, ω > n for every positive integer n. So if value is to make any kind of sense at all in this context, the value of BBBB… must be greater than every positive integer.

Figure 5. The Deep position BRRR. . . + BRRR. . . + BRRR. . . + R

What about a two-checker stack consisting of an ordinary Blue checker on the bottom and a Deep Red checker on the top (BRRRR…)? The fundamental trichotomy predicts that its value (call it ɛ) is positive, since the position is a Blue win; that is, starting from this position, Blue has a way to win, regardless of who plays first. But it also appears that the value of BRRRR… must be smaller than the reciprocal of every positive integer. To see this, consider a position P consisting of n BRRRR… stacks along with a single Red checker, having value (n)(ɛ) + (1)(−1) = nɛ − 1. (Figure 5 shows this position when n = 3.) It’s easy for Red to win this game, regardless of whether she goes first or second, as long as she keeps two directives in mind: never touch the isolated Red checker unless and until it’s the only checker remaining on the board, and after removing a Deep Red checker, replace it by n ordinary Red checkers.. So ɛ, in addition to having the property that ɛ > 0, should have the property that for all positive integers n, nɛ − 1 < 0; that is, nɛ < 1; that is, ɛ < 1/n. So if value is to make sense in this context, the value of BRRRR… must be positive but less than the reciprocal of every positive integer.

We saw before that if we allow Deep Purple checkers, we’ll see positions with values like 2/3 that don’t turn up for ordinary Checker Stacks positions. Now we see that if we allow Deep Blue and Deep Red checkers in our game, and we want a quasi-numerical way to assess the strength of a position for Blue, we’re going to need values like ω that are infinite and other values like ɛ that are infinitesimal. And we don’t just want these values to be isolated specimens; we want them to combine with one another in the sorts of ways that ordinary numbers do.

SURREAL VALUES FOR GAMES

Conway’s system of surreal numbers gives us exactly what we want. In addition to ordinary numbers like 2/3, it contains generalized “numbers” like ω and ɛ. It also comes equipped with operations analogous to addition, subtraction, multiplication, and division that satisfy the same sort of properties that the familiar operations of arithmetic do, and give the expected answers when they’re applied to ordinary real numbers. I won’t tell you how multiplication of surreal numbers is defined, but I can tell you that the infinitesimal surreal number ɛ that we’ve just met turns out to be the reciprocal of the infinite surreal number ω. In addition to containing ω and ɛ=1/ω, the surreal number system contains

π ω² − sqrt(ω) + ω^ω

and all sorts of things even weirder than that. Sachi Hashimoto, a student at Canada/USA Mathcamp, quoted by Roberts, said “The first time you see surreal numbers, you break, you just break; your brain cracks open.”

But what are the surreal numbers? There are several valid ways to answer this question. One approach uses “Gonshor sign expansions”, as described in Polly Shulman’s article (I find these expansions somewhat similar in spirit to the Kaufman decimals). Conway came up with a genetic approach, in which we build up complex games from simple ones, starting with the simplest game of all, namely, the game in which there are no moves available to either player. That simplest game of all games is born on day 0, and from it other games are born, on day 1, day 2, etc. The creation of new games from old occurs by a process of polyamorous “mating” wherein one set of numbers (call it A) mates with another set of numbers (call it B) having the property that every element of A is less than every element of B. If there are no numbers yet that are squeezed between the sets A and B, the mating of the two sets gives rise to such a number, in fact, the simplest such number, which we denote by {A|B}. For instance, when we mate the set A = {0, 1/2, 5/8, 21/32, …} with the set B = {1, 3/4, 11/16, 43/64, …}, we get the number 2/3; when we mate the set A = {0} with the set B = {1, 1/2, 1/4, 1/8, …}, we get the infinitesimal surreal number ɛ; and when we mate the set A = {0, 1, 2, 3, …} with the empty set B = {}, we get the infinite surreal number ω. Under this dynamic viewpoint, “simplest” means “earliest born”. Conway may be better known to recreational mathematicians for other things, but I think that his discovery of the “life” of games is his deepest contribution to human knowledge.

In the surreal numbers, the simplicity rule and the fundamental trichotomy still apply, but not in the way they did before. Before, they operated against the backdrop of the real number system. Now we use them to build up a number system that includes the real numbers and much, much more. The simplicity rule and the fundamental trichotomy, suitably reconfigured as something more like axioms than theorems, guide the expansion of the surreal universe. Metaphorically, it’s the difference between an ordinary explosion that spreads matter through space and the Big Bang that actually created space as it went.

It’s easy to see how Knuth saw in Conway’s theory a metaphor for the creation of the cosmos, much as Genesis was for the ancient Hebrews, and created a parable in which Conway’s rules are written on stone. I was smitten with Knuth’s book, and still am struck by the originality of Knuth’s approach to mathematical exposition and the verve with which he carried it off. But something I didn’t realize at the time, and am acutely aware of now, is that most math research is not like what protagonists Alice and Bill and their real-life counterpart Knuth did (working out the consequences of axioms and definitions obtained from a chiseled stone and an unpublished manuscript, respectively). Most mathematicians don’t start from bare axioms; they work in established bodies of knowledge where there are already theorems sitting around that they build upon. (So many theorems, in fact, that it can take years to learn the rudiments of a subfield — which explains why most mathematicians make important contributions in only one or two subfields.)

And even Conway, who more or less built his theory from the ground up, didn’t do what Alice and Bill did, because unlike Alice and Bill, Conway couldn’t consult any oracular stones to see what the axioms and definitions should be; he had to work it out by a process of trial and error, guided by experiment and a sense of analogy.

There’s a lot you can discover by exploring Deep Checker Stacks, but I’ll close this puzzle with one question: If we set up a game whose initial position has two Deep Blue checkers stacked one atop the other, along with two isolated Deep Red checkers, who has the winning strategy? See the Answers.

OTHER GAMES

The surreal number system, defined in the strictest sense, has a major limitation from the point of view of game theory: it only applies to cold games. What if we allowed a third color of checker — Green, say — with the property that a Green checker (and whatever lies above it) can be removed by either player? Then the theory of values of games hits a major snag: it is no longer possible to assign a value to each stack in such a fashion that fundamental trichotomy will apply. The easiest way to see this is to consider the position P consisting of a single Green checker. This position is not a win for Blue, nor is it a win for Red, nor is it a win for the second player; it’s a win for the first player! So if we’re going to expand our mathematical theory of games to handle this variant of Checker Stacks, we’re going to have to allow values that aren’t positive, aren’t negative, and aren’t zero, and we’ll have to abandon the fundamental trichotomy. (We were going to have to do this sooner or later: after all, not all games are games of attrition!)

This impasse may put you in mind of imaginary numbers, which are neither positive nor negative nor zero, but in fact what we need here are nimbers, which deserve an essay of their own (one I’ll write sometime in the future). Nimbers are values of games that are “impartial”: moves available to one player are available to the other as well. Gardner’s essay “Nim and Hackenbush” gives an excellent treatment of the basics.

The Berlekamp-Conway-Guy theory is an artful melding of the theory of surreal numbers (applicable to cold games) and the theory of nimbers (applicable to impartial games like Nim).  Actual games that people play, like chess, are neither impartial (I can’t move your rook even though you can!) nor cold (if you’re about to put me in checkmate, you’d be a fool to take the genie’s offer and pass instead!). Yet it turns out that by combining ideas that work out elegantly for the surreals with other ideas that work out elegantly for nimbers, one gets a flexible theory that can be applied to the late endgame of Go, as described in Berlekamp and Wolfe’s book “Mathematical Go: Chilling Gets the Last Point”, as well as to certain chess endgames.

I should stress that Berlekamp, Conway and Guy didn’t start their investigation with games like Checker Stacks or Deep Checker Stacks; they started with the game of Go, in which the mathematical structure is hidden under many layers. Their genius lay in seeing the bones of a theory beneath the skin and muscles of the game, following clues provided by other mathematical games that had been studied in isolation from one another, and finding a tent big enough for them all to fit under.

A game that beautifully illustrates, under one small tent, many of the ideas that star in the big tent is Conway’s game of Hotchpotch Hackenbush. I don’t know if the comprehensive library of unwritten novels (described near the end of Lev Grossman’s The Magician’s Land) has room for mathematical novellas, but if it does, I hope it contains a different book that Knuth could have written, set in a universe in which Bouton, Sprague, Grundy, Berlekamp, Conway and Guy never existed; in this novel, three people gradually invent, in tandem, the game of Hotchpotch Hackenbush and the theory that governs the game, by playing games, making conjectures, and seeking proofs. (This kind of feedback loop between theory and practice is reminiscent of a motto often attributed to Knuth: “The best theory is motivated by practice, and the best practice is motivated by theory.”) Perhaps for added drama one of the three is a big fan of all things infinite, and wants the theory to apply to infinite Hotchpotch Hackenbush pictures, while another, more hard-headed and practical member of the trio insists on the primacy of those games that are playable by finite humans, and the two contend for the “soul” of the third. And for even greater realism, the three aren’t on a remote island; they’ve got busy lives in different places, and their conflicting attempts to construct a beautiful, practical theory (“More beautiful!” “No, more practical!”) are further complicated by busy non-mathematical lives.

THE LARGER PICTURE

Might there be more to the surreal numbers than fun and games? Some would object to the question’s tacit suggestion that the study of games is somehow frivolous. Berlekamp, who has done work in engineering and coding theory and knows applied mathematics when he sees it (or creates it!), insists that combinatorial game theory is serious applied mathematics. But I think you know what I mean. Do surreal numbers have applications that are less, well, fun-looking, and might appeal to people who would never deign to play a game?

The late Princeton University mathematician Martin Kruskal, who made his reputation in the theory of solitons (an important modern topic in the theory of differential equations), nursed the hope that the surreal numbers held the key to the proper interpretation of certain kinds of formulas in mathematics called asymptotic expansions. This is a topic I won’t say more about here, other than referring you to Shulman’s article.

In a more theoretical vein, it might be hoped that surreal numbers would play a role in the foundations of mathematics. You may have seen ω before, as one of Georg Cantor’s ordinal infinities. In fact, all of Cantor’s ordinals 0, 1, 2, … ω, ω+1, ω+2, … ω×2, ω×2+1, … ω×3, … ω², … ω³, … ω^ω, … ω^ωω, … are part of Conway’s system. Conway’s way of building new numbers from old includes, as a special case, Cantor’s way of creating ever-larger ordinals. On the other hand, Conway’s construction of 2/3 as {A|B} with A = {0, 1/2, 5/8, 21/32, …} and B = {1, 3/4, 11/16, 43/64, …} is highly reminiscent of Richard Dedekind’s way of building real numbers by cutting the rational number line into pieces. These are both topics I’ll come back to on another occasion. For now, I’ll say that both Cantor’s construction and Dedekind’s were important contributions to the foundations of mathematics. Conway’s theory unifies the “further up” of Cantor with the “further in” of Dedekind in a profound way, and this unification gave Conway and others the strong feeling that, with the discovery of the surreal numbers, we were really onto something big.

Back in the 70s and 80s, it seemed conceivable that surreal numbers would revolutionize mathematics, and have impact on seemingly unrelated branches of pure and applied mathematics, the way complex numbers did. But this hasn’t happened yet. The theory of surreal numbers is beautiful, spacious, and philosophically compelling, but just as it harbors concepts (like its notion of simplicity) that seem unconnected to the mathematical mainstream, it has proved difficult to import into surreal mathematics some mainstream topics like differential equations. There’s a kind of two-way language barrier separating surreal mathematics from the bulk of what mathematicians have been working on over the past several centuries. For instance: In “real” (i.e. standard) mathematics, if you want to define what 2^x means for all real numbers x, you use calculus to define the “natural” logarithm function and the “natural” exponential function exp x = e^x (where e = 2.718…) and then define 2^x  as exp cx where c is the natural logarithm of 2. But in surreal mathematics, calculus doesn’t work in the usual way, and defining e^x for all surreal numbers x so that the function has all the desired properties turns out to be a tricky matter. And yet it turns out to be quite easy to define ω^x for all surreal numbers x (where ω is the value of a Deep Blue checker). That is, the most “natural” exponential function in the surreal number system is a form of exponential function that has no counterpart in the real number system.

Is there some way to get “real” mathematics (which includes the complex numbers, by the way!) and surreal mathematics to interact productively, to get results that neither style of mathematics would yield on its own? That’s certainly how many success stories in mathematics go (stories about the success of ideas, not people!). It’s possible that surreal numbers will hold the key to some contemporary mathematical mysteries. Philip Ehrlich, who along with Norman Alling did a lot of work over the past few decades to develop the field of surreal analysis, has had recent successes in collaboration with Ovidiu Costin and Harvey Friedman in adapting calculus to the surreal numbers, and thinks that applications are not far off. Conway’s Princeton colleague Peter Sarnak (quoted by Robert in her book) says “The surreal numbers will be applied. It’s just a question of how, and when.”

I mentioned above that Checker Stacks is a variant of the game Blue-Red Hackenbush, described in ONAG and Winning Ways. If you want to play Hackenbush against a computer, and you have an iPad, try http://www.hakenbush.com [sic]. It would be great to have a program that plays Checkers Stacks that runs on any modern browser on any modern platform; if any reader creates such software, I’d be glad to include a link to it.

Next month (September 17): Why .999… equals 1, why it’s less than 1, and why it doesn’t exist.

This article was written with help from Elwyn Berlekamp, Philip Ehrlich, Richard Guy, David Jacobi, Carl Lee,  Joe Malkevitch, Siobhan Roberts, Jonathan Schaeffer, James Tanton, and Glen Whitney.

ANSWERS

1. Here is Berlekamp’s method for computing the value of a checker stack whose bottom checker is Blue and that contains at least one Red checker. Write out the stack symbolically, as a string of B‘s and R‘s. Replace the first occurrence of BR in the string by a dot, replace all other B‘s by 1’s and all other R‘s by 0’s, and stick a 1 at the end. Now interpret this new string in a curious hybrid fashion: everything before the dot should be interpreted as a unary integer, while everything after the dot should be interpreted as a binary fraction. For instance, BBBRBBR becomes BB.BBR which becomes 11.1101, or two plus thirteen sixteenths.

2. The position with four Deep checkers (two stacked Deep Blue checkers and two isolated Deep Red checkers) turns out to be a win for the second player. First take the case where Blue plays first. If Blue takes the bottom Deep Blue checker, then there’ll be only finitely many ordinary Blue checkers on the board along with two Deep Red checkers, and it’s clear that Red can win. If Blue takes the top Deep Blue checker and replaces it by n ordinary Blue checkers, Red can replace one of her Deep Red checkers by n ordinary Red checkers, and it’s not hard to continue the analysis to see that Red can win in this case as well by mimicking her opponent. Now take the case where Red plays first. Red must turn one of her Deep stacks into a finite stack of ordinary checkers; Blue can mimic Red, using her top Deep checker. When (as must eventually happen) Red removes her other Deep stack, leaving her with no Deep checkers and only finitely many ordinary ones, Blue can use his bottom Deep checker to leave himself with a surplus of ordinary checkers that can defeat Red’s supply.

The general theory of Blue-Red Hackenbush gives us a quick way to see who wins without going through the tedium of constructing a strategy, using just simple surreal arithmetic: A stack of two Deep Blue checkers has value ω×2, and a Deep Red checker has value −ω. The value of the initial position is therefore (ω×2)+(−ω)+(−ω) = 0, which indicates a second player win.

BIBLIOGRAPHY

Michael H. Albert, Richard J. Nowakowski, and David Wolfe, “Lessons in Play: An Introduction to Combinatorial Game Theory”, 2007.

Elwyn Berlekamp, John Conway, and Richard Guy,  “Winning Ways for Your Mathematical Plays”, 1982.

Elwyn Berlekamp and David Wolfe, “Mathematical Go: Chilling Gets the Last Point”, 1994.

Elwyn Berlekamp, “The Dot and Boxes Game: Sophisticated Child’s Play”, 2000.

Charles L. Bouton, Nim, A Game with a Complete Mathematical Theory, Annals of Mathematics, 2nd Series, Vol. 3, No. 1/4 (1901-1902), pp. 35-39. Available online.

John Conway,  “On Numbers and Games”, 1976.

John Conway, “All Games Bright and Beautiful”,  American Mathematical Monthly, Vol. 86, No. 6, June-July, 1977, pp. 417-434. Available online.

David Eppstein, Combinatorial game theory resource page.

Martin Gardner, “Conway’s Surreal Numbers”, chapter 4, pages 49-62 in “Penrose Tiles to Trapdoor Ciphers”.

Martin Gardner, “Nim and Hackenbush”, chapter 14, pages 142-151 of “Wheels, Life, and Other Mathematical Amusements”.

Martin Gardner, “Nothing”, chapter 1, pages 15-19 in “Mathematical Magic Show”.

Richard Guy, “Fair Game: How to Play Impartial Combinatorial Games”, 1989.

Donald Knuth, “Surreal Numbers”, 1974.

Joseph Malkevitch, “Combinatorial Games (Part I): The World of Piles of Stones”.

Joseph Malkevitch, “Combinatorial Games (Part II): Different Moves for Left and Right”.

Richard Nowakowski, “The History of Combinatorial Game Theory”, 2009.

Siobhan Roberts, “Genius at Play: The Curious Mind of John Horton Conway”, 2015.

Polly Shulman, “Infinity Plus One, and Other Surreal Numbers”, Discover Magazine, Dec. 1995.

Aaron Siegel, “Combinatorial Game Theory”, 2013. The Appendix contains a history of the subject.