Francais | English | Espanõl

Hex (board game)

From Wikipedia, the free encyclopedia

Jump to: navigation, search
The Game of Hex
Image:Hexyscreenshot.jpg

Hexy, a Hex computer program

Players 2

<tr><th>Age range</th><td>4+</td></tr>

Setup time 1 minute
Playing time 15 minutes (11x11 board)
Rules complexity Low
Strategy depth High
Random chance None
Skills required Tactics, strategy, position

Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as a 11x11 rhombus. Other popular dimensions are 13x13 and 19x19 as a result of the game's relationship to the older game of Go. According to the book A Beautiful Mind, John Nash (one of the game's inventors) advocated 14x14 as the optimal size.

Contents

[edit] History

The game was invented by the Danish mathematician Piet Hein, who introduced the game in 1942 at the Niels Bohr Institute, and also independently invented by the mathematician John Nash in 1947 at Princeton University . It became known in Denmark under the name Polygon (though Hein called it CON-TAC-TIX); 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 (according to some sources this was because they played the game using the mosaic of the bathroom floor). In 1952 Parker Brothers marketed a version. They called their version "Hex" and the name stuck.

Hex is an abstract strategy game that belongs to the general category of "connection" games. Other connection games include Omni, Y and Havannah. All of these games are related to the ancient Asian game of Go; Nash's version of Hex, in particular, was done as a response to Go.

[edit] Rules

Each player has an allocated color, Red and Blue being conventional. Players take turns placing a stone of their color on a single cell within the overall playing board. The goal is to form a connected path of your stones linking the opposing sides of the board marked by your colours, before your opponent connects their sides in a similar fashion. The first player to complete their connection wins the game. The four corner hexagons each belong to two sides.

Since the first player to move in Hex has a distinct advantage, the pie rule is generally implemented for fairness. This rule allows the second player to choose whether to switch positions with the first player after the first player makes the first move.

[edit] Strategy

The game can never end in a tie, a fact found by John Nash: the only way to prevent your opponent from forming a connecting path is to form a path yourself. In other words, hex is a determined game.

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 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, aka the swap 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.

[edit] Theory and Proofs

John Nash proved that a game of Hex cannot end in a tie.

In computational complexity theory, Hex has been proven to be PSPACE-complete. (Note that a number of other abstract strategy games, such as checkers, chess and go, are EXPTIME-complete.)

Hex has been solved for all symmetrical playing grids up to and including 9x9: that is, a perfect strategy has been demonstrated for the first player to move, such that they are always able to win.

An important consequence of the determinacy of hex is the Brouwer fixed-point theorem which was shown by David Gale.

[edit] 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.

[edit] Variants

[edit] 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 top-to-bottom in 4 moves, while the team of two could connect left-to-right in 5 moves.

[edit] The games of Y and Havannah

Y and Havannah are considered by some to be generalizations of Hex; they differ primarily in requiring players to connect three or more edges of a polygonal board, rather than two selected edges of a parallelogram.

[edit] Chameleon

Utilizing the same board and pieces as Hex, Chameleon gives the players the option of placing a piece of either color on the board. One player is attempting to connect the north and south edges, and the other is attempting to connect the east and west edges. The game is won when a connection between a player's goal edges is formed using either color. If a piece is placed that creates a connection between both players' goal edges (i.e. all edges are connected), the winner is the player who placed the final piece.

Chameleon is described in Cameron Browne's book Connection Games: Variations on a Theme (2005) and was independently discovered by Randy Cox and Bill Taylor.

[edit] The Shannon Switching game

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

[edit] See also

[edit] External links and references

[edit] General links

[edit] Computer hex

  • Six Strongest Hex program in the world. Linux/Unix based.
  • Hexy Second strongest Hex program, board sizes 4x4 to 11x11, swap rule allowed. Windows based.
  • Queenbee
  • Arthur's Hex Game board sizes 5x5 to 9x9 (weak play), with no swap rule implemented. Web based javascript, downloadable.
  • Hex-7 plays only 7x7 (weak play), no swap rule implemented, instead an ad-hoc rule that the first move cannot be centre square.
  • Java applet plays 3x3, 4x4, 6x6, 8x8, 11x11 (very weak play) - interesting board design.
  • ICGA - Hex Hex information from the 5th Olympiad site

[edit] Computer hex tournaments

Hex programs have featured at four Computer Olympiads:

[edit] Hex Game Servers

  • Little Golem, a popular turn-based server with 13x13 and 19x19 Hex
  • Kurnik, a realtime server with 10x10 and 13x13 Hex
  • PBMserv, an email game server, any size Hex board supported
  • Boardspace.net, another online server for Hex is Boardspace.net with 11x11, 15x15 and 19x19 Hex

[edit] Solutions for small board sizes

[edit] Tools and databases

  • Position Editor Downloadable tool for analysing Hex positions
  • Hex Analyser Similar to Position Editor
  • Jon's Hex Board How to make a Hex board in HTML
  • Jhex A Java game tree editor, useful for analyzing strategy, plus a large database of games
  • OHex An online database of (mainly mediocre) Hex games, plus a Hex mailing list you can join

[edit] Hex Boards

[edit] Book

[edit] References

  • Gale, D. (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly 86: 818-827.da:Hex (brætspil)

de:Hex (Spiel) es:Hex (juego) fr:Hex it:Hex ja:ヘックス (ボードゲーム) nl:Hex no:Hex pl:Hex (gra) zh:六連棋

Retrieved from "http://en.wikivisual.com/index.php/Hex_%28board_game%29"
Personal tools