Lambda-Search in Game Trees - with Application to Go
Lambda-Search in Game Trees - with Application to Go
复制标题
游戏树中的 Lambda 搜索 - 附带应用程序
DOI：
10.1007/3-540-45579-5_2
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Thomas Thomsen
中科院分区：
文献类型：
--
作者：
Thomas Thomsen
本文提出了一种在国际象棋、围棋等游戏中搜索二值(二值)博弈树的新方法。Lambda-Search使用空移动和不同顺序的威胁序列(所谓的lambda树)，将搜索集中在威胁和威胁厌恶上，但仍保证找到最小值(前提是游戏规则允许传球或zugzwang不是动机)。使用本身可以忽略的工作记忆，该方法似乎能够提供比标准α-β大得多的搜索空间的相对减少，这与α-β比极小极大的搜索空间的相对减少不相上下，其中取决于搜索树的不均匀程度。将Lambda-Search与其他类似的方法进行了比较，如空移动剪枝和证明号搜索，并解释了不同阶Lambda-树的概念和上下文如何简化和启发抽象游戏特定知识的实现。这在开放空间围棋拦网战术中得到了说明，区分了不同等级的梯子，并提供了一些关于关联区概念抽象形式化的可能的基础工作(在关联区之外添加任何颜色的石头不能改变给定问题的状态)。
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).