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.
|