Hex
History: The Hex was invented twice. The first time was by the Danish scientist and poet Piet Hein in 1942, and the second time was by the American mathematician John Nash in 1948. However, it was Martin Gardner, in the pages of Scientific American, who popularized it in the 1950s [5]. Today Hex is becoming increasingly popular and is widely studied; a book has already been dedicated to it by Cameron Browne, who later wrote another about games in the same family [2, 3].
Material: Hex is a connection game, usually played on a board like this:
With 60 white pieces and 60 black pieces.
Definitions
Adjacency — Two pieces are said to be adjacent if the hexagons they occupy share an edge.
Group — a set of adjacent pieces of the same color.
Rules
There are two players, White and Black, who alternate coloring a hexagon on the board or placing a piece of their color on a hexagonal cell.
It's worth it balance rule, ie, on his first move, the second player can choose between switching colors (keeping the opponent's first move) or playing normally.
Objective
White tries to build a group between the SW and NE shores, Black connects SE to NW.
A group that would give victory to Black:
Notes
The equivalent Nash game is played on the intersections of a board like this:
One player connects NS, placing pieces of his color on the intersections, the other tries to connect EO.
The first notable fact about this game is that it does not allow draws.
Suppose the board is completely filled with pieces of two random colors. Let us interpret the white pieces as representing water and the black pieces as solid ground. Then, one of two things will happen: either the water flows between the SW and NE banks, or there is a dike connecting the SE and NW banks. In the latter case, Black wins, in the former, White wins. The absence of ties makes Hex an even more interesting game to play.
The above argument is intuitive, of course, but rigorous proof is not difficult.
Since no game of Hex can end in a draw, the game must always be winnable by the first or second player, if both play perfectly. Suppose that it is the second player who has a winning strategy. Then, the first player, on his first move, can play randomly and start to see himself as the second player. Since an extra move, in a connection game, can never be a penalty, the first player will win, using the second player's winning strategy. We have obtained a contradiction. The conclusion is then that it is the first player who has a winning strategy.
This argument was used by John Nash and became known as strategy theft argument. It proves the existence of a winning strategy, but does not show it. Winning strategies for the first player are known explicitly for small boards (up to 7×7). For the usual size, 11×11, it remains unknown. However, opening with a move on the smaller diagonal is very strong, unbalancing the game. It is this advantage of the first player that justifies the balance rule. This way the first player will try not to play too hard on his first move.
Since Hex is a connection game, it's important to know how to extend a group. Playing in an adjacent space seems too slow.
Here the pieces at l7 and m7 are too close to each other, doing little to help connect the edges.
On the other hand, a jump that is too long allows the opponent to interfere:
In this case, the pieces l7 and p7 can be separated if White plays n7.
An example of a good connection, which is not too ambitious, is bridge, which consists of two pieces that share two neighboring houses:
Here, if White tries to cut by playing l6, Black replies with m7, and if White plays m7, Black replies with l6. The two pieces are virtually linked to each other.
Defensive moves also deserve consideration. For example, when trying to block an opposing group, we should not play too close to them, because this allows for immediate extensions:
The blocking attempt k6 gets the response l7. Up to a distance of a bridge the blockade weakens:
If White plays j5, Black responds with k7. Good moves are often in the distance:
David Gale [4] discovered a surprising connection between the above result of the absence of ties in Hex and a theorem in advanced mathematics. He proved that it is equivalent to Brower's fixed point theorem, which is a sophisticated result in mathematics stating that under certain assumptions a function f has a fixed point (ie, there is a x such that f(x) = x). You can also read about this in [1].
References:
- Binmore, K., Fun and Games, DC Heath and Co., 1992.
- Browne, C., Hex Strategy: Making the Right Connections, A.K. Peters, 2000.
- Browne, C., Connection games, A.K. Peters, 2004.
- Gale, David, W., “The game of Hex and the Brower fixed-point theorem”, American Math. Monthly, Vol. 86, 1979, pp. 818–827.
- Gardner, M., “The Game of Hex”, in The Scientific American Book of Mathematical Puzzles and Diversions, Simon and Shuster, New York, 1959, pp. 73–83.
Additional information: