使用极小极大值时，我什么时候应该包含局部决策的分数收益？

Question

在“石头游戏”问题中，爱丽丝和鲍勃轮流从开始或结束处拾取一堆石头。目标是最大化 Alice 的总数

def play(turn, left, right):
    if left > right:
        return 0

    end = piles[right] + play(1 - turn, left, right - 1)
    start = piles[left] + play(1 - turn, left + 1, right)

    return max(start, end) if turn == 0 else min(start, end)

alice = play(0, 0, n - 1)

这遵循经典的极小极大算法。

现在让我们来看看

石头游戏II

。在这个问题中，Alice 和 Bob 可以选择下一个 1 令我惊讶的是，经典的极小极大算法无论是轮到爱丽丝还是鲍勃，都会返回相同数量的石头，从而给我们一个不正确的最终答案<= x <= 2m piles of stones, where m is the maximum x somebody has used.

# DOESN'T WORK
def play(left, m, turn):
    if left == n-1:
        return 0

    total = 0
    ans = inf if turn else -inf
    for pos in range(left+1, min(n, left+2*m+1)):
        total += piles[pos]
        value = total + play(pos, max(m, pos - left), 1 - turn)
        if turn == 0:
            ans = max(ans, value)
        else:
            ans = min(ans, value)
    
    return ans

alice = play(-1, 1, 0)

但是，如果我们只在 Alice 的计算中包含总计，它就会突然起作用：

# WORKS
def play(left, m, turn):
    if left == n-1:
        return 0

    total = 0
    ans = inf if turn else -inf
    for pos in range(left+1, min(n, left+2*m+1)):
        total += piles[pos]
        value = play(pos, max(m, pos - left), 1 - turn)
        if turn == 0:
            ans = max(ans, total + value)
        else:
            ans = min(ans, value)
    
    return ans

alice = play(-1, 1, 0)

有人可以解释为什么我们不应该在第二个示例中添加最小化器的本地总数吗？

Answer 1

石头游戏II中的这句话：

假设Alice和Bob发挥最佳，返回Alice可以获得的最大石头数量。

极小极大算法模拟了假设两个玩家都处于最佳状态的过程。在

Stone Game II

中，目标是计算如果双方都发挥最佳状态，Alice 可以收集的最大石头数量。

• 爱丽丝的回合

  ：爱丽丝试图最大化她的分数，因此我们将她在回合中收集的石头（total）添加到结果中。

• 鲍勃的回合

  ：鲍勃的目标是最小化爱丽丝的总得分，因此他不会将他收集的石头添加到得分中；相反，他只是最小化爱丽丝未来的潜在得分。

在第一个代码中，

total

被添加到两个玩家的值中。这假设鲍勃的目标也是最大化他自己的总数，这是不正确的。

在第二个代码中，

total

仅在轮到Alice时才添加到值中。这意味着爱丽丝试图最大化她的总数，而鲍勃试图最小化爱丽丝的总数而不增加他自己的总数。