python - 将 Minimax 转换为 Negamax(python)

Question

我正在制作黑白棋玩家，并实现了一个带有 alpha-beta 剪枝的极小极大算法。然后我在网上对最好的算法进行了一系列研究，并不断听到他们都使用的“negamax”算法。似乎大多数人认为 negamax 比 minimax 快(我认为是因为它不会在最小玩家和最大玩家之间切换？)，所以如果不太困难的话，我想将我的 minimax 算法变成 negamax。

我想知道人们是否知道使用 negamax 的速度有多快，以及关于如何将我的 minimax 代码转换为 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

因为我收到了询问我的 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

我认为现在您已经实现了 minimax，这已经足够好了，但是您需要在 minimax 中实现最重要的优化，即 alpha-beta修剪，这将是对您的代码的简单更改，并且速度会有非常显着的提高。

编辑:-

注意到您已经使用了 alpha-beta，因此您可以实现 negamax，但您认为它不切换的想法是不正确的，但它减少了 minimax 的代码(我怀疑速度有显着提高)。这里的想法是，一个玩家的移动点数始终是另一个玩家的 -ve 但相同的幅度允许您计算 max(a,b) = -min(-a,-b)。

这里的简单翻译是:-

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

这些只是使用 negamax 评估 minimax 的行

在这里您不需要交替计算最小值和最大值，但是给定最小玩家的分数总是对正玩家的负值这一事实就足够了，因此您始终可以计算最大值以获得正确的分数。

注意:-

这在速度方面不是很重要的优化，但使代码简单易读，因此值得，但不幸的是，您需要删除大量代码才能将代码转换为 negamax，所以我建议不要这样做。