Hex (board game)
From Academic Kids

Hex is a board game played on a hexagonal grid, usually in the shape of a 10 by 10 or a 11 by 11 rhombus. (The book A Beautiful Mind says Nash et al settled on 14 by 14 as best.)
Contents 
History
The game was invented by the Danish mathematician Piet Hein, who introduced the game in 1942 at the Niels Bohr Institute, and independently by the mathematician John Nash in the late 1940s. It became known in Denmark under the name Polygon (though Hein called it CONTACTIX); Nash's fellow players at first called the game Nash. According to Martin Gardner, some of the Princeton University students also referred to the game as John, because it was often played on the hexagonal tiles of bathroom floors. In 1952 Parker Brothers marketed a version. They called their version "Hex" and the name stuck.
Hex_game_over.png
Rules
Players have two colors, say "Red" and "Blue". (Of course, the colors are merely a convention and the actual colors vary from board to board and from version to version.) They alternate turns placing a piece of their color inside a hexagon, filling in that hexagon with their color. Red's goal is to form a red path connecting the top and bottom sides of the parallelogram, and Blue's goal is to form a path connecting the left and right sides.
In the image on left, Red moved first in this game and won.
Strategy
The game can never end in a tie, a fact found by Nash: the only way to prevent your opponent from forming a connecting path is to form a path yourself.
When the sides of the grid are equal, the game favors the first player. A standard nonconstructive strategystealing argument proves that the first player has a winning strategy. It is obvious that since hex is a finite, perfect information game which cannot end in a tie, either the first or second player has a winning strategy. Note that an extra move for either player in any position can only improve that player's position. Therefore, if the second player has a winning strategy, the first player could steal it by making an irrelevant move and then follow the second player's strategy. If the strategy ever called for moving on the square already chosen, the first player makes another random move. This ensures a first player win.
There are two ways to make the game fairer. One way is to make the second player's sides closer together, playing on a parallelogram rather than a rhombus. However, using a simple pairing strategy, this has been proven to result in a win for the second player.
A fairer way is to use the pie rule, by which the second player has the option of swapping colors after the first player makes the first move, or first three moves, thus encouraging the first player to even out the game. Nowadays, in most online sites, the swap rule is the default, with the swap made after only one move. In theory the swap rule ensures that the second player has a winning strategy, but in practice the first player can choose a hex for which no winning strategy is known.
Cameron Browne wrote a book entitled Hex Strategy: Making the Right Connections, which covers Hex strategy at a greater level of detail than any preceding work. However, some hex players feel that this book contains many factual errors and advocates questionable strategies. Another book, to be written by Jack van Rijswijck and Ryan Hayward, was put on hold soon after the publication of Hex Strategy; it was to have a more mathematical bent than the somewhat conversational tone of Browne's book.
In computational complexity theory, Hex has been proven to be PSPACEcomplete. (Note that a number of other abstract strategy games, such as checkers, chess and go, are EXPTIMEcomplete.)
Templates
An important concept in the theory of hex is the template. A template is a subset of the hexes with an assignment of red, blue or empty to each hex with two red edges set apart such that if blue were to move first, red would still be able to connect both red edges no matter what blue does.
Variants
Blockbusters
Hex had an incarnation as the question board from the television game show Blockbusters. In order to play a "move", contestants had to answer a question correctly. The board had 5 alternating columns of 4 hexagons; the solo player could connect toptobottom in 4 moves, while the team of two could connect lefttoright in 5 moves.
The game of Y
Y is considered by some to be superior to Hex, because Hex is a subset of Y.
The Shannon Switching game
See Shannon switching game. Unlike Hex, this isn't PSPACE hard.
Havannah
Havannah is a similar game to hex.
See also:
External links and references
General links
 HexWiki (http://www.hexwiki.org/)
 Jack van Rijswijck's Hex page (http://www.cs.ualberta.ca/~javhar/hex/) includes proof that a draw is impossible.
 Hex game information center (http://www.microring.it/hex/) (has not been updated since 1999)
 basic strategy well explained (http://www.mazeworks.com/hex7/about/basics1.htm)
 Cameron's Hex Page (http://members.optusnet.com.au/cameronb/hex1.htm) Author Cameron Browne explains
 Thesis on Hex (http://maarup.net/thomas/hex/) Excerpts from a thesis on Hex currently being written
 The Game of Hex  Templates (http://www.drking.plus.com/hexagons/hex/templates.html) A catalogue of edge connection templates
 Hex (http://www.f.kth.se/~rydh/Hex/) Has some good information on strategy
 Hex Theory and Proofs Project (http://hex.kosmanor.com/hex/theory.html)
 Hex Can't End in a Draw (http://www.cuttheknot.org/Curriculum/Games/HexTheory.shtml) (requires Java)
Computer hex
 Six (http://six.retes.hu/) The strongest Hex program out there (for Linux/Un*x).
 Hexy (http://home.earthlink.net/~vanshel/) The second strongest program out there. It's for Microsoft Windows and there are some publications on Hex algorithms on this site. Some of the papers there might be of interest to mathematicians willing to make a mathematical analysis of Hex.
 Queenbee (http://www.cs.ualberta.ca/~queenbee/)
 International Computer Games Association  Hex Information (http://www.cs.unimaas.nl/icga/games/hex/)
Playing on the internet
 Kurnik (http://www.kurnik.org/), currently the best realtime server for Hex
 Little Golem (http://www.littlegolem.net/), a popular turnbased server with 13x13 and 19x19 Hex
 PBMserv (http://www.gamerz.net/pbmserv/), an email game server, any size Hex board supported
Solutions for small board sizes
 7x7, 8x8 and 9x9 solutions (http://www.ee.umanitoba.ca/~jingyang/) by Jing Yang of the University of Manitoba
Game database
 OHex (http://www.kosmanor.com/hexbin/board) This is an online database of Hex games. But please take it with a grain of salt since the database contains quite a number of mediocre games. There's also a Hex mailing list you can join there.
Hex tools
 Jhex (http://canyon23.net/jgame/README_hex.html) Jhex is a game tree editor for hex with many features, written in Java. It's useful for analyzing hex strategy. It also contains a fairly large downloadable database of Hex games.
 Jon's Hex Board (http://folk.uio.no/jkleiser/hex/hexboard.html) How to make a Hex board in HTML
Physical hex sets
 Hex Boards (http://www.nada.kth.se/~rydh/Hex/hexPics.html) Photos of wooden boards
 Miguel Garcia's Hex Board Gallery (http://members.fortunecity.es/zeycus/hexboard/hexboard.html) Photos of a Hex board made with steel nuts and ballbearings
 Making A Hex Game With A WhiteErase Board and Magnets (http://gregconquest.com/hex.html)
Book
 Browne, Cameron. Hex Strategy: Making the Right Connections. ISBN 1568811179