Solving 7x7 Hex with domination, fill-in, and virtual connections


Ryan Hayward, Ynvgi Björnsson, Michael Johanson, Morgan Kan, Nathan Po and Jack van Rijswijck. Solving 7x7 Hex with Domination, Fill-In, and Virtual Connections. In Theoretical Computer Science, Volume 349 Issue 2, Pages 123-139. 2005.

Download


Abstract

We present an algorithm that determines the outcome of an arbitrary Hex game-state by finding a winning virtual connection for the winning player. Our algorithm recursively searches the game-tree, combining fixed and dynamic game-state virtual connection composition rules to find a winning virtual connection for one of the two players. The search is enhanced by pruning the game-tree according to two new Hex game-state reductionresults: under certain conditions, (i) some moves dominate others, and (ii) some board-cells can be "filled-in" without changing the game's outcome.

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 is an extended version of our earlier 2004 paper on solving the game of 7x7 Hex.


Hex is a board game independently invented by Piet Hein in 1942 and John Nash in 1947. Hex is a two-player game played on a parallelogram board tiled with hexagons, where two opposite edges are colored red and the other two are colored blue. The blue and red players take turns placing their stones on any unnocupied tile, and are trying to connect their two edges. It is impossible for the game to end in a tie: when the board is filled, exactly one player will have a winning path of stones joining their edges. The game can be played on many board sizes: the 7x7 board, for example, has 7 hexagons across each edge.


Hex has an interesting theoretical property: the first player has a winning strategy (ie, they can win if they play perfectly), but the winning strategy itself is not known for all board sizes (particularly large boards). This means that the value of the game is known, but the winning strategy needed to obtain that value is not. In this work, we created a program that finds explicit winning strategies for the 7x7 game, and explores all lines of attack for the other player to prove that the strategy is a winning one.


Common wisdom in Hex says that the center position is a strong opening move. Other opening moves might also be winning moves, but the center position (and, in general, positions closer to the middle) are widely considered to be strong. The 7x7 game had already been solved by Jing Yang, who showed that the center position is indeed a winning opening move in 7x7. However, to make the game more interesting, Hex is often played with the "Swap Rule". After the first player makes a move, the second player has the option to either place a stone of their color, or to swap colors with the first player. With the swap rule, the second player has a winning strategy. If the first player's opening move is strong (ie, if it has a winning strategy) then the second player should swap. If the first player's opening move is weak (if it is not possible to force a win) then the second player should not swap. Since the players probably do not know exactly which opening moves are winning or losing, the first player will choose a marginal move, where it's not clear if it is too strong or too weak.


To solve the 7x7 game with the swap rule, then, it's not enough to just know the winning strategy for the center position: you have to provewhether or not each of the 49 opening moves has a winning strategy. This is what we accomplished in this paper. We designed a program that accepts an opening move and then explores all useful lines of play following from it. Since the game is very large, we discovered and used strong theoretical properties aboutthe game to reduce the size of the tree that we had to explore. Combined with the already known Virtual Connections formalism for proving if a player could win subgames, and by using an undergraduate computer lab over the summer, we were able to prove whether each opening move was a win or a loss, as shown in this picture:

This diagram shows the outcomes for each opening move without the swap rule. Blue cells are winning opening moves for the blue player (who moves first), and red cells are losses for the first player. The red cells show the response (or one of them) that red can use to win. With the swap rule, if you are playing second, this means that you should swap if the opponent plays in a blue position, and otherwise play the response shown on the cell your opponent moves to.


Links


BibTeX

@article{ 2005-tcs-solving-7x7,
  Title = "Solving 7x7 Hex with Domination, Fill-In, and Virtual Connections",
  Author = "Ryan Hayward and Yngvi Bj{"o}rnsson and Michael Johanson and 
            Morgan Kan and Nathan Po and Jack van Rijswijck",
  Journal = "Theoretical Computer Science",
  Year = "2005",
  Volume = "349",
  Number = "2",
  Pages = "123-139"
}