Reference:

Stefan Kiefer. Die Menge der virtuellen Verbindungen im Spiel Hex ist PSPACE-vollständig. Studienarbeit Nr. 1887, Universität Stuttgart, Juli 2003. In German.

Abstract:

The game of Hex possesses a deep tactical and strategical structure in spite of having very simple rules. Reisch showed in 1981 that classifying a Hex position as winning or losing is PSPACE-complete. So it is non-trivial to design a good Hex-playing computer program. Nevertheless there exist strong Hex programs such as Hexy and Six. They are based on the recognition of certain winning patterns, called virtual connections, in subgames. Virtual connections can be computed "bottom-up" by certain deduction rules introduced by Anshelevich. Those deduction rules are incomplete, i.e., not every winning position can be proved as winning by deducing a virtual connection. Still, state-of-the-art Hex programs spend most of their thinking time with the computation of virtual connections, because that generates valuable insight in the tactical and strategical potential of a Hex position which is indispensible for a good position evaluation function.

In this work we investigate whether the set of virtual connections lies in a lower complexity class then the set of winning positions. The answer is negative: the set of virtual connections is PSPACE-complete, too. The proof is based on Reisch's construction and strengthens his result. This allows for the conclusion that an exhaustive search for virtual connections is computationally intractable.

Suggested BibTeX entry:

@misc{Kie03,
    author = {Stefan Kiefer},
    howpublished = {Studienarbeit Nr. 1887, Universit\"{a}t Stuttgart},
    month = {Juli},
    note = {In German},
    title = {{D}ie {M}enge der virtuellen {V}erbindungen im {S}piel {H}ex ist {PSPACE}-vollst\"{a}ndig},
    year = {2003}
}