标签: negamax

我对这两个感到困惑。Negamax 只是 minimax 的优化吗？或者 Negamax 是另一种搜索树算法？如果 negamax 是另一种搜索树算法，那么哪个更好？

我正在尝试使用换位表实现 alpha beta 剪枝，我在维基百科中找到了该算法的伪代码：https: //en.wikipedia.org/wiki/Negamax#cite_note-Breuker-1 \n但是我相信这psudocode 是错误的，我认为 alphaOrig 是无用的，而不是：

if bestValue \xe2\x89\xa4 alphaOrig\n        ttEntry.Flag := UPPERBOUND\n

它应该是：

if bestValue \xe2\x89\xa4 \xce\xb1\n        ttEntry.Flag := UPPERBOUND\n

谁能确认我是否正确或向我解释为什么我错了，谢谢！

这里是伪代码：

function negamax(node, depth, \xce\xb1, \xce\xb2, color)\n\nalphaOrig := \xce\xb1\n\n// Transposition Table Lookup; node is the lookup key for ttEntry\nttEntry := TranspositionTableLookup( node )\nif ttEntry is valid and ttEntry.depth \xe2\x89\xa5 depth\n    if ttEntry.Flag = EXACT\n        return ttEntry.Value\n    else if ttEntry.Flag = LOWERBOUND\n        \xce\xb1 := max( \xce\xb1, ttEntry.Value)\n    else if ttEntry.Flag …

这是我上一篇文章的后续内容。该代码运行时没有任何错误，并且可以计算下一个最佳移动。我一直在研究如何将换位表和移动排序合并到我的 negamax 函数中，以使其运行得更快、更准确，但对于像我这样的初学者来说，这似乎有些困难和先进。

你可以在这里找到我的代码。

在研究国际象棋编程维基时，我发现了一些换位表的示例代码：

def negamax(node, depth, alpha, beta, color):
alphaOrig = alpha

## Transposition Table Lookup; node is the lookup key for ttEntry
ttEntry = transpositionTableLookup(node)
if ttEntry.is_valid is True and ttEntry.depth >= depth:
    if ttEntry.flag == EXACT :
        return ttEntry.value
    if ttEntry.flag == LOWERBOUND:
        alpha = max(alpha, ttEntry.value)
    if ttEntry.flag == UPPERBOUND:
        beta = min(beta, ttEntry.value)

    if alpha >= beta:
        return ttEntry.value

if depth == 0 or node is terminal_node:
    return color* heuristic_value_of_node

childNodes = …

我正在制作一个黑白棋玩家，并通过 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 …