Jogos Matemáticos Através dos Tempos (no YouTube)
Estatutos da Associação Ludus [pdf]
Cartaz do CNJM15
Ligações
Actividades do dia - Ficha de inscrição
Premiados
Slimetrail (Zillions)
Poster
Hex [in English]
History
The game Hex was invented twice. The first, by the Danish scientist and poet Piet Hein, in 1942, the second, by the American mathematician John Nash, in 1948. However, it was Martin Gardner, in the pages of Scientific American, that popularized it in the 1950s [5]. Today Hex is becoming even more popular and studied, there is already a full book on Hex, by Cameron Browne, who wrote later about other games of the same family [2, 3].
Material
Hex is a connection game, usually played in a board like this:
with 60 white and 60 black counters.
Definitions
Adjacency — two pieces are adjacent, or connected, if the hexagons they occupy share an edge.
Group — a set of same-colored connected pieces.
Rules
There are two players, White and Black. They alternate coloring one hexagon of the board, or dropping a colored counter on an hexagon.
The pie rule holds, i.e., in his first turn the second player can choose between swapping colors (keeping the other player’s first dropping) or playing normally.
Goal
White tries to buid a group between SW and NE banks, Black connects SE to NW.
A possible connection for Black:
Notes
Nash’s equivalent game is played on the intersections of a board like this:
One player connects N-S, by dropping colored counters, for example, the other E-W.
The first striking fact about this game is that Hex cannot end in a draw.
Suppose we fill the board with white and black pieces, at random. Now think of the white stones as water and the blacks as land. Then, either the water flows from SW to NE, or there is a dam connecting SE to NW. In the latter case Black has won, in the former White was the winner. There is no possibility of drawing, wich helps making Hex an interesting game to play.
The above argument is intuitive, of course, but the rigorous proof is not difficult.
As Hex has no draws, it must be a first player win or a second player win. Suppose it is the second player who has a winning strategy. Then, the first player, in his first move, plays at random and looks at himself from then on as the second. An extra move, in a connection game, can never hurt, therefore the first player is going to win, stealing second’s winning plan. This is, of course, contradictory. We conclude that it is the first player that has a winning strategy.
This argument was devised by John Nash and is known by strategy stealing argument. It proves the existence of a strategy, but does not show it. Winning strategies for the first player are explicitely known for small boards (up to 7×7). For the usual size, 11×11, nobody found one yet. However, playing in the shortest diagonal at the beginning is considered to be too strong a move, unbalancing the game. The advantage of the first player justifies the pie rule. This way the first player wont play too strongly in his first move.
As this is a connection game, it is important to know how to extend a group. A move to a neighbor cell seems too slow.
Here the pieces in l7 and m7 are too close to each other, hardly being of any help connecting the edges.
On the other hand, a big jump can be cut by the adversary:
In this case, the pieces l7 and p7 can be effectively separated if White plays in n7.
An example of a good connection, not too far reaching, is a bridge, which consists on having two stones that share two neighbor cells:
Here, if White tries to cut, playing l6, Black replies in m7, and if White plays in m7, Black replies in l6. The two stones are as good as if they were already connected.
Defensive moves must also be well thought out. For instance, trying to block an adversary group should not lead us to play too close to it, because then it can extend easily:
Trying to block in k6 is met with a move in l7. Even at a bridge distance a block is not effective:
If White takes j5, Black replies in k7. Good moves are to be found at a distance:
David Gale [4] found a surprising mathematical connection to the no draws result. He proved that it is equivalent to Brower’s Fixed Point The- orem. This is an advanced result in Mathematics, it asserts that under certain hypotheses, a function f has a fixed point (i.e., there is an x such that f(x) = x). You can read more about this also in [1].
References
- Binmore, K., Fun and Games, D. C. 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.
