Всегда ли Negamax должен возвращать положительное значение?

Question

function negamax(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color * the heuristic value of node
    else
        foreach child of node
            val := -negamax(child, depth-1, -β, -α, -color)
            {the following if statement constitutes alpha-beta pruning}
            if val≥β
                return val
            if val≥α
                α:=val
        return α

Так что, если выше приведен мой код Negamax (скопированный из Википедии), и он называется следующим образом:

negamax(origin, depth, -inf, +inf, 1)

Тогда будет ли эта функция всегда возвращать положительное значение независимо от того, с какой глубиной мы вызываем функцию. Это предполагает, что эвристическое значение само по себе всегда положительно.

Answer 1

Да, если оценка оценки листового узла положительная, negamax вернет положительное значение.Это то, что делает умножение на значение цвета, это гарантирует, что всегда есть встречное отрицание, чтобы полностью изменить обратное отрицание, если есть нечетное количество рекурсивных вызовов negamax.Это связано с тем, что при нечетном количестве рекурсивных вызовов цвет всегда будет равен -1.Если существует четное количество рекурсивных вызовов, все отрицания отменяются, и цвет будет равен 1, что не повлияет на возвращаемое значение.

Обратите внимание, что если вы вызываете negamax с цветом == -1 (это очередь другой стороны, чтобы двигаться), вы должны отменить этот вызов, чтобы получить правильное значение.То есть:

-negamax(origin, depth, -inf, +inf, -1)