Current Staff & Students  |  Home  |  Library  |  Contact  |  Search  | Quick Find
  The University of Newcastle
Machine Intelligence for Hex
Your Location University > Faculty > Electrical Engineering and Computer Science > MIHex
 
 
The AI Challenge of Hex

Even the best computer Hex player in the world, Hexy, is no match for an advanced human Hex player. Some reasons why Hex is challenging for AI include:

  • Deep search is difficult because like the chinese game, Go, Hex has a large branching factor. For the standard 11x11 board there is over 100 possible moves in the early stages of the game, compare this to 30-40 for chess.
  • It is hard to find a feature decomposition for the game. For instance, the piece count gives no indication who is winning since pieces are never removed from the board. Connectivity measures give a better indication who is winning.
  • Neural network approaches work well when the evaluation function is smooth with respect to the network inputs. For instance, in Backgammon where small changes in the position usually lead to small changes in the expected outcome, neural networks can be trained using only the raw board position as inputs instead of a feature decomposition. Unfortunately, the nature of Hex topology and the binary outcome (win or loose) means that the evaluation function for Hex is not smooth with respect to the raw board position.