Solving 7x7 Hex: Virtual Connections and Game-State Reduction


Ryan Hayward, Ynvgi Björnsson, Michael Johanson, Morgan Kan, Nathan Po and Jack van Rijswijck. Solving 7x7 Hex: Virtual Connections and Game-State Reduction. In Advances in Computer Games 10 (ACG), 2004.

Download


Abstract

We present an algorithm which determines the outcome of an arbitrary Hex game-state by finding a winning virtual connection for the winning player. Our algorithm performs a recursive descent search of the game-tree, combining fixed and dynamic game-state virtual connection composition rules with some new Hex game-state reduction results based on move domination. The algorithm is powerful enough to solve arbitrary 7x7 game-states; in particular, we use it to determine the outcome of a 7x7 Hex game after each of the 49 possible opening moves, in each case finding an explicit proof-tree for the winning player.


Notes

This paper was the first to prove the outcome (with perfect play) of every opening move in the game of 7x7 Hex. It was later extended in 2005 as a journal paper, which I've described in much more detail. See that page instead.


BibTeX

@InProceedings{ 2004acg-solving-7x7,
  Title = "Solving 7x7 Hex: Virtual Connections and Game-State Reduction",
  Author = "Ryan Hayward and Yngvi Bj{"o}rnsson and Michael Johanson 
            and Morgan Kan and Nathan Po and Jack van Rijswijck",
  Booktitle = "Advances in Computer Games 10 (ACG)",
  Year = "2004",
  Editor = "H. Jaap van den Herik and Hiroyuki Iida and Ernst A. Heinz",
  Volume = "135",
  Series = "International Federation for Information Processing (IFIP)",
  Pages = "261-278",
  Publisher = "Kluwer Academic Publishers, Boston"
}