The Game of Hex

Hex is a mathematical strategy game for two players (Black and White), invented independently by mathematicians Piet Hein and John Nash in the 1940s.

The board consists of a grid of hexagons arraged in a diamond shape (rhombus). The object of the game is to connect two opposite sides of the board with a continuous chain of pieces, while the opposing player tries to connect the other two sides.

The HexMachine version 2.0 (July 2005) plays a strategy based on an iterative approach to identifying guaranteed connections between cells on the board.

- Click here to download the HexMachine version 2.0

Installation note: Due to issues with the web server hosting this site, this software is currently only available as a Zip file. For guidance on installing the software, click here. To run the software you will need the .NET Framework. You can install it here.

The Game

Two opposite sides of the board belong to each player (marked with the player's colour along the edge). Each of the corner cells counts as part of two edges.

Black starts. On each turn, a player places a piece of the appropriate colour on any empty cell.

The object of the game is to connect your two sides of the board with a continuous line of your pieces. In trying to connect the other two edges, your opponent is also blocking your chain.

The end of the game.
Black's winning line is marked in dark red.

Strategy

The strategy used in this software is based on the concept of bridges or guaranteed connections between cells. A simple bridge is a situation in which one cell is connected to another via two empty cells:

A brige for black

Such a link cannot be broken unless black makes a mistake - if white plays in one of the empty cells, black can play in the other.

In more complex bridges, the connections to the empty cells may themselves be via bridges:

A sure win for black: if white plays in any of the cells marked 'A',
black can play in the corresponding cell marked 'B'.

This software repeatedly applies the set of rules which define a bridge in order to map out the guaranteed connections between cells from each player's point of view, and where new bridges can be formed. The value of these potential bridges is then assessed using a modified version of the electric circuit model described in a paper by V. Anshelevich in order to choose the best move.

The weakness of the current strategy is that it does not take account of more complex bridges in which three or more potential routes are needed in order to guarantee a connection. Research is underway on ways of improving the strategy.