12-超越α -β剪枝效果的极小化极大算法改进方案

8.4　超越α -β剪枝效果的极小化极大算法改进方案

本章对算法的研究已经非常深入了，多年来已经发现了很多优化技术。其中一些优化技术是特定于某种游戏的，例如，用于国际象棋的“位棋盘”（bitboard）减少了合法棋步的生成时间，但大多数都是适用于任何游戏的通用技术。

有一种常见的优化技术就是迭代加深（iterative deepening）。在迭代加深技术中，搜索函数将先以最大深度1运行，然后以最大深度2运行，再以最大深度3运行，依次类推。达到指定时限时，搜索停止。最后一次完成的搜索深度的结果将会被返回。

在本章的示例中，搜索深度是被硬编码的。如果游戏没有时钟和时间限制，或者我们不关心计算机的思考时长，这当然没有问题。迭代加深技术使得AI能够耗费固定时长来找到下一步走法，而不是固定的搜索深度以及不定的完成时长。

还有一种可能的优化技术是静态搜索（quiescence search）。在静态搜索技术中，极小化极大搜索树将朝着会让棋局发生巨大变化的路线（如国际象棋中的吃子）行进，而不是朝着相对“平静”的棋局发展。理想情况下，采用这种方案搜索不会将计算时间浪费在无聊的棋局上，也就是那些不会让玩家获得明显优势的棋局。

极小化极大搜索的最佳优化方案不外乎两种，一种是在规定的时间内搜索更深的深度，另一种就是改进棋局评分函数。要在相同时间内搜索更多的棋局，就需要减少在每个棋局上耗费的时间，这可以通过提高代码效率或采用运行速度更快的硬件而获得，但也可能会通过后一种改进技术（改进棋局评分函数）而获得。采用更多的参数或启发式算法来对棋局进行评分可能会耗费更多的时间，但最终能够获得更优质的引擎，即用更少的搜索深度找到最优走法。

在用于国际象棋游戏的带α-β剪枝（alpha-beta pruning）的极小化极大搜索算法中，有一些评分函数具有数十种启发式算法，甚至会用到遗传算法对这些启发式算法进行调优。国际象棋游戏中马的吃子应该评分多少？与象的得分一样吗？要区分一个国际象棋引擎是合格还是优秀，这些启发式算法就是秘密武器。