Research Re: search & Re-search

搜索算法通常按照它们的节点扩展策略进行分类。其中一种选择是深度优先策略，一种简单的回溯策略，按照生成后继节点的顺序遍历搜索空间。另一种选择是最佳优先策略，它旨在使用特定领域的启发式信息。通过首先探索有前途的搜索空间部分，最佳优先算法通常比深度优先算法更有效率。 在像国际象棋和跳棋等下棋游戏中，搜索的效率非常重要。鉴于最佳优先算法在其他领域的成功，人们也期望它们在极小化最大值游戏中得到应用。然而，所有高性能的下棋程序都基于深度优先算法。 本研究着眼于深度优先算法AB和最佳优先算法SSS。关于这些算法的普遍看法是，SSS提供了更高效的搜索潜力，但其复杂的公式和指数级的内存需求使其不切实际。这项工作的理论部分表明，这两种算法之间有一个令人惊讶的简单联系 - 对于所有实际目的而言，SSS是AB的一个特殊情况。随后的实证证据证明了关于SSS的普遍看法是错误的：它不是一个复杂的算法，也不需要太多的内存，而且它也不比深度优先搜索更高效。

比较深度优先搜索和最佳优先搜索在解决极小极大游戏中的效率和实用性，验证现有观点是否正确。

论文发现最佳优先搜索(SSS)实际上是深度优先搜索(AB)的一个特例，因此并不比深度优先搜索更高效。

论文通过理论和实验研究发现，最佳优先搜索并不比深度优先搜索更高效，且并不需要过多的内存和复杂的公式。实验使用了极小极大游戏，论文的结论对于游戏AI领域有重要的指导意义。

近期相关研究包括使用深度学习优化极小极大游戏AI的研究，如《Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm》。