Threat-space search and λ-search

[foxyseta]

"Allis generalised the idea of threat-space search to a method called dependency-based
search [7]. However, the latter name was never adopted and the idea of threat-space
search or threat-sequence search is widely known by now. Threat-space search investigates
whether by a sequence of threats, to which the opponent at any time has only a limited
set of replies, a win can be forced. Since the opponent effectively has no real choices, this
search algorithm represents the application of single-agent search to two-player games.
A recent successor of threat-space search, called λ-search, has been proposed by
Thomsen [111]. This method uses null moves combined with different orders of threat
sequences, called λ-trees. Thomsen introduces λ1-moves, which threaten to end the game
or reach a specified subgoal immediately, followed by λ2-moves threatening a winning λ1-
sequence, and so on. The method behaves as a goal-directed searcher, with a favourable tree
size relative to standard α-β trees. It can be combined with any search method to search the
λ-trees. As a relevant example Thomsen mentions proof-number search. A combination of
null moves and proof numbers seems a promising method for solving Go endgames.
A close analogue to λ-search is Abstract Proof Search, proposed by Cazenave [27].
This method has reportedly been able to solve Philosopher’s Football on 9 × 9 boards.
304 H.J. van den Herik et al. / Artificial Intelligence 134 (2002) 277–311
Extensions of the algorithm can solve the 11 × 11 game and may be able to solve 13 × 13
as well [28]." Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck