Lecture Notes in Computer Science, 2001, Volume 2063/2001, 19-38, DOI: 10.1007/3-540-45579-5_2

Lambda-Search in Game Trees — with Application to Go

Thomas Thomsen

View Related Documents

Abstract

This paper proposes a new method for searching two-valued (binary) game trees in games like chess or Go. Lambda-search uses null-moves together with different orders of threat-sequences (so-called lambda-trees), focusing the search on threats and threat-aversions, but still guaranteeing to find the minimax value (provided that the game-rules allow passing or 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 standard alpha-beta comparable to the relative reduction in search space of alpha-beta over minimax, among other things depending upon how non-uniform the search tree is. Lambda-search is compared to other resembling approaches, such as null-move pruning and proof-number search, and it is explained how the concept and context of different orders of lambda-trees may ease and inspire the implementation of abstract game-specific knowledge. This is illustrated on open-space Go block tactics, distinguishing between different orders of ladders, and offering some possible grounding 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).

Keywords  binary tree search - threat-sequences - null-moves - proof-number - search - abstract game-knowledge - Go block tactics

Fulltext Preview

Image of the first page of the fulltext document