Princeton, Spring 1949
JOHN VON NEUMANN, aka the Great Man behind his back, was threading his way through the crowd, nattily dressed as always and daintily holding a cup in one hand, a saucer in the other.1 The students’ common room was unusually crowded on this late afternoon in spring. A large audience, from the Institute and physics as well as math, had turned out for So and So’s lecture and was lingering over tea. Von Neumann hovered for a moment by two rather sloppily dressed graduate students who hunched over a peculiar-looking piece of cardboard. It was a rhombus covered with hexagons. It looked like a bathroom floor. The two young men were taking turns putting down black and white go stones and had very nearly covered the entire board.
Von Neumann did not ask the students or anyone near him what game they were playing and when Tucker caught his eye momentarily, he averted his glance and quickly moved away. Later that evening, at a faculty dinner, however, he buttonholed Tucker and asked, with studied casualness, “Oh, by the way, what was it that they were playing?” “Nash,” answered Tucker, allowing the corners of his mouth to turn up ever so slightly, “Nash.”
• • •
Games were one of the charming European customs that the émigrés brought with them to Fine Hall in the 1930s. Since then one game or another has always dominated the students’ common room. Today it’s backgammon, but in the late 1940s it was Kriegspiel, go, and, after it was invented by its namesake, “Nash” or “John.”2
In Nash’s first year, there was a small clique of go players led by Ralph Fox, the genial topologist who had imported it after the war.3 Fox, who was a passionate Ping-Pong player, had achieved master status in go, not altogether surprising given his mathematical specialty. He was sufficiently expert to have been invited to Japan to play go and to have once invited a well-known Japanese master named Fukuda to play with him at Fine Hall. Fukuda, who also played against Einstein and won, obliterated Fox — to the delight of Nash and some of the other denizens of Fine.4
Kriegspiel, however, was the favorite game. A cousin of chess, Kriegspiel was a century-long fad in Prussia. William Poundstone, the author of Prisoner’s Dilemma, reports that Kriegspiel was devised as an educational game for German military schools in the eighteenth century, originally played on a board consisting of a map of the French-Belgian frontier divided into a grid of thirty-six hundred squares.5 Von Neumann, growing up in Budapest, played a version of Kriegspiel with his brothers. They drew castles, highways, and coastlines on graph paper, then advanced and retreated armies according to a set of rules. Kriegspiel turned up in the United States after the Civil War, but Poundstone quotes an army officer complaining that the game “cannot readily and intelligently be pursued by anyone who is not a mathematician.” Poundstone compared it to learning a foreign language.6 The version of Kriegspiel that surfaced in the common room in the 1930s was played with three chessboards, of which one — the only one that accurately showed the moves of both players — was visible only to the umpire. The players sat back to back and were ignorant of each other’s moves. The umpire told them only whether the moves they made were legal or illegal and also when a piece was taken.
A number of his fellow students remember thinking that Nash spent all of his time at Princeton in the common room playing board games.7 Nash, who had played chess in high school,8 played both go and Kriegspiel, the latter frequently with Steenrod or Tukey.9 He was by no means a brilliant player, but he was unusually aggressive.10 Games brought out Nash’s natural competitiveness and one-upmanship. He would stride into the common room, one former student recalls, where people were playing Kriegspiel, glance at the boards, and say offhandedly but loudly enough for the players to hear, “Oh, white really missed his opportunity when he didn’t take castle three moves ago.”11
One time, a new graduate student was playing go. “He managed not just to overwhelm me but to destroy me by pretending to have made a mistake and letting me think I was catching him in an oversight,” Hartley Rogers recalled. “This is regarded by the Japanese as a very invidious way of cheating — hamate— poker-type bluffing. That was a lesson both in how much better he was and how much better an actor.”12
• • •
That spring, Nash astounded everyone by inventing an extremely clever game that quickly took over the common room.13 Piet Hein, a Dane, had invented the game a few years before Nash, and it would be marketed by Parker Brothers in the mid-1950s as Hex. But Nash’s invention of the game appears to have been entirely independent.14
One can imagine that von Neumann felt a twinge of envy on hearing Tucker tell him that the game he was watching had been dreamed up by a first-year graduate student from West Virginia. Many great mathematicians have amused themselves by thinking up games and puzzles, of course, but it is hard to think of a single one who has invented a game that other mathematicians find intellectually intriguing and esthetically appealing yet that nonmathematical people could enjoy playing.15 The inventors of games that people do play — whether chess, Kriegspiel, or go — are, of course, lost in the mists of time. Nash’s game was his first bona fide invention and the first hard evidence of genius.
The game would likely not have appeared in a physical manifestation, in the Princeton common room or anywhere else, had it not been for another graduate student named David Gale. Gale, a New Yorker who had spent the war in the MIT Radiation Lab, was one of the first men Nash met at the Graduate College.16 Gale, Kuhn, and Tucker ran the weekly game theory seminar. Now a professor at Berkeley and the editor of a column on games and puzzles in The Mathematical Intelligencer, Gale is an aficionado of mathematical puzzles and games. Nash knew of Gale’s interest in such games since Gale was in the habit, during mealtimes at the Graduate College, of silently laying down a handful of coins in a pattern or drawing a grid and then abruptly challenging whoever was dining across the table to solve some puzzle. (This is exactly what Gale did when he saw Nash for the first time after a fifty-year hiatus at a small dinner in San Francisco to celebrate Nash’s Nobel.)17
One morning in late winter 1949, Nash literally ran into the much shorter, wiry Gale on the quadrangle inside the Graduate College. “Gale! I have an example of a game with perfect information,” he blurted out. “There’s no luck, just pure strategy. I can prove that the first player always wins, but I have no idea what his strategy will be. If the first player loses at this game, it’s because he’s made a mistake, but nobody knows what the perfect strategy is.”18
Nash’s description was somewhat elliptical, as most of his explanations were. He described the game not in terms of a rhombus with hexagonal tiles, but as a checkerboard. “Assume that two squares are adjacent if they are next to each other in a horizontal or vertical row, but also on the positive diagonal,” he said.19 Then he described what the two players were trying to do.
When Gale finally understood what Nash was trying to tell him, he was captivated. He immediately started to think about how to design an actual game board, something that had apparently never occurred to Nash, who had been toying with the idea of the game since his final year at Carnegie. “You could make it pretty, I thought.” Gale, who came from a well-to-do business family, was artistic and a bit of a tinkerer. He also thought, and said as much to Nash, that the game might have some commercial potential.
“So I made a board,” said Gale. “People played it using go stones. I left it in Fine Hall. It was the mathematical idea that counted. What I did was just design. I acted as his agent.”
“Nash” or “John” is a beautiful example of a zero-sum two-person game with perfect information in which one player always has a winning strategy.20 Chess and tic-tac-toe are also zero-sum two-person games with perfect information but they can end in draws. “Nash” is really a topological game. As Milnor describes it, an “n by n” Nash board consists of a rhombus tiled with n hexagons on each side.21 The ideal size is fourteen by fourteen. Two opposite edges of the board are colored black, the other two white. The players use black and white go stones. They take turns placing stones on the hexagons, and once played the pieces are never moved. The black player tries to construct a connected chain of black stones from the black to black boundary. The white player tries to do the same with white stones from the white to white boundary. The game continues until one or the other player succeeds. The game is entertaining because it is challenging and appealing because it involves no complex set of rules as does chess.
Nash proved that, on a symmetrical board, the first player can always win. His proof is extremely deft, “marvelously nonconstructive” in the words of Milnor, who plays it very well.22 If the board is covered by black and white pieces, there’s always a chain that connects black to black or white to white, but never both. As Gale put it, “You can walk from Mexico to Canada or swim from California to New York, but you can’t do both.”23 That explains why there can never be a draw as in tic-tac-toe. But as opposed to tic-tac-toe, even if both players try to lose, one will win, like it or not.
The game quickly swept the common room.24 It brought Nash many admirers, including the young John Milnor, who was beguiled by its ingenuity and beauty. Gale tried to sell the game. He said, “I even went to New York and showed it to several manufacturers. John and I had some agreement that I’d get a share if it sold. But they all said no, a thinking game would never sell. It was a marvelous game though. I then sent it off to Parker Brothers, but I never got a response.”25 Gale is the one who suggested the name Hex in his letter to Parker Brothers, which Parker used for the Dane’s game. (Kuhn remembers Nash describing the game to him, very likely over a meal at the college, in terms of points with six arrows emanating from each point, proof, in Kuhn’s mind, that his invention was independent of Hein’s.)26 Kuhn made a board for his children, who played it with great delight and saw to it that their children learned it too.27 Milnor still has a board that he made for his children.28 His poignant essay on Nash’s mathematical contributions for the Mathematical Intelligencer, written after Nash’s Nobel Prize, begins with a loving and detailed description of the game.