在人工智能的机器博弈中首先学习的就是极小极大值搜索Minimax，有人翻译成Minmax，少写了中间的字母i，感觉意思不够准确。
维基百科中给出的伪代码如下： 加上了中文翻译。
function minimax(node, depth) // 指定当前节点和搜索深度 // 如果能得到确定的结果或者深度为零，使用评估函数返回局面得分 if node is a terminal node or depth = 0 return the heuristic value of node // 如果轮到对手走棋，是极小节点，选择一个得分最小的走法 if the adversary is to play at node let α := +∞ foreach child of node α := min(α, minimax(child, depth-1)) // 如果轮到我们走棋，是极大节点，选择一个得分最大的走法 else {we are to play at node} let α := -∞ foreach child of node α := max(α, minimax(child, depth-1)) return α;
我实现的C++代码：
// 返回值是搜索的评估值，board是当前的局面 // 这里30000是红方取胜的局面，-30000是黑方取胜的局面int MiniMaxSearch(int depth) { // 所谓确定的结果，在象棋里就是被将死的情况 // 当着法生成中已经有了将军的判断，下面这几行的if else是不需要的 // 因为如果某方被将死了，n_moves将等于0，说明产生不出合法的着法，此时就直接返回-30000或30000了 if (board.WhichTurn == TURN_BLACK && board.IsCheckmated()) { return -30000; } else if (board.WhichTurn == TURN_RED && board.IsCheckmated()) { return +30000; } if (depth == 0) return Evaluate(board); // 搜索达到指定深度时 int bestValue = (board.WhichTurn == TURN_RED) ? -30000 : 30000; Move move_list[256]; int n_moves; n_moves = GenerateAllMoveList( board, move_list ); for(int i=0; i bestValue)? value : bestValue; else // 极小节点 bestValue = (value < bestValue) ? value: bestValue; } return bestValue; } 在这个网站有一个java applet可以用图示的方式清晰地演示minimax和alphabeta剪枝的运行过程。 http://ksquared.de/gamevisual/launch.php?agent=2
NegaMax的算法更简洁：
但要注意：NegaMax中的评估函数，对轮到谁走棋是敏感的。
例如：
在MiniMax中，轮红方走棋时，假如评估值为100，轮黑方走棋评估值仍是100。
但在NegaMax中，轮红方走棋时，假如评估值为100，轮黑方走棋时评估值要为-100。
1 int Search::NegaMax(int depth, int maxDepth) 2 { 3 /* 在着法生成中有将军的判断，这里就不需要再进行判断了。否则还要进行终止局面的判断。 4 */ 5 6 if (depth == maxDepth) return Eval::Evaluate(board); 7 8 int bestScore = -30000 + depth; //这种写法可以搜索最好的杀着 9 10 Move moveList[256];11 int countMoves;12 13 // 着法生成中要进行将军的判断，也就是轮到红方走棋时，红方的走完后，帅不能被将军14 countMoves = MoveGenerator::GenerateAllMoveList( board, moveList );15 16 for(int i=0; i bestScore)? score : bestScore;22 }23 return bestScore;24 }