MiniMax算法优化:Alpha-Beta剪枝算法

alphabeta

通过前面两次博客的介绍,现在我们已经可以在手机上写出一个三子棋游戏,并且可以使用Minimax算法为游戏添加AI,让程序也学会下三子棋。但是其中Minimax算法是使用了一种全局搜索,这个算法会遍历整个博弈树的所有节点,在三子棋中,博弈树的深度和广度并不是很大,但是如果到了五子棋或者其他棋类,博弈树的深度和广度将会成指数型增长,这下再不优化算法的话,程序走一步棋就可能要运算几天了,特别浪费时间。这篇博客将会讲述Minimax算法的优化。其中包括负极大值算法和Alpha-Beta剪枝算法。

优化1:搜索深度限制

回顾上一篇文章的算法思路和代码,这个博弈树会被完成的搜索,我们的Minimax算法是基于深度优先搜索的一个算法。

关于如何对一颗博弈树进行搜索,我们面临着以下几种选择:

  • 是在内存中生成整个树进行搜索,还是在搜索的过程中仅仅产生想要搜索的节点?
  • 广度优先搜索还是深度优先搜索?
  • 有必要生成整棵树嘛,那样可能会耗费大量系统资源

所以权衡利弊,几乎任何人使用Minimax算法时都会去选择深度优先搜索,这样在过程中仅仅生成树的一小部分,之后搜索过的部分立即被删去,这样更加节省内存。

在上一篇博客中,搜索的深度很大,因为我们编写时并没有限制他的搜索深度,这样在最坏情况下(棋盘中没有棋子),程序对每一个节点的搜索深度可能会达到9(平局情况,棋子占满棋盘),这样对于三子棋来说可能不算什么,三子棋的博弈树节点也不是很多,但是对于五子棋那类棋盘很大的棋类游戏呢?之前的代码还是会进行一个完全树搜索,五子棋空的棋盘有10×12个格子,也就是说搜索深度可能会达到120,而且五子棋可能出现的结果远远多于三子棋,这样的话,第一下落子就够程序算个几天都出不来,所以必须进行深度限制。

可以再算法开始时进行深度检测,如果达到了规定的最大的深度就直接返回,不在进行深度优先搜索。


def MinMax (board, player, depth, maxDepth)
 if ( board.isGameOver() or depth == maxDepth )
    return board.evaluate(player), null

 bestMove = null
 if ( board.currentPlayer() == player )
    bestScore = -INFINITY 

 for move in board.getMoves()
     newBoard = board.makeMove(move)
     score = MinMax(newBoard, player, depth+1, maxDepth)
     if ( board.currentPlayer() == player )
       if ( score > bestScore ) # max
           bestScore = score
           bestMove = move 
       elseif ( score < bestScore ) 
           bestMove = move

     return bestScore, bestMove

MinMax(board, player, 0, maxDepth)

这样每次递归是通过检测depth到达maxDepth就知道有没有到达最大最大深度从而返回评估分值。

这样下来AI是会变笨的,就像下棋一样,厉害的人可以预测出未来5步的情况,上一篇博客的AI可以预测出知道游戏结束的情况,也就是说最坏的情况,AI可以预测出未来9步的情况,但是一旦限制了搜索深度,这就不可能了,如果搜索深度是3的话,AI就只能分析出来棋局未来3步的情况,比如玩家在五子棋中已经落下2个连子,AI就可以发现在未来3步中玩家可能会连成5个子来赢得比赛,但是玩家下了1个子的时候由于搜索深度不足,AI是无法发现玩家可能输赢的情况的。但是只能这么做,而且通过改进估值算法,AI也会变得更加聪明,即使他的搜索深度不在是无穷的。

优化2:负极大值算法 (Negamax Algorithm)

普通的极大极小值算法有一些笨,一方要取最大值而另一方试图取极小值,换句话说,我们总是要检查哪一方要取最大值而哪一方要取最小值,然后执行不同的动作。

Screen Shot 2016-01-25 at 2.16.23 PM

所以引入负极大值算法,消除了两方面的差别,并且使得代码简介优雅,使用负极大值算法,博弈双方都取极大值。

负极大值算法的原理是通过 max(a, b) = −min(−a, −b) 变量a,b中的最大值也是 -a,-b中的最小值得负值,通过这一个定理来简化了算法。


def NegaMax (board, depth, maxDepth)
   if ( board.isGameOver() or depth == maxDepth )
       return board.evaluate(), null

   bestMove = null
   bestScore = -INFINITY

   for move in board.getMoves()
       newBoard = board.makeMove(move)
       score = NegaMax(newBoard, depth+1, maxDepth)
       score = -score # alternates players

       if ( score > bestScore )
           bestScore = score
           bestMove = move

    return bestScore, bestMove

NegaMax(board, 0, maxDepth)th)

注意代码中的符号。负极大值算法的核心就是;父节点的值是各个子节点的值得负数的极大值。如果要这个算法正常运作,需要一点额外的放东西。估值函数必须知道是谁在走棋,如果玩家1的估值是正的话,对于玩家2就要返回负值。

优化3:Alpha-Beta剪枝算法

AlphaBeta剪枝算法是对Minimax方法的优化,它们产生的结果是完全相同的,只不过运行效率不一样。

就像前文介绍的一样Minimax算法会对整个博弈树进行完成整搜索,这样就造成了很多的浪费和不必要,比如在进行第一次搜索的时候算法已经算出下一步走那里可以赢得比赛,但是算法还是会完成剩下的所有搜索,这是没有任何意义的,是对计算机资源的浪费。

Alpha-Beta剪枝算法就是在当知道一个节点的评估情况后,如果处理到后面的节点,有的情况比上一个节点更加糟糕的话,则停止处理,停止深度搜索,开始搜索同层的另外节点。所以说这个算法和MiniMax结果相同,只是时间上的不同。

举个例子:

Screen Shot 2016-01-25 at 2.44.52 PM

对于Max来看,最好的情况是Min的中间节点(评估结果是5),之后开始分析右节点,得到了1,但是1是比5小,显然节点值为5的那个节点要比这个节点结果好,所以直接放弃搜索估值为1的节点的后续节点。

接下来分别解释下Alpha和Beta分别意味着什么

Alpha

  • 任何情况下能得到的最好分值
  • 任何比Alpha分值低的节点都是没用的,可以被修剪掉
  • Max可以得到的最低分值
  • 初始值应该为负无穷大

Beta

  • 对手可能出现的最差的分值
  • 任何比Beta值高的节点都不会被使用
  • Min能得到的最大的分值
  • 初始值应该为正无穷大

 


    def ABNegaMax (board, depth, maxDepth, alpha, beta)
        if ( board.isGameOver() or depth == maxDepth )
            return board.evaluate(), null
        bestMove = null
        bestScore = -INFINITY

     for move in board.getMoves()
         newBoard = board.makeMove(move)
         score = ABNegaMax(newBoard, maxDepth, depth+1,-beta,
                                       -max(alpha,bestScore))
         score = -score
         if ( score > bestScore )
             bestScore = score
             bestMove = move
             # early loop exit (pruning)
             if ( bestScore >= beta ) return bestScore, bestMove
                 return bestScore, bestMove

ABNegaMax(board, player, maxDepth, 0, -INFINITY, INFINITY)

 

 

 

打赏

Leave a Reply

Your email address will not be published. Required fields are marked *