Alpha-Beta剪枝算法

最近做了一个中国象棋项目，其中用到了Alpha-Beta剪枝算法，在此做个记录。

Alpha-Beta剪枝算法是一种传统的搜索算法, 它在博弈算法中有着非常广泛的运用,它大大减少了相同搜索深度下的计算量。

Alpha-Beta剪枝算法是由最大值和最小值算法得来的，该算法是一个0总和算法，即一方要在可选的情况下使其优势最大化，使对手优势最小化，而开始的时候为0.

example：

假设方框是极大值的节点，圆是极小值的节点，B的值为18，D的值为16，而C是极小值，因此C<=16，A取max(B,C)，因而没有必要考虑C的其他子节点。

Alpha-Beta剪枝算法(递归伪代码)：

 1 int AlphaBeta(int depth, int alpha, int beta){
 2    if (depth == 0) {
 3     　　return Evaluate();
 4     }
 5     GenerateLegalMoves();
 6     while (MovesLeft()) {
 7         MakeNextMove();
 8     　　val = -AlphaBeta(depth - 1, -beta, -alpha);
 9     　　UnmakeMove();
10     　if (val >= beta) {
11     　   return beta;
12     　}
13     　if (val > alpha) {
14     　　　alpha = val;
15     　}
16     }
17    return alpha;
18 }

参考：http://www.xqbase.com/computer/search_alphabeta.htm