Lambda Search

Lambda Search is a kind of generalized Null-Move Search for solving open-space Go problems. The objective can be to capture a group, connect two of your own groups and similar problems where the outcome is a simple yes/no answer. It is defined to use lambda-trees of different orders. Lambda-trees can only contain lambda-moves of the same order (subset of all legal moves).

Evaluating the minimax value on a lambda-n tree, results in either 1 (success) or 0 (failure). When the result is 1, there is absolute certainty, that this result can be reached in normal play, i.e. the minimax value of the full game tree is indeed 1.

However, if the value of the lambda-n tree is 0, this does not mean the problem cannot be solved. There could be a solution when going to higher orders (lambda-(n+1) tree, ...). (Go tactics: if a working ladder does not exist, look for a net)

Lambda trees can be searched with standard game tree search algorithms like Alpha-Beta Search, or Proof-Number Search; but for the moves, it has to be determined whether moves are really Lambda-n moves (which is checked with a recursive call: after a null move (=defender pass) there has to exist a lambda-n tree of lower order for the attacker).

By limiting the allowed moves in the lambda-trees, the branching factor is reduced, which makes the search more effective (only threats up to a certain level are considered).

Examples:

• Lambda_a^0 Tree: (for attacker, lambda level=0)
  • has value 1: if the attacker's goal can be achieved directly by at least one of the attacker's legal moves
  • has value 0: otherwise

• Lambda_a^1 Tree: (for attacker, lambda level=1, like Go Ladder)
  • has value 1: if ladder played by the attacker works (sequence of ataris, with final capture)
  • has value 0: otherwise

• Lambda_a^2 Tree: (for attacker, lambda level=2, like Go net)
  • has value 1: a working "net" or loose ladder exists
  • has value 0: otherwise

etc ...

References

• Thomas Thomsen: Lambda-search in game trees – with application to Go
• Kazuki Yoshizoe, Akihiro Kishimoto, Martin Müller: Lambda Depth-first Proof Number Search and its Application to Go
• Shunsuke Soeda, Tomoyuki Kaneko and Tetsuro Tanaka: Dual Lambda Search and Shogi Endgames
• Martin Suda: [Relevancy Zones for Lambda Search in Rigid Board

Games| https://web.archive.org/web/20200709142707if_/mff.cuni.cz/veda/konference/wds/proc/pdf08/WDS08_126_i1_Suda.pdf]

• https://t-t.dk/go/cg2000/code.html Pseudo code. Lambda Search is used in MadLab