TOPICS
Search

Game of Hex


HexGame

Hex is a two-player game invented by Piet Hein in 1942 while a student at Niels Bohr's Institute for Theoretical Physics, and subsequently and independently by John Nash in 1948 while a mathematics graduate student at Princeton. The game was originally called Nash or John, with the latter name at the same time crediting its inventor and referring to the fact that it was frequently played on the tiled floors of bathrooms (Gardner 1959, pp. 74-75). The name Hex was invented in 1952, when a commercial version was issued by the game company Parker Brothers.

Hex is played on a diamond-shaped board made up of hexagons. The game is usually played on a boards of size 11 on a side, for a total of 121 hexagons, as illustrated above. In the game, one player plays white pieces, while the other plays black, with play alternating between players and placement only allowed on unoccupied hexagons. Alternate sides of the board are designated white and black as shown above, and the goal of the game is to complete a chain of pieces between one player's two sides. The game cannot end in a draw since no chain can be completely blocked except by a complete chain of the opposite color.

In 1949, Nash showed using a reductio ad absurdum proof that there is always a winning strategy for the first player on an n×n board of any size. However, this provides only an existence proof. The win/lose status has been determined for every move in 7×7 hex (Hayward). A winning strategy is known for 8×8 and 9×9 boards assuming a first play at the center of the board (Yang), but not larger square boards. C. F. Shannon and E. F. Moore built a hex-playing machine that associated a two-dimensional electrical charge distribution with any given Hex position. This machine then made decisions based on properties of the corresponding potential field (Shannon 1953).

GameofHexUneven

For play on a n×(n+1) board, the second player, playing the shorter direction, can always win by playing a mirror image move, as illustrated above (Gardner 1959).

A modified version changes the rules so that the first player to form a chain loses. For this variant, there is a winning strategy for the first player if there is an even number of cells on each side; otherwise, there is a winning strategy for the second player (Gardner 1959, p. 78).


Explore with Wolfram|Alpha

References

Anshelevich, V. V. "The Game of Hex: An Automatic Theorem Proving Approach to Game Programming." http://home.earthlink.net/~vanshel/VAnshelevich-01.pdf.Arratia, A. "On the Descriptive Complexity of a Simplified Game of Hex." Log. J. IGPL 10, 105-122, 2002.Beck, A.; Bleicher, M.; and Crow, J. Excursions into Mathematics. New York: Worth, pp. 327-339, 1969.Berlekamp, E. R.; Conway, J. H; and Guy, R. K. Winning Ways for Your Mathematical Plays, Vol. 1: Adding Games. London: Academic Press, p. 218, 1982.Berlekamp, E. R.; Conway, J. H.; and Guy, R. K. Winning Ways for Your Mathematical Plays, Vol. 2: Games in Particular. London: Academic Press, pp. 679-680, 1982.Browne, C. Hex Strategy: Making the Right Connections. Wellesley, MA: A K Peters, 2000.Browne, C. Connection Games: Variations on a Theme. Wellesley, MA: A K Peters, pp. 68-77, 2005.Epstein, R. A. The Theory of Gambling and Statistical Logic. New York: Academic Press, 2009.Even, S. and Tarjan, R. "A Combinatorial Problem which Is Complete in Polynomial Space." J. ACM 23, 710-719, 1976.Gale, D. "The Game of Hex and the Brouwer Fixed-Point Theorem." Amer. Math. Monthly 86, 818-827, 1979.Gardner, M. "The Game of Hex." Ch. 8 in Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Puzzles and Games. New York: Simon and Schuster, pp. 73-83, 1959.Hayward, R. B. "7×7 Solution Proof." http://www.cs.ualberta.ca/~hayward/hex7trees/.Milnor, J. "The Game of Hex." In The Essential John Nash (Ed. H. W. Kuhn and S. Nasar). Princeton, NJ: Princeton University Press, pp. 29-33, 2002.Reisch, S. "Hex ist PSPACE-vollständig." Acta Inform. 15, 167-191, 1981.Shannon, C. E. "Computers and Automata." Proc. Inst. Radio Eng. 41, 1234-1241, 1953.Stewart, I. "Hex Marks the Spot." Sci. Amer. 283, 100-103, Sep. 2000.van Rijswijck, J. Computer Hex: Are Bees better than Fruitflies? Master's thesis. Alberta, Canada: University of Alberta, 2000.van Rijswijck, J. "Search and Evaluation in Hex." http://www.cs.ualberta.ca/~javhar/research/y-hex.pdf.Yang, J.; Liao, S.; and Pawlak, M. "New Winning and Losing Positions for 7×7 Hex." In Computers and Games: Third International Conference, CG 2002, Edmonton, Canada, July 25-27, 2002, Revised Papers (Ed. J. Schaeffer, M. Muller, and Y. Bjornsson). New York: Springer-Verlag, pp. 230-248, 2003.

Referenced on Wolfram|Alpha

Game of Hex

Cite this as:

Weisstein, Eric W. "Game of Hex." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GameofHex.html

Subject classifications