The Danish engineer and poet Piet Hein invented the game Con-Tac-Tix, now known as Hex, and presented it at the Niels Bohr Institute of Theoretical Physics in 1942. Piet Hein invented Con-Tac-Tix while contemplating the four-colour theorem for topology. This theorem states that four colours is sufficient to colour countries on a map such that no two adjacent countries have the same colour. The four-colour theorem was unproven at the time. The arrangement of hexagons on the Con-Tac-Tix board was of interest to Piet as this topology is an example that requires only three colours. Piet Hein marketed Con-Tac-Tix in 1968. The game of Con-Tac-Tix became very popular in Denmark as a pen and paper game under the name Polygon.
In 1948, John F. Nash rediscovered the game of Hex and presented several theories and proofs on the game at Princeton University. In 1949, John Nash proved the existence of a winning strategy for the opening player. However, this proof is an existence proof and does not reveal the details of the winning strategy.
To date, the game of Hex has been completely solved for small board sizes up to and including the 7x7 Hex board. Much of the pioneering work in solving small Hex boards was done by Ying Yang et al from the University of Manitoba and described in there technical report called: "On a Decomposition Method for Finding Winning Strategies in Hex game". Their contribution was to identify a feature of Hex board positions, which they called Threat Patterns. With threat patterns, Ying Yang was able to deduce by hand some of the winning strategies for the 7x7, 8x8 and 9x9 Hex boards. However, they did not prove solutions for all opening moves.
In the year 2000, around the same time as Ying Yang's work, Vadim Anshelevich published a paper called: "An Automatic Theorem Proving Approach to Game Programming" and in 2002 a paper called: "A Hierarchical Approach to Computer Hex". Anshelevich identified a feature of Hex board positions, similar to threat patterns, which he called Sub-Games. The neat property of sub-games was that one could apply deduction rules on a set of simple sub-games to deduce new and more complex sub-games. Anshelevich's main contribution was a sub-game deducing algorithm called the H-Search algorithm. The H-Search algorithm can solve Hex completely for Hex boards smaller than 5x5. On larger board sizes, the H-Search algorithm is effective in finding solutions towards the end of games. Given this property, Anshelevich used his H-Search algorithm to develop a strong artificial Hex player called Hexy. This player won first place at the 2000 International Computer Olympiad for the game of Hex.
In 2002, Jack van Rijswijck from the University of Alberta wrote a technical report called "Search and Evaluation in Hex". This report features a search algorithm called Pattern Search. Pattern search is best described as a hybrid between a game tree search algorithm and a threat pattern deduction algorithm. Pattern search features an exhaustive game-tree search which applies a deduction rule on threat patterns as it backtracks from terminal board positions. A side effect of this deduction rule is extensive pruning of the search. The patterns search can completely solve small Hex boards, however, it does not scale well.
In 2003, Ryan Hayward et al, also from the University of Alberta, addressed some of the scaling problems with the pattern search algorithm in their paper "Advances in Computer Games: Solving 7x7 HEX: Virtual Connections and Game-State Reduction ". This paper features a Hex solving algorithm called Hex Solver. Hex Solver can completely solve all small Hex boards up to and including the 7x7 Hex board.
My research is building on the shoulders of these great works. In 2004, my supervisor Dr. Frederic Maire and I wrote a paper called "An extension of the h-search algorithm for artificial hex players". This paper talks about a sub-game deduction algorithm which lends some technology from Jack van Rijswijck's pattern search. Our sub-game deduction algorithm is not a complete Hex solving algorithm, however, it can solve a more complex class of sub-games than the H-Search algorithm.
In 2006, my supervisors Dr Frederic Maire, Dr Ross Hayward and I wrote a paper called "A Move Generating Algorithm for Hex Solvers". In this paper we present a move generating algorithm able to significantly maximize pruning in a pattern search. We call a pattern search algorithm extended with our move generating algorithm the Connection Utility Search algorithm. We show that our connection utility search algorithm can perform better than a min-max search with alpha-beta pruning when set the task to solve the 3x3 and 4x4 Hex boards. In more recent work, we have extended the connection utility search algorithm with a specialized transposition table and have solved up to and including the 6x6 Hex board. We a poised to solve completely the 7x7 Hex board. Our aim is to solve completely the 8x8 Hex board.
Last modified 12/12/2006