Hex Information

Topic Editor: Vadim V. Anshelevich

Contributions are welcome and the ICGA will, with permission, list contributor's names and email addresses on its Contributor's page.

SIX won the Gold Medal of the 8th Computer Olympiad in Graz.

Congratulations to Gábor Melis.

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.

Programs and Programmers

  • Mongoose by Yngvi Björnsson, Ryan Hayward, Mike Johanson, Morgan Kan, and Nathan Po. (2003)
  • Hex 7x7 and 8x8 Solutions by Jing Yang. (7x7 and 8x8. Always moves first with no swap allowed. It seemingly demonstrates the perfect play)
  • Queenbee by Jack van Rijswijck. (11x11. Applet)
  • Hex 1.0 by Sven Erik Elfgren. (1997. 7x7. Windows. Always moves first with no swap allowed. It seemingly demonstrates the perfect play)
  • Hexomania by Jörg Kienzle. (1996. 11x11. Macintosh)
  • Hex by Zhiping You. (1995. Up to 19x19. DOS)
  • Hex by Chris Lusby Taylor. (1991. Up to 14x14. Windows)

Games Databases

  • JHex by Kevin Walker.

Events

  • The 8th Computer Olympiad, Graz, November 23-27, 2003. A report by Gábor Melis and Ryan Hayward is to appear in The ICGA Journal.
  • The 5th Computer Olympiad, London, August 21-25, 2000. A report by Vadim Anshelevich is published in The ICGA Journal, 23(3), 2000, pp.181-184.

Game-playing Servers

Examples of Games

Two master-level games between human players

1.B2 2.E6 3.G6 4.G5 5.F6 6.F5 7.I4 8.I3 9.H4 10.H3 11.G4 12.G3 13.F4 14.H5 15.I5 16.H6 17.I6 18.H7 19.I7 20.H9 21.H8 22.D8 23.E9 24.F3 25.E4 26.E3 27.D4 28.D3 29.B4 30.C4 31.B5 32.C5 33.B6 34.D5 35.D6 36.B9 37.C8 38.C9 39.D7 Blue resigned 1.A2 Swap to B1 2.F5 3.F7 4.E7 5.F6 6.E6 7.D9 8.E8 9.E9 10.F8 11.F9 12.G8 13.G9 14.I8 15.H8 16.I7 17.H7 18.I6 19.H6 20.C9 21.D8 22.C8 23.D7 24.C7 25.D6 26.C6 27.D4 28.H4 29.I5 30.D5 31.E4 32.E5 33.G4 34.C3 35.E2 Red resigned



Queenbee (Red) vs. Hexy (Blue) at the 5th Computer Olympiad in London, August 24, 2000

1.B2 Swap to B2 2.F6 3.F7 4.G6 5.G7 6.C9 7.D8 8.E7 9.E9 10.C8 11.D7 12.C7 13.D5 14.C5 15.C6 16.B6 17.B7 18.D6 19.F4 20.E5 21.E4 22.H4 23.H3 24.G4 25.G3 26.I3 27.J1 28.K1 29.J2 30.K2 31.J3 32.I2 33.I1 34.K3 35.J4 36.K4 37.J5 38.K5 39.J6 40.H2 41.H1 42.G2 43.G1 44.F2 45.F1 46.K6 47.J8 48.J7 49.H8 50.I7 51.H6 52.E2 53.E1 54.C2 55.D2 56.D3 57.C3 58.B3 59.B5 60.B4 61.C4 62.I8 63.H10 64.H9 65.G10 66.I9 67.I10 68.G9 69.F10 Red resigned

Note. Due to a different implementation of the swap rule, the game shown here is the mirror image of the game played at the Olympiad.

Books and Papers

  • Hayward, R.; Björnsson, Y.; Johanson, M.; Kan, N.; Po, J.; and van Rijswijck, J. 2003. Solving 7x7 Hex: Virtual Connections and Game-State Reduction. In: van den Herik, H.; and Iida, H. (Eds) International Federation for Information Processing. vol. 263 Kluver Academic Publishers Boston 261-278. (Download)
  • Anshelevich, V. V. 2002. The Game of Hex: The Hierarchical Approach. In: Nowakowski, R. (Ed) 2002. More Games of No Chance. MSRI Publications, 42, Cambridge Universisty Press, 151-165. (Download)
  • Anshelevich, V. V. 2002. A Hierarchical Approach to Computer Hex. Artificial Intelligence, 134: 101-120. (Also in: Schaeffer, J.; and Van den Herik, J. (Eds) 2002. Chips, Computers and Artificial Intelligence, Elsevier, 141-160) (Download)
  • Anshelevich, V. V. 2000. Hexy Wins Hex Tournament. The ICGA Journal, 23(3):181-184. (Download)
  • Anshelevich, V. V. 2000. The Game of Hex: An Automatic Theorem Proving Approach to Game Programming. Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000), 189-194, AAAI Press, Menlo Park, CA. (Download)
  • Arratia-Quesada, A. A.; and Stewart, I. A. 1997. Generalized Hex and Logical Characterizations of Polynomial Space. Information Processing Letters, 63(3):147-152. (Download)
  • Even, S.; and Tarjan, R. E. 1976. A Combinatorial Problem Which Is Complete in Polynomial Space. Journal of the Association for Computing Machinery, 23(4):710-719
  • Gale, D. 1979. The Game of Hex and the Brouwer Fixed-Point Theorem. American Mathematical Monthly, 86:818-827.
  • Gardner, M. 1959. The Scientific American Book of Mathematical Puzzles and Diversions. New York: Simon and Schuster.
  • Lagarias, J.; and Sleator, D. 1999. Who Wins Misere Hex? In: Berlecamp, E.; and Rodgers, T. (Eds) The Mathemagician and Pied Puzzler. A Collection in Tribute to Martin Gardner. A K Peters, Natick, MA, 237-240. (Download)
  • Reisch, S. 1981. Hex ist PSPACE-vollständig. Acta Informatica, 15:167-191
  • Shannon, C. E. 1953. Computers and Automata. Proceedings of Institute of Radio Engineers, 41:1234-1241
  • Van Rijswijck, J. 2002. Search and Evaluation in Hex. Technical report, University of Alberta, Edmonton, Canada. (Download)
  • Van Rijswijck, J. 2000. Are Bees better than Fruitflies? (Experiments with a Hex playing program). AI'00: Advances in Artificial Intelligence, 13th biennial Canadian Society for Computational Studies of Intelligence (CSCSI) Conference, (ed. H. Hamilton), Springer-Verlag, New York, NY, 13-25. (Download)
  • Van den Herik, H. J.; Uterwijk, J. W. H. M.; and Van Rijswick, J. 2002. Games solved: Now and in the future. Artificial Intelligence, 134:277-311. (See also in: Schaeffer, J.; and Van den Herik, J. (Eds) 2002. Chips, Computers and Artificial Intelligence, Elsevier, 321-355) (Download)
  • Yang, J.; Liao, S.; and Pawlak, M. 2002. New Winning and Losing Positions for 7x7 Hex". 3rd International Conference on Computers and Games, July 25-27, 2002, Edmonton, Canada. (Download)
  • Yang, J.; Liao, S. and Pawlak, M. 2002. Another solution for Hex 7x7. Technical report, University of Manitoba (Download)
  • Yang, J.; Liao, S. and Pawlak, M. 2001. On a Decomposition Method for Finding Winning Strategy in Hex Game. International Conference on Application and Development of Computer Games Conference in 21st Century (ADCOG21), Nov 22-23, 2001, Hong Kong (Download)

Web Sources

  • Hex by Tijs Krammer.