1

我有一个带有 alpha-beta 修剪的普通 Negamax 算法，它是通过迭代加深 (ID) 启动的。我认为要真正使用 ID，我将从深度 1 计算的有效移动保存在表格中，所以下次我去深度 2 并且相同的原始位置到达时，我可以从表格中获取有效移动来节省时间. 但是，我发现这个想法并没有真正节省任何时间，这让我想到：

  1. 我从未见过有人这样做，出于某种原因不值得吗？
  2. 我的实现是错误的？
  3. 我对 Negamax 的工作方式感到困惑，也许这首先是不可能做到的？

这是原始的迭代调用，以及 Negamax 函数本身的片段：

self.valid_moves_history = []
for depth in range(1, s.max_search_depth):
    move, evaluation = self.negamax(gamestate, depth, -math.inf, math.inf, s.start_color)

# ----------------------------------------------------------------------------

def negamax(self, gamestate, depth, alpha, beta, color):

    if self.zobrist_key in self.valid_moves_history:
        children = self.valid_moves_history[self.zobrist_key]
    else:
        children = gamestate.get_valid_moves()
        self.valid_moves_history[key] = children

    if depth == 0 or gamestate.is_check_mate or gamestate.is_stale_mate:
        return None, e.evaluate(gamestate, depth) * color

    # Negamax loop
    max_eval = -math.inf
    for child in reversed(children):
        gamestate.make_move(child[0], child[1])
        score = -self.negamax(gamestate, depth - 1, -beta, -alpha, -color)[1]
        gamestate.unmake_move()
        if score > max_eval:
            max_eval = score
            best_move = child
        alpha = max(alpha, max_eval)
        if beta <= alpha:
            break

我的完整程序中最耗时的任务是这样分布的（占游戏总运行时间的百分比）：

  • 计算有效动作：60%
  • 评估函数（目前中等复杂度）：25%
  • Negamax 本身具有查找、表格保存等功能：5%
  • 做出/取消动作：4%

计算移动时间这么高是否正常/合理？这是我首先考虑将有效动作保存在列表中的主要原因。

或者有人可以解释为什么这是一个好/坏的主意，我应该怎么做？感谢您的任何意见。

4

1 回答 1

0

我知道这个线程在这一点上已经很老了，但我认为这对某些人仍然有用。您正在谈论的整个主题在 Minimax 中称为转置表，您可以找到许多指向该主题的链接。Negamax 与 Minimax 相同，只是您没有为 Max 和 Min 播放器提供单独的函数，而是您只需调用一个 max 函数并将其转换为负数。我认为首先实现移动排序可能对您更有用，因为它可以使您的程序速度加倍。您还可以找到一种更有效的方法来找到有效的移动来加速程序。

于 2021-07-30T17:22:33.937 回答