第184页 | 算法技术手册 | 阅读 ‧ 电子书库

分析

图7-19是一字棋游戏中，玩家O采取NegMax搜索时的追寻深度为2的轨迹。注意这里会扩展出所有可能的棋面状态，即使确定玩家X可以稳赢时。每个叶子局面状态的得分都是从玩家的角度出发。我们看到初始局面状态的得分是-2，因为这是所有其子节点的最大负分。

NegMax探测的状态数目和Minimax一样，如果追寻深度为d，每个局面状态的可行走法为b个，那么数目近似于bd。

最后我们可以看到NegMax是如何处理博弈树的叶子节点的。你同样可以在例7-7的代码中看到，这些叶子状态节点都是从玩家的角度出发，也就是说双亲节点从叶子节点选择的MoveEvaluation只是简单的最大化这些叶子节点的得分。

NegMax的操作好似流水线一般，它不需要来回切换MAX或者MIN层级。我们回忆一下Minimax是如何要求评估函数要从将要走棋的玩家的观点来进行评估的。在NegMax中，局面状态是基于走棋之后的玩家的视角。因为算法是选择“负分最大的子节点”。