Introduction
In the realm of artificial intelligence for games, determining whether a position is a win or a loss typically involves searching through an AND/OR tree. Depth-First Proof-Number (df-pn) search has emerged as a powerful technique for this task, prioritizing nodes that appear easiest to prove or disprove. However, when applied to complex games like Shogi (Japanese chess), standard df-pn search encounters significant hurdles: infinite loops, underestimation of search effort, and overestimation due to multiple paths reaching the same state.
The Challenge of Complex Game Graphs
Shogi presents a unique challenge for search algorithms. Unlike Western chess, captured pieces can be "dropped" back onto the board, leading to a high branching factor and frequent cycles in the game graph.
As illustrated in Figure 1, these graphs are often Directed Cyclic Graphs (DCG). Standard algorithms can become trapped in infinite loops. Previous attempts to mitigate this, such as df-pn(r), often ignore "old" nodes to break cycles. However, this leads to underestimation, where the AI incorrectly assumes a position is easier to solve than it is, wasting resources on dead ends. Conversely, in Directed Acyclic Graphs (DAG), multiple paths can converge on a single node, leading to overestimation if the difficulty of that node is counted multiple times.
Algorithmic Innovations: TCA and SNDA
To address these flaws, this research introduces two novel algorithms: the Threshold Controlling Algorithm (TCA) and the Source Node Detection Algorithm (SNDA).
Threshold Controlling Algorithm (TCA)
TCA moves beyond simply ignoring nodes to avoid loops. When the algorithm detects that a search is stagnating within a cycle, it strategically increases the "thresholds" for proof and disproof numbers. This mechanism forces the search to expand these nodes further until a leaf node (a definitive win or loss) is reached. By doing so, TCA breaks loops while maintaining a more accurate estimate of the required search effort.
Source Node Detection Algorithm (SNDA)
SNDA targets the overestimation problem in DAGs. It identifies "source nodes"—the specific points where different search paths merge. By utilizing transposition table pointers, SNDA detects these merges and adjusts the calculation of proof numbers. This ensures that each unique sub-problem is only counted once, preventing the search from being misled by inflated difficulty estimates.
Evaluation on Tsume-shogi
The effectiveness of these algorithms was tested using a suite of 78 notoriously difficult Tsume-shogi (checkmating) problems. These problems are characterized by extreme solution lengths, ranging from 300 to over 1,500 ply. Many of these instances were previously considered unsolvable by automated engines.
Key Results
The integration of TCA and SNDA yielded a dramatic improvement in solver performance. While the standard df-pn(r) approach failed to solve 14 of the 78 problems, the enhanced df-pn + TCA + SNDA configuration solved all but one.
As shown in Figure 6, the addition of TCA and SNDA progressively reduces the number of unsolved cases. Beyond just solving more problems, the SNDA-enabled version proved to be 2.5 to 6.2 times faster than previous methods on the most challenging instances. The solver successfully cracked legendary problems like "Meta-Shinsekai" (941 ply) in approximately two hours, a feat previously unattainable for automated solvers.
Conclusion
By addressing the fundamental issues of loops and inaccurate proof-number estimation, TCA and SNDA significantly extend the capabilities of df-pn search. While there is some computational overhead associated with SNDA's table traversals, the overall gain in search efficiency and accuracy is substantial. Future work may involve applying these techniques to other complex domains, such as Tsume-Go, to further validate their generalizability across different graph structures.
Summary updated