将Minimax转换为Negamax（python）

Question

我正在制作一个黑白棋的玩家，已经实现了一个带有α-β剪枝的极小极大算法。然后我在网上做了很多研究，发现大家都在提到一个叫“负极大”（negamax）的算法。似乎大多数人认为负极大比极小极大要快（我觉得是因为它不需要在最小和最大玩家之间切换？），所以如果不太难的话，我想把我的极小极大算法改成负极大。

我想知道使用负极大究竟快多少，还有没有人能给我一些建议或者代码，帮我把我的极小极大代码改成负极大的算法，这样我会很感激！

这是我的极小极大算法：

def minimax(Board, maximizingPlayer, depth, count):
     # maximizing player has 'B' and minimizing 'W'
     if maximizingPlayer: player, opp = Board.player, Board.opp
     else: player, opp = Board.opp, Board.player

     moves_list = Board.get_moves_list(player, opp)
     best_move = (-1,-1)

     # base case
     if ( depth==0 or moves_list == [] ):
         best_score, parity, mobility, stability = Board.evaluate()
         best_move = (-1, -1)
         return best_score, best_move, count

     # maximizing player
     if maximizingPlayer:
           best_score = float("-inf")
           for move in moves_list:
                new_board = deepcopy(Board)
                new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
                the_score, the_move, count = minimax(new_board, False, depth-1, count+1)
                best_score = max(best_score, the_score)
                if (the_score == best_score):
                    best_move = move

           return best_score, best_move, count
     # minimzing player
     else:
           best_score = float("inf")
           for move in moves_list:
                new_board = deepcopy(Board)
                new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
                the_score, the_move, count = minimax(new_board, True, depth-1, count+1)
                best_score = min(best_score, the_score)
                if (the_score == best_score):
                    best_move = move

           return best_score, best_move, count

因为有人问我关于α-β剪枝的事，这里是相关内容：

def alphabeta(Board, maximizingPlayer, depth, count, alpha, beta):
     # maximizing player has 'B' and minimizing 'W'
     if maximizingPlayer: player, opp = Board.player, Board.opp
     else: player, opp = Board.opp, Board.player

     moves_list = Board.get_moves_list(player, opp)
     best_move = (-1,-1)

     # base case
     if ( depth==0 or moves_list == [] ):
         best_score, parity, mobility, stability = Board.evaluate()
         best_move = (-1, -1)
         return best_score, best_move, count

     # maximizing player
     if maximizingPlayer:
           best_score = float("-inf")
           for move in moves_list:
                new_board = deepcopy(Board)
                new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
                the_score, the_move, count = alphabeta(new_board, False, depth-1, count+1, alpha, beta)
                if (the_score > alpha):
                    alpha = the_score
                    best_move = move
                if beta <= alpha: break

           return alpha, best_move, count
     # minimzing player
     else:
           best_score = float("inf")
           for move in moves_list:
                new_board = deepcopy(Board)
                new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
                the_score, the_move, count = alphabeta(new_board, True, depth-1, count+1, alpha, beta)
                if (the_score < beta):
                    beta = the_score
                    best_move = move
                if beta <= alpha: break

           return beta, best_move, count

Answer 1

我觉得现在你已经实现了最小最大算法（minimax），这已经不错了，但你需要加入一个非常重要的优化，叫做α-β剪枝。这个优化只需要对你的代码做一些简单的修改，就能大幅提升运行速度。

编辑：

我注意到你已经使用了α-β剪枝，所以你可以实现negamax（负最大算法），但你认为它不切换的说法是不对的。实际上，它能减少最小最大算法的代码量（我怀疑在速度上不会有显著提升）。这里的核心思想是，一个玩家的得分总是另一个玩家得分的负值，但绝对值是相同的，这样你就可以用公式max(a,b) = -min(-a,-b)来计算。

简单来说就是：

score = -negamax(depth-1,-player)
best = max(score,best)

这些只是用negamax来评估最小最大算法的代码行。

在这里，你不需要交替评估最小值和最大值，因为给最小玩家的分数总是正玩家分数的负值，这样你就可以直接评估最大值来得到正确的分数。

注意：

这在速度上并不是一个显著的优化，但能让代码更简单易读，所以还是值得的。不过不幸的是，你需要删除很多代码才能把你的代码转换成negamax，所以我建议不要这样做。