Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Terms of use
Privacy Policy

More Mathematics
CTK Exchange

Games to Relax
Guest book
Recommend this site

Sites for teachers
Sites for parents

Manifesto: what CTK is about Buying a book is a commitment to learning Things you can find on CTK Email to Cut The Knot Recommend this page

Hex Can't End in a Draw

The game of Hex has been invented in 1942 by Piet Hein, reinvented in 1948 by John Nash, got its name in 1952 from a commercial distribution by Parker Brothers, and has been popularized by Martin Gardner in 1957.

The game is played on a diamond shaped board with hexagonal cells and two pairs of opposite sides painted in two distinct colors, say, red and blue. Two players take turns putting chips down, one chip per a cell. One player plays with red chips, the other with blue chips. The goal of the "red chip" player is to connect the two red sides of the board with an uninterrupted chain of red chips. The other player pursues a similar goal with regard to the blue color.

Much is known about the game, even a winning strategy for small -- up to 9×9 -- boards. Simple as the game appears, no winning strategy has been discovered for bigger boards. The most important fact known about the game is that, unlike some other games, it can't end in a draw. One of the players is bound to win. In fact the first player can force a win. This was shown by John Nash in 1949 by what since became known as the strategy stealing argument.

The argument goes as follows. Assume there is a winning strategy for the second player. We are then going to show that the first player can utilize this same strategy to win the game. To make this work, the first player makes a very first move and, in a sense, forgets about it. He imagines now being a second player and, as such, playing the winning strategy on the board with an extra chip of his color. Note that the extra chip can do no harm to this player. If, in time, the winning strategy requires placing a chip in a cell occupied by the extra chip, the player puts a chip randomly elsewhere, and thinks of the latter as the (new) extra chip. Impersonating his rival and playing the latter's winning strategy will lead the first player to victory. Contradiction.

Thus in the game of Hex, the first player has an advantage. Different stratagems have been devised to minimize this advantage [Gardner, Browne]. However, it must be said, that the game is sufficiently complicated for a novice to make use of this advantage. A good second player will have no difficulty to consistently thrush a game opening novice. Do try playing the game. On- and offline games are freely available. Just search the web.

The goal of this page is to discuss the aforementioned fact: Hex can't end in a draw. If it could, it would be possible to fill out the board without there being a game resolving chain of either color. You can experiment with the applet below to convince yourself that there is always a game winning chain. (You can click on a cell to modify the color of the chip it contains.)

Along with the hexagonal board, the applet also allows experimenting with a similar game on a square board. This affords three distinct variants depending on the notion of connectedness that make two (now square) cells adjacent.

The diagram depicts the cells adjacent to the central square in gray. The variants based on the 4- and 8-connectedness do not lead to interesting games. In the 4c (for shortness) game, the draw is possible; in the 8c variant, the chains of different colors can cross without blocking each other.

The 6c variant is equivalent to playing the game on the standard hexagonal board. It is more convenient for arithmetization and subsequent analysis and programming of the game. Historically, this is exactly the variant John Nash came up with.

(The 4- and 8-square grids still provide some entertainment. Looking at the board that contains no 4-chain or two crossing 8-chains, can you tell at a glance how many clicks will it take to get a single winning chain of a selected color?)

<hr> <h3> This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet. </h3> <hr>

Discussion

Copyright © 1996-2008 Alexander Bogomolny



Search:
Keywords: