What Does It Take to Win Hex?
Analyzing winning conditions in the board game Hex with a combinatorial graph theory approach
What is Hex, and where did it come from?
First invented in 1942 by Piet Hein and independently reinvented in 1948 by John Nash, Hex is a two-player strategy board game that has interested mathematicians for a long time. Hein initially came up with the game while thinking about the four-color theorem of topology (where any map on a plane can be colored with at least 4 colors such that no countries with a common border have the same color). After lecturing on it at the Institute for Theoretical Physics in Denmark, the newspaper Politiken popularized the game by publishing an article about it with the name “Polygon.”
John Nash reinvented the game while studying at Princeton University. His first version of the game used squares, where a cell is adjacent to another cell if it shares an edge or corner with it. After discussing the game with one of his instructors, the two revised it into the version Hein had invented. The game became referred to as either “Nash” (from John Nash’s name) or “John” (because it was commonly played on the school’s hexagonal bathroom tiles; a john is another name for a toilet) at Princeton, but it soon became widely known as “Hex” when marketed by Parker Brothers, Inc. in 1952.
We investigated one defining feature of Hex: that a win is forced, meaning one player is guaranteed to win. We also showed why the first player always has a distinct advantage during perfect play, using logic and graph theory.
Rules and setup
The game of Hex is traditionally played on an n×n parallelogram-shaped board of hexagons. The most common sized board is 11×11 (Figure 1), but other sizes such as 13×13 are also popular. Opposite pairs of the sides of the board are colored white and black, denoting the starting and ending sides for the two players, who are also labeled as player “A” (white) or “B” (black). They alternate turns placing their respectively colored tile into an empty hexagonal slot.
The winner of the game is the first person to connect their corresponding ends of the board in an unbroken chain of their colored tiles. The corner cells are considered parts of both sides and can be used to complete a chain for either color.
Proving the Hex Theorem
A game of Hex cannot end in a draw. This is the Hex Theorem, and can be proved by thinking of Hex as a planar graph, in which a vertex is a corner of a cell’s border. First, we must prove some lemmas about graphs:
- Lemma 1: A graph with N vertices, each with degree at most 2, will have at most N edges.
Given any arbitrary set of N vertices, in order to have the maximum number of edges where each vertex had a degree of at most 2, the starting vertex would first be given two edges. From the two vertices now connected by edges to the starting vertex, only one edge can be added so that the degree remains at most 2. These added edges to the 2 connected vertices will force one edge in two more vertices and will repeat until the Nth vertex, which must already be connected by 2 edges. By summing the edges (a sequence of N terms), we have 2 + 1 + 1 + … + 0 = N.
- Lemma 2: Any finite graph where a vertex has a degree of at most 2 is a union of disjoint components, and each component is either (A) an isolated vertex, (B) a simple cycle, or (C) a simple path.
We can use a proof by induction for this. Given a graph G with N vertices, where each vertex has degree at most 2, the maximum number of edges is N by Lemma 1.
Let k be the number of edges in a graph Gₖ. With the base case, G₀, there are N vertices and 0 edges, meaning it is a graph of only isolated vertices. By assumption, Gₙ is a union of disjoint vertices, simple cycles, and simple paths. Given graph Gₙ₊₁, with n + 1 vertices of degree at most 2, we randomly choose an edge (x, y) to remove, thereby creating a graph Gₙ, which meets the definition from Lemma 1. Since every vertex in Gₙ₊₁ had at most 2 edges initially, the vertices x and y now have at most 1 edge. This means they are not in a cycle. Adding the edge (x, y) back in will keep the graph as a set of disjoint vertices, simple cycles, and simple paths. Therefore graph Gₖ, where every vertex has degree 2 with k edges and for all k, 0 ≤ k ≤ N, is a union of disjoint components of isolated vertices, simple cycles, and simple paths.
Hex’s board can be considered a graph in many ways. We can assign a vertex to every corner of every cell. This makes the borders of each cell into edges, and each “cell” itself becomes a face, as shown in Figure 2.
- Theorem 1 (Hex Theorem): If every hexagon on the Hex board is colored black or white, there is either a white path from north to south or a black path from east to west.
We first represent the Hex board as a graph G = (V, E), where V is the set of vertices of the graph (there is a vertex on the graph for every corner of a hexagon on the board), and E is the set of edges between vertices or a side of a hexagon on the board. We then place vertices u₁, u₂, u₃, u₄ next to each corner tile and connect them to the graph by edges e₁, e₂, e₃, e₄, respectively. To make visualization easier, we will also change white spaces to x spaces and black spaces to o spaces. North and South will be changed to X and X’ respectively, while East and West are changed to O and O’ respectively. Now, we can restate the Hex Theorem.
- Theorem 1 (Restated): If every hexagon in a Hex board is marked either x or o, there is an x-path connecting X and X’ or an o-path connecting O and O’.
We then create another graph G’ = (V, E’) with the same set of vertices V, but where an edge is only considered if it lies between an x face and an o face, where an x/o face is a tile labeled x/o or one of the 4 external regions X, X’, O, O’. Figure 3 below provides a visualization.
If a vertex is surrounded with three faces of a kind, it will have no edges. If a vertex is surrounded by two of a kind and one different face, it will have 2 edges. The vertices u₁, u₂, u₃, u₄ only have 1 edge connecting them to the graph. This means that every vertex in the graph has at most degree 2, which means the graph is just a collection of components that are either lone vertices, simple cycles, or simple paths by Lemma 2.
Because the vertices u₁, u₂, u₃, u₄ only have one edge, they must be the endpoints of a simple path (a lone point has 0 edges; a vertex in a cycle or in the middle of a path must have 2). u₁, u₂, u₃, u₄ are also the only four points that can be endpoints in a path since every other vertex has either degree 0 or 2. Since u₁, u₂, u₃, u₄ are all endpoints of paths, there must exist exactly two paths in G’ with u₁, u₂, u₃, u₄ being endpoints to exactly one path each. The paths containing endpoints u₁, u₂, u₃, u₄ must also outline a winning path for at least one player because every edge borders an x-face and an o-face. Figure 3 contains a path from u₁ to u₄ and a path from u₃ to u₂. The path from u₁ to u₄ outlines a winning path of o-faces from the left side, while the path from u₃ to u₂ outlines the same path from the right side. Therefore, for any arbitrary placement of Hex tiles, there is a winning chain on the board.
Strategy stealing
Now that we have shown that there must be a winning path in any full Hex board, we can prove that Player A (the first player), in particular, will always win when given perfect, rational play. We can show this through the strategy stealing argument. We can prove this by contradiction.
- Lemma 3: Having extra/random pieces of a player’s own color lying on the board cannot hurt the player.
To prove Lemma 3, suppose there is a random tile x on the board of your color. If tile x happens to be a part of a player’s winning strategy, then they would include it in their chain. Otherwise, they would continue to ignore it and place a tile anywhere else on the board.
Suppose that Player B (the second player) has a winning strategy. However, because both players are rational and assuming both use perfect play (meaning they are at an equal playing level and one is not better than the other), Player A understands Player B’s winning strategy and will thus try to use it. Player A, going first, can place their first tile anywhere on the board. Because Player A now has an extra one of their tiles x on the board, Player A will never be harmed, but Player B will. Therefore, when Player B makes the next move, they are effectively the “first” player; they are playing on an “empty” board in Player A’s mind. Now, Player A is now effectively the “second” player, and Player A can use the original winning strategy for the rest of the game. This is strategy-stealing. Since Player A has now “stolen” the winning strategy originally put forth by Player B, Player B cannot win.
Let us consider some points. What is stopping Player B from stealing back the winning strategy from Player A by making a random move as demonstrated in the first move of the game? Since we are assuming perfect play from both players, even if Player B is playing at their best, they will never win against Player A. If there is perfect play on both ends, how did Player A steal the strategy in the first place? Why isn’t Player B able to adapt and continue playing smartly? This is where the contradiction lies. Because of Player A’s initial random move that worked in their favor, Player B is no longer in charge of the winning strategy. The winning strategy, no matter which player it originated with, will default to Player A.
Conclusion
The first player in a game of Hex has an indisputable advantage. Through the strategy stealing argument and with the knowledge that Hex cannot end in a tie, the first player is guaranteed to win with perfect play.
Although this is shown, a limitation of our proof is that a specific, step-by-step winning strategy for the first player was not (and cannot be with current computing capabilities) found. This causes the game to be classified as “ultra-weakly solved.” Hex on boards up to 6×6 have been “strongly solved” by computers, and winning strategies have been shown for boards from 7×7 to 9×9 (“weakly solved”).
Despite its straightforward rules, Hex grows complicated quickly. The standard 11×11 board has approximately 2×10¹⁰ times as many possible board layouts as chess. Therefore, it presents a significant challenge to artificial intelligence models that try to solve larger boards. Getting computers to solve Hex however has led to some advancements in artificial intelligence, and higher board levels might cause further benefits. Since Hex has a large branching factor, humans have consistently outperformed computers, and larger n×n boards are unlikely to be completely solved by anyone.
References
Li, J. (2011). Hex. Massachusetts Institute of Technology. http://web.mit.edu/sp.268/www/hex-notes.pdf
Hayward, R., & van Rijswijck, J. (2006). Hex and combinatorics. Discrete Mathematics, 306(19–20), 2515–2528. https://doi.org/10.1016/j.disc.2006.01.029
Gardner, M. (1959). Mathematical Puzzles and Diversions: The Game of Hex. University of Kentucky. http://www.ms.uky.edu/~lee/ma415fa11/gardner-hex.pdf
Keller, M., & Trotter, T. (2017). Applied Combinatorics. Georgia Institute of Technology. https://rellek.net/book/app-comb.html
Schachner, M. (2016). The Game of Hex A Study in Graph Theory and Algebraic Topology. University of Chicago. http://math.uchicago.edu/~may/REU2019/REUPapers/Schachner.pdf
