将 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 的行

在这里，您不需要交替评估 min 和 max，但给予 minplayer 的分数始终是正玩家的负数这一事实足以让您始终可以评估 max 以获得正确的分数。

笔记：-

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