Welcome to my website. If you have an interest in research relating games and artificial intelligence then you have come to the right place. This website contains information about the game of Hex including some of my own research into artificial players and Hex solvers.
For those not familiar with the game of Hex. The game of Hex is a competitive two-player game on a rhombic board of hexagonal places (see fig 1). The correct terminology for a place is "cell" and the terminology for a playing piece is "stone". Each player has a cache of stones. The player "Black" has black stones and "White" has white stones. Each player takes turns and places a stone on an empty cell. The aim of the game for "Black" is to connect the North and South sides of the board with an unbroken chain of black stones. Similarly, the aim of "White" is to connect the East and West sides with an unbroken chain of white stones. The first player to make such a connection wins the game.
Fig 1. Displays a Hex 9-board.
The opening player has a distinct advantage if the opening move is towards the centre of the board. If the player who moves second feels that the opening move is too strong then that player can apply the swap rule. The swap rule assigns the second player with the opening move. The second player can apply this rule only once and must do so immediately after the opening move. After a swap the second player gains the opening move and the opening player has another turn. The simplest way to apply the swap rule is for the players to swap colour.
Hex is a perfect connection game with simple rules. The problem of solving Hex is intractable and the synthesis of artificial Hex players is a great and difficult challenge. The decision problem associated with solving Hex is PSPACE-complete, which means that Hex can be solved using polynomial space and unlimited time. It is very unlikely that a PSPACE-complete problem can be solved polynomial time (unless P = PSPACE). One expects that the problem of solving Hex is NP-hard.
Author: Rune Rasmussen
Last Modified 24/08/2008