Negamax
Negamax搜索是最小化搜索的一种变体形式，它依赖于双人游戏的零和属性。这种算法依靠的是以下事实{displaystyle{max(a,b)=-min(-a,-b)}来简化最小化的实现。以简化minimax算法的实现。更确切地说，在这样的博弈中，一个位置对棋手A的价值是对棋手B的价值的否定。因此，下棋的棋手寻找的是使下棋产生的价值的否定值最大化的棋步：根据定义，这个后续位置必须已经被对手估价。无论A或B是在下棋，前一句的推理都是有效的。这意味着可以用一个程序来为两个位置估值。这是对最小化的编码简化，最小化要求A选择具有xxx价值的后手的棋，而B选择具有最小价值的后手的棋。它不应与negascout相混淆，后者是一种通过巧妙地使用1980年代发现的α-β剪枝法来快速计算最小值或否定值的算法。请注意，alpha-beta修剪本身就是一种通过避免搜索某些不感兴趣的位置来快速计算位置的最小值或xxx值的方法。大多数对抗性搜索引擎都使用某种形式的negamax搜索进行编码。Negamax基础算法NegaMax在与minimax搜索算法使用的相同的博弈树上运行。树上的每个节点和根节点都是一个双人游戏的游戏状态（如游戏板配置）。向子节点的转换代表了即将从给定节点开始下棋的棋手的可用动作。negamax搜索的目标是为正在根节点下棋的棋手找到节点得分值。下面的伪代码显示了negamax的基本算法，对xxx搜索深度有一个可配置的限制。根节点从它的一个直接子节点继承它的分数。最终设定根节点最佳分数的子节点也代表了最佳棋步。虽然所示的negamax函数只返回节点的最佳得分，但实际的negamax实现会保留并返回根节点的最佳棋步和最佳得分。对于非根节点来说，只有节点的最佳分数是必不可少的。而对于非根节点来说，节点的最佳棋步没有必要保留或返回。可能令人困惑的是，当前节点的启发式价值是如何计算的。在这个实现中，这个值总是从棋手A的角度来计算，其颜色值为1。换句话说，较高的启发式数值总是代表对棋手A更有利的情况，这与正常的最小化算法的行为相同。由于negamax和颜色参数的价值否定，启发式值不一定与节点的返回值相同。
negamax节点的返回值是一个启发式分数，从该节点的当前玩家的角度来看。Negamax分数与棋手A即将下棋的节点的minimax分数相匹配，而棋手A是minimax等价物中的xxx化棋手。Negamax总是为其所有节点寻找xxx值。因此，对于棋手B的节点，最小化分数是其negamax分数的否定值。在最小化等价物中，玩家B是最小化玩家。negamax实现中的变体可能会省略颜色参数。在这种情况下，启发式评估函数必须从节点的当前玩家的角度返回数值。带有α-β修剪的Negamax针对minimax的算法优化也同样适用于Negamax。α-β修剪可以减少negamax算法在搜索树中评估的节点数量，其方式与minimax算法的使用类似。使用α-β修剪的深度有限的negamax搜索的伪代码如下。函数negamax(node,depth,α,β,color)是如果深度=0或节点是一个终端节点，则返回颜色×节点的启发式值α(α)和β(β)代表在给定的树的深度上子节点值的下限和上限。Negamax将根节点的参数α和β设置为可能的最低和最高值。其他搜索算法，如negascout和MTD(f)，可能会用alte初始化α和β。
