An Extension of the H-Search Algorithm for Artificial Hex Players

摘要

Hex is a classic board game invented in the middle of the twentieth century by Piet Hein and rediscovered later by John Nash. The best Hex artificial players analyse the board positions by deducing complex virtual connections from elementary connections using the H-Search algorithm. In this paper, we extend the H-search with a new deduction rule. This new deduction rule is capable of discovering virtual connections that the H-search cannot prove. Thanks to this new deduction rule, the horizon of the artificial Hex players should move further away.