图7-19是一字棋游戏中,玩家O采取NegMax搜索时的追寻深度为2的轨迹。注意这里会扩展出所有可能的棋面状态,即使确定玩家X可以稳赢时。每个叶子局面状态的得分都是从玩家的角度出发。我们看到初始局面状态的得分是-2,因为这是所有其子节点的最大负分。
NegMax探测的状态数目和Minimax一样,如果追寻深度为d,每个局面状态的可行走法为b个,那么数目近似于bd。
最后我们可以看到NegMax是如何处理博弈树的叶子节点的。你同样可以在例7-7的代码中看到,这些叶子状态节点都是从玩家的角度出发,也就是说双亲节点从叶子节点选择的MoveEvaluation只是简单的最大化这些叶子节点的得分。
NegMax的操作好似流水线一般,它不需要来回切换MAX或者MIN层级。我们回忆一下Minimax是如何要求评估函数要从将要走棋的玩家的观点来进行评估的。在NegMax中,局面状态是基于走棋之后的玩家的视角。因为算法是选择“负分最大的子节点”。
图 7-19 NegMax探测