Proof-Set Search
Proof-Set Search
复制标题
证明集搜索
DOI：
10.1007/978-3-540-40031-8_7
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Martin Müller
中科院分区：
文献类型：
--
作者：
Martin Müller
Victor Allis的证明数搜索是一种功能强大的最佳优先树搜索方法，它可以通过在博弈树中重复展开最具证明性的节点来求解博弈。证明数搜索的一个众所周知的问题是，它没有考虑到换位的影响。如果搜索构建的是一个有向无环图而不是树，那么同一个节点可以被计算多次，从而导致错误的证明数和反证数。虽然有精确的方法来计算dag中的证明数，但它们太慢而不实用。证明集搜索（PSS）是一种新的搜索方法，它使用与证明数搜索类似的值传播方案，但它备份的是证明集和反驳集，而不是数字。虽然通过证明集搜索计算的集合不能保证具有最小的大小，但它们确实提供了比证明数可能提供的更严格的可证明边界。具有（P，D）截断节点集或pssp，D的广义证明集搜索在内存需求和解决方案质量之间提供了良好的控制权衡。证明数搜索和证明集搜索都是pssp，D的特殊情况。PSS和pssp， d都可以利用叶节点成本的启发式初始化，正如Allis在证明数搜索中提出的那样。
Victor Allis’ proof-number search is a powerful best-first tree search method which can solve games by repeatedly expanding a most-proving node in the game tree. A well-known problem of proof-number search is that it does not account for the effect of transpositions. If the search builds a directed acyclic graph instead of a tree, the same node can be counted more than once, leading to incorrect proof and disproof numbers. While there are exact methods for computing proof numbers in DAGs, they are too slow to be practical.Proof-set search (PSS)is a new search method which uses a similar value propagation scheme as proof-number search, but backs up proof and disproofsetsinstead of numbers. While the sets computed by proof-set search are not guaranteed to be of minimal size, they do provide provably tighter bounds than is possible with proof numbers.The generalizationproof-set search with (P,D)-truncated node setsorPSSP,Dprovides a well-controlled tradeoff between memory requirements and solution quality. Both proof-number search and proof-set search are shown to be special cases ofPSSP,D. Both PSS andPSSP,Dcan utilize heuristic initialization of leaf node costs, as has been proposed in the case of proof-number search by Allis.