我正在制作一个奥赛罗播放器，并实现了一个带α-β剪枝的minimax算法。然后我在网上做了一系列关于最好的算法的研究，不断地听到他们都使用的“negamax”算法。似乎大多数人认为negamax比min i max快（我想是因为它没有在min和max player之间切换？），所以如果不太困难的话，我想把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
既然我得到了一个关于我的α-β修剪的回复，这里是：
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的代码（我怀疑速度上的显著提高）。这里的想法是，一个玩家移动的点数总是另一个玩家的-ve，但大小相同，允许您计算max（a，b）=-min（-a，-b）。
简单的翻译如下：-
score = -negamax(depth-1,-player)
best = max(score,best)
这些只是用negamax求minimax的行
在这里，你不需要评价最小和最大的交替，但事实上，给min player的分数总是消极的积极的球员是足够的，所以你可以总是评价最大，以获得正确的分数。
注：-
从速度上来说，这并不是一个显著的优化，但它使代码简单易读，因此值得一提，但不幸的是，您需要删除大量代码才能将代码转换为negamax，所以我建议您不要这样做。