Set colouring games
Jack van Rijswijck · 2006
The game of Hex has been of particular interest to mathematicians, computer scientists, and game players alike ever since its discovery in the 1940s. The game is provably difficult in the sense of algorithmic complexity, yet its rich mathematical structure allows for many properties to be provable even when exact solutions to the game are unknown. Such properties can then be used to boost computational approaches to solving Hex on small boards, and playing well on larger boards. This thesis presents a general class of mathematical games that contains Hex and many of its relatives. The thesis generalizes all previously known Hex theory to this class, and identifies conditions that give rise to these properties. This enables rigorous proofs of game properties previously known only colloquially, as well as introduction of new properties. Algorithmic optimizations that follow from this theory have enabled advances in Hex solving and playing, and can be applied to related games as well.