Focused Depth-first Proof Number Search using Convolutional Neural Networks for the Game of Hex

Chao Gao, Martin Müller, Ryan HaywardIJCAI 2017 · OpenReview

TL;DR

This paper introduces FDFPN-CNN, a novel approach to solving the game of Hex by integrating Convolutional Neural Networks (CNNs) into a focused proof number search algorithm. By leveraging CNNs for move ordering and widening decisions, FDFPN-CNN significantly outperforms previous methods, demonstrating a promising direction for improving game solvers by learning from expert play.

What Problem Does This Paper Address?

Solving perfect information games like Hex involves exploring vast game trees to determine theoretical outcomes. Traditional search algorithms, such as Proof Number Search (PNS) and its variants like Focused Depth-first Proof Number Search (FDFPN), struggle with games that have large and relatively uniform branching factors, like Hex. FDFPN, while an improvement, is sensitive to the quality of its heuristic move ordering function. This paper addresses the challenge of creating more robust and efficient game solvers by incorporating the powerful pattern recognition capabilities of Convolutional Neural Networks (CNNs), trained on expert game data, to guide the search process more effectively.

Methods

The core innovation lies in augmenting FDFPN with two CNNs:

  • Policy CNN: This network is trained to predict the probability of expert players making specific moves. It replaces the traditional resistance-based heuristic for move ordering, aiming to prioritize more promising moves during the search.
  • Value CNN: This network estimates the value of a given game state. It's used to dynamically adjust the "widening size" – how many child nodes are explored from a given node. Instead of a static widening factor, the value CNN's prediction allows for a more informed decision, potentially narrowing the search when a state is likely losing and expanding more when it's uncertain or winning.

The FDFPN algorithm itself is a variant of PNS that uses proof and disproof numbers to guide search. FDFPN introduces "dynamic widening" to prune the search space. FDFPN-CNN builds upon this by using the CNNs to inform both the move ordering and the widening strategy, creating a more "focused" search.

Datasets

  • Training Data: The authors generated a large dataset of 62,853 games by having two strong Hex AI players (Mohex and Wolve) play against each other. This data was then processed to create two primary datasets:
  • D₁: State-action pairs for training the policy network.
  • D₂: State-value pairs for training the value network.
  • Evaluation Data: The experiments were conducted on all 32 openings of the 8x8 Hex game.

Key Insights and Ideas

  • CNNs as Heuristics for Game Solving: The paper demonstrates that CNNs, typically associated with game playing, can be effectively adapted for game solving. By learning from expert data, CNNs provide a powerful way to guide search algorithms beyond handcrafted heuristics.
  • Dynamic Widening Informed by Value: Using a value network to dynamically adjust the widening factor is a key insight. This allows the search to be more aggressive when a state is clearly losing, but also to explore more when the outcome is uncertain, leading to a more efficient search.
  • Policy Network for Move Ordering: Replacing a traditional heuristic with a policy network trained on expert moves significantly improves the ability to identify promising branches of the game tree.
  • Learning from Expert Data is Crucial: The success of FDFPN-CNN hinges on the quality of the training data. Games played by strong AI players provide the necessary knowledge for the CNNs to learn effective move ordering and value estimation.

Key Results

  • Significant Performance Improvement: FDFPN-CNN outperformed the original FDFPN on 8x8 Hex openings, solving all 32 openings with a cumulative time that was 36% less than FDFPN.
  • Reduced Node Expansion: Crucially, FDFPN-CNN expanded 46.7% fewer nodes than FDFPN, indicating a much more efficient exploration of the game tree.
  • Value Network Accuracy: The value network achieved an accuracy of 85.7% in classifying nodes as winning or losing within the solution graph of a complex opening (a5).
  • Policy Network Effectiveness: The policy network showed a top-one prediction accuracy of 60.4% on the test data, which is comparable to state-of-the-art results in computer Go.

Limitations and Future Work

  • Data Generation: While the authors generated a substantial dataset, the quality of "expert" data is inherently limited by the players used. The paper notes that the training data might contain "noisy" labels.
  • Sensitivity to Widening Factor: FDFPN-CNN's performance can still be influenced by the choice of widening factor (μ).
  • Future Directions:
    • Improved Training Targets: The authors suggest adjusting training targets to discern frequently played good moves and occasional blunders, rather than just maximizing the likelihood of a single expert move.
  • Addressing Graph Structures: Hex game trees are actually directed acyclic graphs (DAGs), and the paper acknowledges that mis-selection of "Most Proving Nodes" due to exponential over-counting is an issue that needs addressing.
  • Hierarchical Value Estimation: Investigating ways to estimate node values by considering descendants (utilizing the AND/OR structure) could lead to more aggressive focusing.
  • Larger Board Sizes and Other Games: The framework could be adapted for larger Hex boards (beyond 8x8) and potentially other complex games.

Summary updated

Abstract

Proof Number search (PNS) is an effective algorithm for searching theoretical values on games with non-uniform branching factors. Focused depth-first proof number search (FDFPN) with dynamic widening was proposed for Hex where the branching factor is nearly uniform. However, FDFPN is fragile to its heuristic move ordering function. The recent advances of Convolutional Neural Networks (CNNs) have led to considerable progress in game playing. We investigate how to incorporate the strength of CNNs into solving, with application to the game of Hex. We describe FDFPN-CNN, a new focused DFPN search that uses convolutional neural networks. FDFPN-CNN integrates two CNNs trained from games played by expert players. The value approximation CNN provides reliable information for defining the widening size by estimating the value of the node to expand, while the policy CNN selects promising children nodes to the search. On 8x8 Hex, experimental results show FDFPN-CNN performs notably better than FDFPN, suggesting a promising direction for better solving Hex positions where learning from strong players is possible.
BibTeX
@inproceedings{gao2017focused,
  author = {Chao Gao and Martin Müller and Ryan Hayward},
  title = {{Focused Depth-first Proof Number Search using Convolutional Neural Networks for the Game of Hex}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=ByNWzVM_bB},
}

Loading related content...

Figure