Automated Discovery of Search-Extension Features

The design of effective search-extension schemes in game-playing programs traditionally relies on manual, intuition-based selection of move categories, a process that is both time-consuming and prone to human error. To address this limitation, the Gradual Focus algorithm provides a systematic approach for the automated discovery of move categories. By iteratively combining atomic features—such as piece type and placement—into more refined and complex categories, the algorithm identifies optimal search extensions without requiring extensive domain expertise.

The methodology centers on an iterative construction process that builds sophisticated features from a base set of atomic properties. This approach effectively manages the combinatorial explosion typically associated with feature generation. By focusing only on the most promising combinations, the algorithm significantly reduces the computational overhead required to identify effective search strategies. This represents a departure from brute-force methods, which often struggle with the exponential growth of potential feature sets.

Empirical evaluation within the game Breakthrough demonstrates the efficacy of this approach. The results indicate that Gradual Focus explores a search space two orders of magnitude smaller than that of a brute-force search, while successfully maintaining high levels of precision and recall. These findings suggest that automated feature discovery is a viable and efficient alternative to manual tuning, particularly in game environments where optimal move-extension strategies are not well-defined. By automating the discovery of these features, developers can improve the performance of alpha-beta search algorithms in complex, adversarial board games.