A hierarchical approach to computer Hex

摘要

Hex is a beautiful game with simple rules and a strategic complexity comparable to that of Chess and Go. The massive game-tree search techniques developed mostly for Chess and successfully used for Checkers and a number of other games, become less useful for games with large branching factors like Hex and Go. In this paper, we describe deduction rules, which are used to calculate values of complex Hex positions recursively starting from the simplest ones. We explain how this approach is implemented in HEXY—the strongest Hex-playing computer program, the Gold medallist of the 5th Computer Olympiad in London, August 2000.