A Reverse Hex Solver
This work addresses a specific combinatorial game problem for researchers and AI enthusiasts, representing an incremental advancement in solving Reverse Hex.
The authors tackled the problem of solving Reverse Hex, a variant of Hex where the player connecting their sides loses, by developing Solrex, an automated solver that uses enhanced search algorithms. The result is that Solrex can solve arbitrary positions on board sizes up to 6x6, with the hardest position taking less than four hours on four threads.
We present Solrex,an automated solver for the game of Reverse Hex.Reverse Hex, also known as Rex, or Misere Hex, is the variant of the game of Hex in which the player who joins her two sides loses the game. Solrex performs a mini-max search of the state space using Scalable Parallel Depth First Proof Number Search, enhanced by the pruning of inferior moves and the early detection of certain winning strategies. Solrex is implemented on the same code base as the Hex program Solver, and can solve arbitrary positions on board sizes up to 6x6, with the hardest position taking less than four hours on four threads.