Home MadLab Info Algorithm |

Details about the
algorithm (lambda-search) |

Lambda-search is in the same family of algorithms as Tristan Cazenave's GAPS, using the concept of threats (null-moves) together with topological knowledge. It also has some relation to the null-move pruning idea used successfully in chess. You may consult my paper on Lambda-search for many more details on the algorithm. The MadLab engine builds upon these principles, but it should be noted that the algorithm has undergone a transformation in a number of respects since the date of the paper (2000). Go is a game characterized by a huge branching factor of 200-250, compared to 30-40 in western chess. This means that a Go program -- including a tesuji solver -- cannot rely upon brute force (looking at all variations) in the same way as a chess program. In addition, the topological properties of the Go board should be taken into account. Lambda-search uses the concept of threats (and meta-threats, and so on) together with topological knowledge in order to address open-space tesuji problems that would entail an explosion in the number of variations without these techniques. In addition, proof-number search is integrated as the "search engine" for searching the so-called lambda-trees. In general, proof-number search performs much better on tesuji problems than algorithms like alpha-beta and variants. In addition to this, the original lambda-search algorithm has been augmented in order to also take the depth of lambda-trees into account. This has some similarities with the above-mentioned GAPS algorithm, and at present the lambda-algorithm can be employed in two ways: (1) default, with the depth of lambda-trees taken into account, or (2) a more depth-oriented algorithm ('deep search mode') corresponding to the one descriped in my paper from 2000. The default version performs better on most kinds of tesuji problems, except those with very deep forced lines. So on systems with multiple processors, it could make sense to run both version of the algorithm at the same time (MadLab can solve several problems at the same time, each running on its own board). A future MadLab version might support multiple processors in a more integrated way. The algorithm is precise in the sense that if it finds a solution to a given problem, this solution is 100% definitive; meaning that the goal (e.g. killing some stones) can be obtained no matter what the defender tries. Regarding this, MadLab is in the same spirit as the tsume-solver GoTools, either providing definite answers, or running out of time. MadLab does not give wrong answers: it either gives a working answer or keeps searching :-). Like GoTools, the program can analyze problems where one of the players has external ko threats to his or her disposition. MadLab uses the super ko rule, and care is taken to avoid the so-called GHI (Graph History Interaction) problem. Regarding go-specific knowledge and patterns, it should be emphasized that the program does not contain any such at the present stage, relying instead upon advanced search-techniques combined with topological properties of the board. In some cases this may be a drawback, but on the other hand it means that MadLab is not biased in regards to solving certain kinds of tesuji patterns better than others. MadLab prefers problems with a relatively low lambda-order, but apart from this MadLab has no preferences whatsoever. This means that MadLab will have a go at all kinds of tesuji problems, including very artificial or unusual ones. In addition to obtaining goals, MadLab can also search for the inverse: namely avoiding goals; for instance the program can be asked to find moves that prevent a block from being killed. You can read more about 'avoid goal' search here. If you want to see some very simple Java-code illustrating the lambda-search algorithm, you can find quite a bit of code here. |