chess - Negamax 截止返回值？

问题描述

我的 Negamax 算法有问题，希望有人能帮助我。

我正在用 Cython 写它

我的搜索方法如下：

cdef _search(self, object game_state, int depth, long alpha, long beta, int max_depth):
    if depth == max_depth or game_state.is_terminated:
            value = self.evaluator.evaluate(game_state) evaluates based on current player
            return value, []

    moves = self.prepare_moves(depth, game_state) # getting moves and sorting 
    max_value = LONG_MIN

    for move in moves:
        new_board = game_state.make_move(move) 
       
        value, pv_moves = self._search(new_board, depth + 1, -beta, -alpha, max_depth, event)
        value = -value

        if max_value < value:
            max_value = value
            best_move = move
            best_pv_moves = pv_moves

        if alpha < max_value:
            alpha = max_value

        if max_value >= beta:
            return LONG_MAX, []

    best_pv_moves.insert(0, best_move)

    return alpha, best_pv_moves

在许多示例中，您在检测到截止后中断，但是当我这样做时，算法找不到最佳解决方案。我正在测试一些国际象棋谜题，我想知道为什么会这样。如果我在检测到截止后返回最大数量它工作正常但我需要很长时间（深度 6 为 252 秒）......

速度：节点前秒：21550.33203125

或者，如果您有其他改进，请告诉我（我使用转置表、pvs 和杀手启发式）

标签： chessminmaxnegamax

原来我使用了c限制

cdef extern from "limits.h":
    cdef long LONG_MAX
    cdef long LONG_MIN

当你尝试反转 LONG_MIN 时，使用 -LONG_MIN 你会得到 LONG_MIN，因为溢出？

chess - Negamax 截止返回值？

问题描述

解决方案

推荐阅读