休止符搜索

休止符搜索是一种算法，通常用于扩展博弈计算机程序中最小化博弈树的不稳定节点的搜索。它是评估功能的扩展，将评估推迟到位置足够稳定时再进行静态评估，也就是说，不考虑位置的历史或位置的未来移动。它缓解了人工智能引擎在国际象棋和围棋等各种游戏中面临的地平线问题的影响。人类棋手通常有足够的直觉来决定是否放弃一个看起来不好的棋步，或者对一个有希望的棋步进行深入的搜索。静止搜索试图模仿这种行为，指示计算机对不稳定的位置进行比安静的位置更深入的搜索，以确保没有隐藏的陷阱，并获得对其价值的更好估计。任何合理的标准都可以用来区分安静位置和不稳定位置。一个常见的标准是，该局面中存在的棋步能够极大地改变该局面的价值，例如国际象棋或围棋中的擒杀。由于静止搜索的主要动机是为了从静态评价函数中得到一个稳定的数值，因此检测一个简单的启发式评价器在几个阶段中返回的数值的广泛波动也是有意义的，也就是一个历史标准。只要根据标准，位置保持不稳定，静止搜索就会继续。为了使静止搜索终止，棋谱通常被限制在直接处理威胁的棋步上，例如国际象棋中捕捉和夺回的棋步（通常称为”捕捉搜索”）。在高度不稳定的游戏中，如围棋和黑棋，相当大比例的计算机时间可能花在静止搜索上。

地平线效应

地平线效应是人工智能中的一个问题，当从一个游戏树中的特定节点出发的所有棋步都被搜索到一个固定的深度时，就会出现这个问题。搜索深度以外的威胁和机会将不会被察觉。这可能会导致一个程序的奇特伎俩，即采取延迟行动，降低位置，直到把威胁推到搜索深度或地平线之外。当必须处理该威胁时，该位置已经退化得无法挽救了。Quiescence搜索试图通过扩展不稳定位置的搜索深度来缓解这个问题，在这个位置上，启发式数值可能在不同的行动之间有很大的波动。

伪代码

这个伪代码从算法上说明了这个概念。