Difference between revisions of "Hex 11x11"
Jkrabbenbos (talk | contribs) |
Jkrabbenbos (talk | contribs) |
||
| Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Games|Games]] * [[Hex 11x11|Hex 11x11]]''' | '''[[Main Page|Home]] * [[Games|Games]] * [[Hex 11x11|Hex 11x11]]''' | ||
| − | + | ==Introduction== | |
| + | |||
| + | Hex was invented by the Danish poet and mathematician Piet Hein. He introduced the game in 1942 in a lecture to students at the Niels Bohr Institute for Theoretical Physics. The game soon became popular in Denmark under the name of Polygon. It was independently re-invented by John Nash in 1948 when he was a graduate student at Princeton University. Parker Brothers marketed a version of the game in 1952 under the name Hex. | ||
| + | |||
| + | A Hex-playing analog machine was constructed by Claude Shannon and E. F. Moore in 1953, both at that time on the staff of Bell Telephone Laboratories. | ||
| + | |||
| + | The game was presented to the general public by Martin Gardner in Scientific American in 1959. | ||
| + | |||
| + | ==Rules of the Game== | ||
| + | |||
| + | Hex is a two-player game played on a rhombic board with hexagonal cells. The classic board is 11x11, but it can be any size. The 10x10, 14x14 and even 19x19 board sizes are also popular. | ||
| + | |||
| + | The players, Red and Blue, or as some prefer, Black and White, take turns placing pieces of their color on empty cells of the board. Red's objective is to connect the two opposite red sides of the board with a chain of red pieces. Blue's objective is to connect the two opposite blue sides of the board with a chain of blue pieces. | ||
| + | |||
| + | Red (Black) moves first. | ||
| + | |||
| + | Hex can never end in a draw. This follows from the fact that if all cells of the board are occupied then a winning chain for Red or Blue must necessarily exist. | ||
| + | |||
| + | The player moving first has a big advantage in Hex. In order to equalize chances, players often employ a swap rule, where the second player has the option of taking the first player's opening move. It means that the second player removes the first player's piece from the board and put his own piece in the mirror image position. | ||
| + | |||
| + | ==Complexity== | ||
| + | |||
| + | Using a "strategy stealing" argument, John Nash showed that with no swap allowed, a winning strategy exists for the first player. However, this is only a proof of existence, and it does not provide any clues that can help the first player to win. Moreover, S. Even and R. E. Tarjan (1976) showed that the problem of determining which player has a winning strategy in a generalization of Hex, called the Shannon switching game on vertices, is PSPACE complete. A couple of years later S. Reisch (1981) proved this for positions of Hex on arbitrary board sizes. | ||
Revision as of 15:38, 31 August 2019
Introduction
Hex was invented by the Danish poet and mathematician Piet Hein. He introduced the game in 1942 in a lecture to students at the Niels Bohr Institute for Theoretical Physics. The game soon became popular in Denmark under the name of Polygon. It was independently re-invented by John Nash in 1948 when he was a graduate student at Princeton University. Parker Brothers marketed a version of the game in 1952 under the name Hex.
A Hex-playing analog machine was constructed by Claude Shannon and E. F. Moore in 1953, both at that time on the staff of Bell Telephone Laboratories.
The game was presented to the general public by Martin Gardner in Scientific American in 1959.
Rules of the Game
Hex is a two-player game played on a rhombic board with hexagonal cells. The classic board is 11x11, but it can be any size. The 10x10, 14x14 and even 19x19 board sizes are also popular.
The players, Red and Blue, or as some prefer, Black and White, take turns placing pieces of their color on empty cells of the board. Red's objective is to connect the two opposite red sides of the board with a chain of red pieces. Blue's objective is to connect the two opposite blue sides of the board with a chain of blue pieces.
Red (Black) moves first.
Hex can never end in a draw. This follows from the fact that if all cells of the board are occupied then a winning chain for Red or Blue must necessarily exist.
The player moving first has a big advantage in Hex. In order to equalize chances, players often employ a swap rule, where the second player has the option of taking the first player's opening move. It means that the second player removes the first player's piece from the board and put his own piece in the mirror image position.
Complexity
Using a "strategy stealing" argument, John Nash showed that with no swap allowed, a winning strategy exists for the first player. However, this is only a proof of existence, and it does not provide any clues that can help the first player to win. Moreover, S. Even and R. E. Tarjan (1976) showed that the problem of determining which player has a winning strategy in a generalization of Hex, called the Shannon switching game on vertices, is PSPACE complete. A couple of years later S. Reisch (1981) proved this for positions of Hex on arbitrary board sizes.
