研究者用Proof Number搜索求解终极井字棋

我解决 Ultimate Tic Tac Toe 的工作基于 Proof Number Search（即“PN Search”）系列搜索算法。这一系列算法已被用于求解许多游戏，包括 Checkers 和 9x9 Hex，也被用于许多其他游戏的残局求解器，包括 Chess 和 Go。我将介绍基本的 PN 算法，以及一些已开发的变体和增强方法——在它们与我的工作相关时。本节的大部分材料基于 2012 年的综述论文“Game-tree search using proof numbers: The first twenty years”以及 Victor Allis 1994 年的学位论文“Searching for Solutions in Games and Artificial Intelligence”中的材料。我推荐这些文献作为有兴趣的读者进一步深入研究的起点。

与 minimax 系列中的搜索算法不同，PN 搜索专门旨在对某个游戏节点进行穷举搜索以求解它，也就是说，证明该局面是某一方的强制胜利（或者在双方都采取最优着法的情况下为强制和棋）。它可以被视为一种在游戏树上的最佳优先搜索算法，根据节点对最终求解根节点之贡献潜力的估计来检查节点。PN 搜索算法旨在为所检查的局面产生一个单一的布尔值——“已证明”或“已否证”（也就是“强制胜利”或“强制失败”）。它们不考虑许多游戏（包括 Ultimate Tic Tac Toe）中存在的第三种可能性，即“在最优着法下强制和棋”。为了弥合这一差距，我们习惯上将一个玩家定义为“攻击方”，并将“胜利”定义为“攻击方获胜”，将“失败”定义为“攻击方失败或和棋”。因此，如果 PN 搜索返回“已证明”，我们就知道该游戏是胜利；如果它返回“已否证”，我们无法判断该游戏是强制和棋还是强制失败。我们将首先考虑两人零和游戏树的一般形态，然后讨论 PN 搜索维护的额外统计数据以及它如何搜索这棵树。

游戏树以某个局面为根，边对应于可能的着法，节点对应于结果局面。在像 Ultimate Tic Tac Toe 这样玩家轮流走子的游戏中，树的每一层交替表示轮到哪个玩家走子： (0) X to play A / | _ (1) O to play B C D_ /|\ / \ /|\
(2) X to play E F G I J K L M N … 我们将 X 定义为攻击方（因此“已证明”意味着“X 获胜”）。

我们注意到节点与其子节点之间存在交替的“AND”和“OR”关系模式，对应于轮到走子的玩家： 通过 De Morgan 定律或只是反向重复我们的分析，否证 A（或任何轮到 X 走子的节点）需要否证其所有子节点，而否证 B（或任何轮到 O 走子的节点）只需要否证其子节点中的一个。

PN 搜索的基本形态是在内存中增量地实例化搜索树，反复启发式地选择一个子节点（称为“最易证明节点”）进行扩展，希望以此朝着求解根节点取得进展。因为我们增量地扩展树，内存中的树将有三类节点：

为了选择最易证明节点，PN 搜索在每个节点维护两个关键统计数据，称为“证明数”和“否证数”，简称“pn”和“dpn”。这些数的构造使得一个节点的（否）证数是该节点后代中为了（否）证该节点而必须检查的数量的下界。让我们考虑上面的游戏树，并根据前面讨论的 AND/OR 性质考虑根的 (d)pn。如前所述，要证明 A，证明其任何一个子节点就足够了，但证明该子节点将需要证明其所有子节点。因此，证明 A 要求在第 (1) 行中存在某个节点，我们证明该节点在第 (2) 行的所有子节点。第 (1) 行中子节点最少的节点是 C；因此，同时证明 I 和 J 就足以证明 A，于是我们有 pn(A) = 2。反过来，否证 A 需要否证 B、C 和 D 全部，但否证这些节点中的每一个只需要否证其任何一个子节点；例如，否证 E、J 和 L 就足以否证 A。所以我们有 dpn(A) = 3。

一般来说，我们发现内部 OR 节点的 pn 等于其任何子节点的最小 pn（因为我们只需要证明一个子节点），而其 dpn 是其子节点 dpn 之和（因为否证需要否证其所有子节点）。对于 AND 节点则相反。用公式表示（令 (\operatorname{succ}(N)) 为一个节点的所有子节点的集合）：

对于终端节点，我们根据游戏结果直接设置证明数：

对于未扩展节点，我们在分配证明数时有一定的灵活性；在一般情况下，我们必须定义一个初始化规则来确定如何初始化证明数。最保守的规则是设置 pn = dpn = 1——回想一下，(d)pn 是必须证明的节点数的下界，而 1 必然是非终端节点的下界。然而，初始化规则是将游戏特定的启发式注入 PN 搜索的一个机会。一种常见的启发式是在从局面可用的着法数量足够廉价计算的情况下，基于该数量来初始化 pn 和 dpn。

如前所述，在每次迭代中，PN 搜索选择一个“最易证明（叶）节点”（“MPN”）进行扩展。选择 MPN 的目标是选择一个节点，如果它被证明或否证，将一路传播回根节点并影响根的 pn 或 dpn。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）