将Minimax转换为Negamax（python）

Question

我正在制作一个奥赛罗播放器，实现了一个带有alpha-beta剪枝的极大极小算法。然后，我在网上对最好的算法做了一些研究，并不断听到他们都使用的“negamax”算法。好像大部分人都觉得negamax比minimax快(我觉得是因为它不在min和max播放器之间切换？)，所以我想把我的minimax算法变成negamax，如果那不是太难的话。

我想知道人们是否有任何洞察力，有多少更快地使用Nigamax，以及任何提示或代码，如何把我的极小极大代码变成一个Nigamax算法，将不胜感激！

这是我的最小最大值算法：

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

Answer 1

我认为现在你已经实现了最小化，它已经足够好了，但是你需要实现最小化中最重要的优化，那就是阿尔法-贝塔修剪，这将是对你的代码的一个简单的改变，速度有了非常显著的提高。

编辑：-

注意到你已经使用了alpha beta，所以你可以实现negamax，但你认为它不切换的想法是不正确的，但它减少了minimax的代码（我怀疑速度的显著提高）。这里的想法是，一个玩家的移动点数总是与另一个玩家相同，但大小相同，可以让你计算max（a，b）=-min（-a，-b）。

这里简单的翻译是：-

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

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

在这里，你不需要评估最小和最大的替代，但事实是，给MinPlayer的分数总是负的积极的球员是足够的，所以你可以总是评估最大得到正确的分数。

注意：-

就速度而言，这不是显着的优化，但使代码简单易读，因此值得一试，但不幸的是，您需要擦除大量代码才能将代码转换为nigamax，因此我建议不要这样做。