Hex is one name for a

board game invented independantly by a

Danish inventor, mathematician, and author called

Piet Hein in 1942, and then-

Princeton grad student and

Nobel-prizewinning mathematician

John Forbes Nash, Jr. in 1948. Hex was the name used by

Parker Brothers when they published it in 1952; in

Denmark it was first known as

Polygon, and in American university math departments it went by

Nash or, as noted above,

John.

Hex is played with two colors of stones (like go stones) on a rhombus-shaped board that is tiled with hexagons. The board can be of any size, but is almost always NxN and it is common to find 7x7 thru 14x14 boards. The game progresses much like go: two players take turns laying different-colored markers on any open spot. Each player "owns" two opposite sides of the board, and the object is to connect one's sides with a continuous chain of stones of one's color. The chain can take any path, however winding, to get from one side to the other. The game can be played on MxN boards but this tilts the odds heavily in favor of the player with the shorter distance to traverse.

Hex is a zero-sum game with perfect information, meaning one player's total gain is the other's total loss and both players know all there is to know about the state of the game. Other games of this type include go, chess, and checkers. Hex differs from these games in a very important way-- it is impossible for a game to end in a draw. Put another way, when an NxN board is filled there is always at least 1 path between parallel sides.

Based on this fact, Nash proved that the player who goes first can, with the right strategy, win the game every time. Nash's reductio ad absurdum proof can be summarized thusly: Assume there is a winning strategy for Player 2. Knowing that strategy, Player 1 could first play an arbitrary move, and thereafter play as though they were Player 2, in effect stealing Player 2's winning strategy. Player 1 would then win, contradicting the assumption; since Player 2 cannot have a winning strategy, and there can be no draw, the winning strategy must belong to Player 1. Elegant, no? However, there exists no method describing how to obtain such a strategy.

__Sources__

Better explanation of Nash's proof, and proof of the impossibility of a draw in Hex: http://www.cs.ualberta.ca/~javhar/hex/index.html

Hex FAQ: http://www.gamerz.net/~pbmserv/hex.faq.html

Hex IAQ: http://www-2.cs.cmu.edu/~hde/hex/hexfaq/

http://www.mazeworks.com/hex7/about/

http://www.abstractgamesmagazine.com/hex.html