Archive

A Beautiful Game

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. 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.”

Sylvia Nasar, "A Beautiful Mind"

John Forbes Nash Jr would go on to make major advances in the fields of economics and mathematics, but his invention of this game was his first real intellectual contribution.

The game board consists of an 11 × 11 grid of hexagons with two white and two black sides. Two players (white and black) take turns placing a stone on the board. The goal is to be the first player to connect both his sides.

The interesting thing about "Nash" is that not only is it fun to play, it is also easy to prove things about it. This is unusual. Normally, games which are fun to play are hard to reason about (like chess). And games which are easy to reason about are not that much fun to play (like tic-tac-toe).

Nash was able to prove two things about his game. Firstly, that it cannot end in a draw. And secondly, that the first player can always win if he doesn’t make any mistakes.

Nash used a simple yet ingenious topological argument to prove that the game cannot end in a draw. And that therefore one of the two players must have a winning strategy (Zermelo's Theorem). He then showed that if the second player had a winning strategy, then the first player could “steal” that strategy by placing his first stone on a random hexagon on the board, thereby effectively making himself the second player.