Hex is the classic two-player connection game invented by Piet Hein in 1942 and independently by John Nash in 1948, and popularized by Martin Gardner in his Scientific American Mathematical Games column in 1957. The game has perfect information and deterministic actions, and is played on a parallelogram board divided into hexagon tiles. The players, black and white, take turns in placing stones of their color on empty tiles, and aim to create a path of their stones joining their two colored edges of the board.
It is impossible for Hex to end in a tie. Every filled board has a winning path for one player, and completing a path makes it impossible for the opponent to also complete a path. Hex is an ultra-weakly solved game: a winning strategy exists for the first player, but for arbitrary board sizes this strategy is unknown. Humans typically play on large boards (10x10 to 19x19), and recent research has solved every opening move of the game on boards up to 8x8.
Challenges for Artificial Intelligence Research
Hex is well-suited to artificial intelligence research for several reasons:
- The rules are simple, and the game is easily implemented. Algorithms from other games, particularly connection games such as go, can be tested and compared.
- Hex has a large branching factor, and so agents must identify which lines of play are worth considering.
- Recent research has shown that the game can be decomposed into subgames (known as virtual connections) or simplified by adding stones without changing the outcome (known as inferior cell analysis). This allows for accurate shallow search techniques, an alternative to the traditional approach of fast, deep heuristic search using simple evaluation functions.
Computer Hex dates from the 1950s, when E.F. Moore and Claude Shannon built an analogue player that modeled the game as an electrical circuit. Since then, artificial intelligence research towards Hex has reached the following milestones.
- 1994-1999: Queenbee, an alpha-beta heuristic search agent, is developed by Jack van Rijswijck.
- 2000: Hexy, an alpha-beta search agent based on virtual connections, is developed by Vadim Anshelevich. Hexy wins gold in the 2000 Computer Olympiad while Queenbee takes silver, and a paper describing Hexy wins the AAAI 2000 Outstanding Paper award.
- 2002-2003: Progress is made on solving 7x7 Hex. Jing Yang et al. find the first winning opening strategy for 7x7, and Hayward et al. go on to solve all 49 opening moves.
- 2003-2006: Six, by Gábor Melis, wins three Computer Olympiad gold medals. Six is an alpha-beta search agent using virtual connections.
- 2009: Henderson et al. solve all 8x8 openings.
- 2009-2011: MoHex becomes the strongest Hex program. Unlike earlier alpha-beta search based agents, MoHex uses Monte Carlo Tree Search, an algorithm widely used in the computer go community.