LAMBDA-SEARCH IN GAME TREES – WITH APPLICATION TO GO

Article type: Research Article

Authors: Thomsen, Thomas^{; 1}

Affiliations: Copenhagen, Denmark

Note: [1] Stockholmsgade 11, 4. th., DK-2100, Copenhagen, Denmark. Email: thomas@t-t.dk, http://www.t-t.dk.

Abstract: This paper proposes a new method for searching two-valued (binary) game trees in games like chess and Go. Lambda-search uses null moves together with different orders of threat sequences (so-called lambda-trees). Lambda-search focuses on threats and threat aversions, but still guarantees to find the minimax value. The guarantee presupposes that the game rules allow passing or that zugzwang is not a motive. Using negligible working memory in itself, the method seems able to offer a large relative reduction in search space over the standard alpha-beta method (comparable to the relative reduction in search space of alpha-beta over minimax). Among other things, the reduction depends upon how non-uniform the search tree is. Lambda-search is compared to other analogous approaches, such as null-move pruning and proof-number search. Moreover, it is explained how the concept and context of different orders of lambda-trees may ease and encourage the implementation of abstract game-specific knowledge. This is illustrated on open-space Go block tactics, by distinguishing between different orders of ladders. In close relation, some possibly fundamental work regarding an abstract formalization of the concept of relevancy zones (zones outside of which added stones of any colour cannot change the status of the given problem) is offered.

DOI: 10.3233/ICG-2000-23402

Journal: ICGA Journal, vol. 23, no. 4, pp. 203-217, 2000