我正在开发一个奥赛罗游戏玩家，并实现了带有alpha-beta剪枝的minimax算法。之后，我在网上做了大量研究，发现大家都在使用一种名为“negamax”的算法。似乎大多数人认为negamax比minimax更快（我认为这是因为它不需要在最小化和最大化玩家之间切换），所以如果转换难度不大，我想把我的minimax算法改成negamax。

我想知道使用negamax能快多少，以及是否有人能提供一些建议或代码，帮助我将我的minimax代码转换为negamax算法，这将非常有帮助！

这是我的minimax算法：

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

由于有人问到了我的Alpha-beta剪枝，这里是相关的代码：

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

回答：

我认为你已经实现了minimax算法，这已经足够好了，但你需要实现minimax中最重要的优化，即alpha-beta剪枝，这对你的代码来说是一个简单的修改，但能显著提高速度。

编辑:-

注意到你已经使用了alpha-beta剪枝，所以你可以实现negamax，但你认为它不需要切换的想法是不正确的，但它确实简化了minimax的代码（我怀疑速度上没有显著的改进）。这里的想法是，一个玩家的移动得分总是另一个玩家的负值，但幅度相同，这允许你计算max(a,b) = -min(-a,-b)。

简单的转换如下：

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

这些是使用negamax评估minimax的唯一几行代码

在这里，你不需要交替评估最小化和最大化，而是利用最小化玩家的得分总是最大化玩家的负值这一事实，这样你总是可以评估最大值来得到正确的得分。

注意:-

这在速度上不是显著的优化，但使代码更简单和可读，因此值得一试，但不幸的是，你需要删除很多代码才能将你的代码转换为negamax，所以我建议不要这样做。