History of computer Hex

Hex is a game that was invented by mathematicians and has simple rules, making it relatively easy to create a basic artificial intelligence (AI) compared to more complex games like chess. However, the branching factor (the number of possible moves) in Hex is quite large, making a brute-force approach less effective than in chess. In this regard, Hex is similar to Go, which also has a large branching factor.

Chronology

• Hex was invented in 1942.
• In 1953, Shannon and Moore built a machine that could play Hex by treating the board as an electric circuit. Red's hexes were considered as on switches, Blue's hexes as off switches, and empty hexes as resistances. The machine calculated the overall resistance of the circuit between Red's edges, evaluated all possible moves, and selected the move that minimized the resistance value of the circuit, trying to make it easier to join the two sides.
• In 1994, the program Queenbee was developed.
• In 2000, the program Hexy won a gold medal at the 5th Computer Olympiad in London. Hexy was the first computer program to use virtual connections.
• In 2002, the program Six was created. It was the best available Hex playing program at the time.
• In 2008, the program Wolve won a gold medal at the 13th Computer Olympiad in Beijing.
• In 2009, the program MoHex was developed. It uses the UCT algorithm and is currently one of the best non-AI computer Hex players. It is also a reasonably efficient Hex solver.
• Starting in the mid-to-late 2010s, it became much easier to train artificial intelligences, and there are now a number of very strong AI-based computer Hex players. The best ones consistently beat the best human players.

See also

• History of Hex
• Computer Hex

References

• Anshelevich, Vadim V. The Game of Hex: An Automatic Theorem Proving Approach to Game Programming. See paragraphs 2 and 3 for the first Hex playing machine.
• Gardner, Martin (1988). Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Puzzles and Games. University of Chicago Press, ISBN 0-226-28254-6.
• Reference for creation of Six.