上次的MiniMax算法虽然在效果上已经达到了预期的目的，即不可战胜的棋力，但在效率上仍然不够理想。电脑每次走步都得估计往下N层棋局的所有情况并估值，层数虽然可以控制，但在大棋局（如五子棋，象棋等）游戏中如此生成的博弈树分支叶子仍然相当庞大，由此有了在此基础上进行“剪枝”的改进算法–Alpha-beta剪枝算法（Alpha-Beta algorithms）。此算法主要优点在于其在边生成博弈树时候边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。

还是简单说说算法的基本思想（再次声明此算法是建立在MiniMax算法基础上）：
1. 对于一个MIN节点，若能估计出其倒推值的上确界Beta，并且这个Beta值不大于MIN的父节点(MAX节点)的估计倒推值的下确界Alpha，即Alpha≥Beta，则就不必再扩展该MIN节点的其余子节点了，因为这些节点的估值对MIN父节点的倒推值已无任何影响了，这一过程称为Alpha剪枝。
2. 对于一个MAX节点，若能估计出其倒推值的下确界Alpha，并且这个Alpha值不小于MAX的父节点(MIN节点)的估计倒推值的上确界Beta，即Alpha≥Beta，则就不必再扩展该MAX节点的其余子节点了，因为这些节点的估值对MAX父节点的倒推值已无任何影响了。这一过程称为Beta剪枝。
3. 一个MAX节点的Alpha值等于其后继节点当前最大的最终倒推值，一个MIN节点的Beta值等于其后继节点当前最小的最终倒推值

如果觉得还是有点难以理解（比如我第一次接触就觉得不知所云），看看下面的伪代码：

alpha-beta(player,board,alpha,beta)
    if(game over in current board position)
        return winner

    children = all legal moves for player from this board
    if(max's turn)
        for each child
            score = alpha-beta(other player,child,alpha,beta)
            (we have found a better best move....)
            if score > alpha then alpha = score
            (cut off...)
            if alpha >= beta then return alpha
        return alpha (this is our best move)
    else (min's turn)
        for each child
            score = alpha-beta(other player,child,alpha,beta)
            (opponent has found a better worse move.....)
            if score < beta then beta = score
            (cut off....)
            if alpha >= beta then return beta
        return beta (this is the opponent's best move)

简单的说，在MiniMax函数中我们已经知道，对于MIN节点，我们是要找其子节点的最小估值，如上面的代码，当min’s turn时候，我们先估值，如果 score < beta then beta = score，即是把MIN节点的孩子中的估值最小值给赋给Beta，这时候在判断Alpha是否大于等于Beta，Alpha是这个MIN节点的父亲节点的下界，即MAX节点，想一想，MAX应该是要找其子节点的最大估值，而它目前的下界Alpha都大于Beta了，那么可以遇见在将来这个MIN节点肯定不会被它的父亲MAX节点选取了，那么此时这个MIN节点可以停止继续展开孩子估值了，因为注定不会被选取，继续进行只是在浪费时间和资源。

上面讲的这个过程就好像两个人，其中一个人有几个口袋（即是几个MIN节点），每个口袋有几种东西，你（MAX）可以选取其中一个口袋，而无疑他会把你选取口袋里价值最低的物品给你（即MIN取最小值），而你为了获得最大收益只能判断这几个口袋所有的“最低价值物品”中那件还算是最有价值（即是MAX取最大值），MiniMax算法是你把对方所有口袋翻个遍再判断要哪个口袋，无疑这样效率不高。那么Alpha-Beta算法所做的就是：首先你先把第一个口袋里所以物品依次翻出来，假如第一个口袋里是车钥匙和手表，那么假如选这个口袋你只能得到手表，这个就是Beta了，因为此时还没有Alpha值，那么你把这个第一次获得的Beta再向上赋给Alpha，再翻第二个口袋，假如第一次翻出的是咸鱼（ew~~~），先赋给Beta，那么这个咸鱼Beta怎么说都比第一个口袋的表垃圾吧？！即此时手表Alpha >= 咸鱼Beta，因为对方只会把口袋价值最低的物品给你，这个口袋要么最低是咸鱼，要么还有比咸鱼给无语的东西，意味着这个口袋已经不值得在往下翻了，就算里面还有很多东西。

如果你把上面伪代码中的加粗部分去掉，那便是miniMax的算法，所以说这个算法其实是一个通过减少不必要的分支来节约时间资源的“砍枝”算法

估值函数依然采用MiniMax算法中的估值函数，所以就不再多述，下面是Alpha-beta剪枝算法的主算法函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

def comp3(board,player):
 
    t0 = time.time()
    board.output() # print the chessboard
    dep=3
 
    def miniMax(board, alpha, beta, depth=dep, p=player):
 
 
        opponent = { Player_O : Player_X, Player_X : Player_O }
 
        # return if game over
        if board.gameOver():
            if board.gameOver()== player:
                return +100
            if board.gameOver()== opponent[player]:
                return -100
            return 0
 
        if depth!=0:
 
            depth-=1
            for move in board.getValidMoves():
 
                board.makeMove(move, p)
                point=miniMax(board,alpha,beta,depth,opponent[p])
                if (p!=player):
                    #Min's turn
                    if point<beta:
                        beta=point
                    if alpha >= beta:
                        board.undoMove(move)
                        return beta
                else:
                    #Max's turn
                    if point>alpha:
                        alpha = point
                        if (depth==dep-1):
                            # find the bestmove of computer
                            board.bestmove=move
                    if alpha >= beta:
                        board.undoMove(move)
                        return alpha
                board.undoMove(move)
 
        else:
            # evalauate function
            return miniMaxEvalauate2(board,player)
 
 
        if p != player:
            return beta
 
        else:
            return alpha
 
    miniMax(board ,-1000,1000)
    board.makeMove(board.bestmove, player)
    print "miniMax move: %0.3f ms" % ((time.time()-t0)*1000)

结合MiniMax算法和上面的说明应该很容易理解这个函数的，写完这个算法我把它和原来的miniMax算法进行了比试，一直是平手，这也说明在同样遍历深度（3层）情况下，这个算法同样达到了无法战胜的目的，平均时间好像是十多毫秒，因为Tic Tac Toe的棋局较少，所以这个算法的优势体现的不是很明显，但如开头所说，在象棋等大棋局博弈中，这个算法所节省的时间和资源是非常可观的。

代码是需要在上次算法的文件里加入上面的函数即可，所以不再提供新的下载，搜资料的时候发现这里有个Java写的两种算法流程的小demo（文章最底下），感兴趣的可以看看，也许有助于区别理解