负极大值算法
负极大值搜索是极大极小值搜索的一个变体，用于搜索二人零和游戏。
这个算法简化了极大极小值搜索，原理是基于以下事实：max(a, b) = −min(−a, −b)。准确地说，一个着法对玩家A的估值，等于其对玩家B的估值的相反数。因此，当前玩家要搜索的是一个 使其估值的相反数最大化 的着法——其后继的着法分数必须由对方评估——这句话无论对于当前是A还是B都适用，这也意味着，同一个过程可以无论对A还是B都适用。所以，负极大值是对极大极小值算法的简化，不需要对A返回极大值而对B返回极小值。
不要和 NegaScout 算法弄混，这个算法是对于 AlphaBeta 剪枝算法的一个巧妙应用，用于快速计算极大极小值或者负极大值，发现于1980年代——注意 AlphaBeta 剪枝算法本身的目标就是通过放弃搜索无用路径，加快计算极大极小值或者负极大值。
很多的对抗性搜索算法是基于负极大值算法。
基本的负极大值算法
负极大值算法和极大极小值算法使用的是同样的搜索树，每一个节点包括根节点代表了双人游戏中的一个游戏状态——比如棋盘上的一种布局。节点到子节点的转移则代表了当前玩家的一种可能的着法。
负极大值搜索的目标是找到作为根节点的当前玩家的估值。下面的伪代码展示了负极大值算法的基础逻辑，所搜索的最大深度作为参数传入。
01 function negamax(node, depth, color)
02 if depth = 0 or node is a terminal node
03 return color * the heuristic value of node
04 bestValue := −∞
05 foreach child of node
06 v := −negamax(child, depth − 1, −color)
07 bestValue := max( bestValue, v )
08 return bestValue
//玩家A的初始调用
rootNegamaxValue := negamax( rootNode, depth, 1)
rootMinimaxValue := rootNegamaxValue
//玩家B的初始调用
rootNegamaxValue := negamax( rootNode, depth, -1)
rootMinimaxValue := -rootNegamaxValue
根节点的分数是从某一个子节点的值直接继承过来，被选中的最佳分数子节点也就代表了这一步的最佳着法。虽然这段伪代码只返回了 bestValue 作为最佳分数，但是实践中需要为根节点同时返回分数和最佳着法。在基础的负极大值算法中，根节点只有最佳分数和非根节点相关，非根节点的最佳着法不需要保存或者返回。
有一点比较容易迷惑的是当前节点的估值是如何计算的，在上面的伪代码里，这个值是始终以玩家A的角度给出，其 color 值是1——换句话说，估值高意味着局面对A更有利，这种设计是和通常的极大极小值算法一致的。估值结果不一定和节点的返回值——bestValue——保持一致，因为还要在 negamax 函数中乘以 color 参数，节点的返回值——bestValue——是从当前玩家的角度给出的估值。
负极大值的得分和极大极小值算法里当前玩家为A时的估值是一样的，即把玩家A作为极大值玩家。负极大值算法会搜索所有子节点以寻找最大值。对于玩家B层的节点，极大极小分数正好是负极大值分数的相反数，玩家B就相当于极大极小值里的极小层。
还有另外一种变体是省略 color 参数，如果省略的话，估值函数必须以当前玩家的视角返回估值（也就是估值函数必须知道当前玩家是谁，对A和对B的返回值是相反数）
带 AlphaBeta 剪枝的负极大值算法
对极大极小值算法的优化也可以一样用于负极大值算法，如同在极大极小值算法中的作用一样，AlphaBeta 剪枝能减少负极大值算法所搜索的节点数。
以下伪代码展示了一个带有 AlphaBeta 剪枝的负极大值算法：
01 function negamax(node, depth, α, β, color)
02 if depth = 0 or node is a terminal node
03 return color * the heuristic value of node
04 childNodes := GenerateMoves(node)
05 childNodes := OrderMoves(childNodes)
06 bestValue := −∞
07 foreach child in childNodes
08 v := −negamax(child, depth − 1, −β, −α, −color)
09 bestValue := max( bestValue, v )
10 α := max( α, v )
11 if α ≥ β
12 break
13 return bestValue
//玩家A的初始调用
rootNegamaxValue := negamax( rootNode, depth, −∞, +∞, 1)
alpha(α) 和 beta(β) 分别代表了搜索树的某个层级中的节点估值下界和上界。负极大值算法初始设置根节点的 α 和 β 为理论最小值和理论最大值，其他的算法中——比如上面提到的 NegaScout 或者 MTD-f，可能会设置一个更精确的值以优化搜索性能。
当算法检测到一个超过 [α,β] 之外的值时，会切断这个子树——上面伪代码第12行的 ** break ** ——，因此就可以不搜索这一支子树。剪枝完全基于节点的返回值——bestValue。一个节点如果返回了其初始 α 和 β 范围内的值，说明返回的是准确值，这个值就作为算法要返回的值，不需要剪枝和边界限制。如果一个节点返回值超出了这个范围，那么这个值代表了节点估值的上界(如果 value ≤ α) 或者下界 (如果 value ≥ β)。AlphaBeta 剪枝最后会丢弃任何超出范围的值，因为这些值对于最终的搜索结果没有影响。
This pseudocode shows the fail-soft variation of alpha-beta pruning. Fail-soft never returns α or β directly as a node value. Thus, a node value may be outside the initial α and β range bounds set with a negamax function call. In contrast, fail-hard alpha-beta pruning always limits a node value in the range of α and β.
This implementation also shows optional move ordering prior to the foreach loop that evaluates child nodes. Move ordering[2] is an optimization for alpha beta pruning that attempts to guess the most probable child nodes that yield the node’s score. The algorithm searches those child nodes first. The result of good guesses is earlier and more frequent alpha/beta cut offs occur, thereby pruning additional game tree branches and remaining child nodes from the search tree.