Abstract
Temperature Discovery Search (TDS) is a fundamental forward search method in combinatorial game theory (CGT) used to approximate or compute the "temperature" and "mean" of a game. These values are critical for determining optimal play in games that can be decomposed into a sum of independent subgames. This paper presents TDS+, an optimized version of the algorithm incorporating five key enhancements: iterative refinement, mathematical pruning based on game depth, generalized transposition tables, recursive search updates, and improved terminal position handling. Experimental results on Amazons subgames demonstrate that TDS+ significantly outperforms the original algorithm in both speed and accuracy, solving more than twice as many problems within the same time constraints.
Introduction
In combinatorial game theory, complex games like Go or Amazons are often analyzed as a sum of independent subgames. To play optimally, a player must understand the mean (the average score advantage) and the temperature (the urgency of moving) for each subgame. The original TDS algorithm calculates these by performing an $\alpha\beta$ search on a subgame combined with a "coupon stack"—a set of moves with decreasing values that simulate an environment of other games.
However, the original TDS implementation suffers from significant scalability issues. As the required precision increases (via a smaller step size $\delta$), the search depth explodes. Furthermore, the algorithm is susceptible to the "Graph History Interaction" (GHI) problem, where different paths to the same position yield different values due to the state of the coupon stack, leading to redundant computations.
The TDS+ Framework
TDS+ introduces five algorithmic enhancements (E1–E5) to address these bottlenecks:
- Iterative Refinement (E1): Instead of starting with high precision, TDS+ performs fast pre-searches with a large $\delta$. It utilizes a "2$\delta$-Conjecture" to establish safe upper bounds for subsequent, more precise searches, drastically reducing the number of coupons processed.
- Mathematical Pruning (E2): By applying "birthday" theory (the recursive depth of a game), the authors prove that certain temperatures are mathematically impossible for a game of a given size, allowing for aggressive branch pruning.
- Generalized Transposition Table (E3): A redesigned hash table allows for information reuse across different searches. It resolves the GHI problem by encoding the number of consecutive "pass-like" moves into the search state.
- Recursive TDS (E4): This dynamically applies iterative refinement. If the temperature drops significantly at an internal node, the algorithm recursively updates its bounds to skip unnecessary coupon sequences.
- Improved PTP Handling (E5): Enhanced recognition of "Pseudo-Terminal Positions"—where neither player benefits from moving—allows for earlier search termination.
Experimental Evaluation
The researchers evaluated TDS+ using 600 subgame positions from $4 \times 4$ Amazons boards, with complexities ranging from 2 to 14 empty squares. They compared various combinations of enhancements against the baseline TDS.
Performance and Coverage
The impact of these enhancements on search efficiency is profound. As shown in the performance data, the full TDS+ configuration ($TDS_{12345}$) consistently solves more problems across all time limits compared to the original TDS or partial enhancement sets.
In a 250-second window, the original TDS solved only 76 problems, whereas the full TDS+ solved 159. The data highlights that the combination of enhancements is synergistic; for instance, $TDS_{12345}$ significantly outperforms $TDS_{134}$ at higher time limits.
Approximation Accuracy
For practical real-time play, an algorithm must provide the best possible estimate within a fixed time limit. TDS+ demonstrates superior accuracy in these scenarios. By utilizing the iterative refinement of E1, it converges on the true mean and temperature much faster than the baseline.
As illustrated in the error analysis, the average error for both mean and temperature is consistently lower for TDS+ across different time limits. This makes TDS+ a more reliable engine for "Hotstrat" players—strategies that prioritize moves in the subgame with the highest temperature.
Conclusion
TDS+ represents a significant advancement in the computational analysis of combinatorial games. By leveraging mathematical properties of game depth and optimizing state management, it transforms TDS from a theoretical tool into a practical engine for high-performance play. While the 2$\delta$-Conjecture remains empirically robust but mathematically unproven, the current results provide a strong foundation for future work, including extending the framework to games with cycles, such as Go.
Summary updated