HEX and Neurodynamic Programming
This work addresses the challenge of game-solving in Hex for AI researchers, representing an incremental step by adapting methods from AlphaGo Zero to a new domain.
The paper tackles the problem of solving the complex game Hex without using traditional game tree structures or heuristic information like Virtual Connections, instead employing reinforcement learning through self-play and neural network approximations to bypass the high branching factor and large state-action evaluation tables, resulting in a novel approach inspired by AlphaGo Zero.
Hex is a complex game with a high branching factor. For the first time Hex is being attempted to be solved without the use of game tree structures and associated methods of pruning. We also are abstaining from any heuristic information about Virtual Connections or Semi Virtual Connections which were previously used in all previous known computer versions of the game. The H-search algorithm which was the basis of finding such connections and had been used with success in previous Hex playing agents has been forgone. Instead what we use is reinforcement learning through self play and approximations through neural networks to by pass the problem of high branching factor and maintaining large tables for state-action evaluations. Our code is based primarily on NeuroHex. The inspiration is drawn from the recent success of AlphaGo Zero.