ENCYCLOPEDIA 4U .com

# Encyclopedia Home Page

 Web Encyclopedia4u.com

# Hex (board game)

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

 Table of contents 1 History 2 Rules 3 Strategy 4 Templates 5 Variants 6 See also: 7 External links and References

## History

The game was invented by the Danish mathematician Piet Hein in 1942, and independently by the mathematician John Nash in the late 1940s. It became known in Denmark under the name Polygon; 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.

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

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 non-constructive strategy-stealing argument proves that the first player has a winning strategy. It is obvious that since hex is a finite, perfect information and can not 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, this has been proven to result in a win for the second player, so it theoretically doesn't improve matters. The proof of this involves a simple pairing strategy.

A better way is to allow the second player to choose his color after the first player makes the first move, or first three moves, which encourages the first player to intentionally even out the game. See the pie rule for a more detailed discussion. Nowadays, in most online site, the swap rule is the default, with the swap made after only one move.

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.

Hex has been proven to be PSPACE hard. But don't be frightened by this. After all, checkers, chess and go are EXPTIME hard!

## 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

### The game of Y

See Y (game). It has a lot of similarities with hex.

### The Shannon Switching game

See Shannon switching game. Unlike Hex, this isn't PSPACE hard.

## External links and References

• Hex game information center
• http://members.iex.net/~rfinn/gameshlf/abstract/hex/hex.htm
• Playsite - play hex online.
• Six This is supposedly the strongest Hex program out there. Sadly, even I could beat it consistently. Hex AI still has a long long way to go... Also, this program is only for UNIX.
• Hexy The second strongest program out there. It's for 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.
• Hex Program Olympiad In light of the dismal quality of current Hex programs, why not take the challenge and participate in this annual Computer Olympiad? You can be a winner if you beat the current entries!
• OHex 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.
• Jhex Jhex is a game tree editor for hex with many features, written in Java. It also contains a fairly large downloadable database of Hex games.
• 7x7, 8x8 and 9x9 solutions by Jing Yang of the University of Manitoba
• Java applet (downloadable) It's of poor quality. I suggest Six if you have UNIX or Hexy if you have Windows instead.
• basic strategy well explained
• Browne, Cameron. Hex Strategy: Making the Right Connections. ISBN 1-56881-117-9
• Cameron's Hex Page author Cameron Browne explains
• Xah: Great Math Programs links concerning Martin Gardner and various programs.

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.

Copyright © 2005 Par Web Solutions All Rights reserved.
| Privacy

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Hex (board game)".