使用Minimax算法时，何时需纳入局部决策的得分收益？

问题回顾 #

Stone Game的经典Minimax实现 #

在Stone Game问题中，玩家轮流从首尾取石子堆，目标是最大化Alice的总得分，经典Minimax代码如下：

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)

Stone Game II的错误与正确实现 #

Stone Game II中，玩家可选取1≤x≤2m堆石子（m为之前选取的最大x值）。最初按照经典Minimax思路写的代码无法得到正确结果：

# 错误写法
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回合的计算逻辑（Bob回合不加total），代码即可正常运行：

# 正确写法
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)

核心原因：递归函数的语义定义不同 #

这两个写法的本质差异在于递归函数的返回值语义：

在Stone Game II的正确代码中，play(left, m, turn)的返回值定义为：从当前状态开始，Alice最终能获得的总得分。基于这个定义：

• Alice回合（turn=0）：她选x堆石子拿到的total是自己的得分，加上后续局面中Alice能拿到的得分（递归返回的value），就是当前选择下Alice的总得分，所以要取最大值。
• Bob回合（turn=1）：Bob选x堆石子拿到的total是他自己的得分，和Alice的总得分无关。递归返回的value是Bob操作后，Alice在后续局面中能拿到的得分。Bob会选择让Alice得分最少的选项（因为Bob要最大化自己的得分），所以直接取这些value的最小值即可，不需要加total。

而错误写法中，Bob回合也把total加到value里，相当于把Bob的得分算进了Alice的总得分，完全违背了我们要统计Alice得分的目标，自然会得到错误结果。

再看Stone Game的经典实现，它的递归函数返回的是当前玩家的得分与对手得分的差值（或当前玩家能拿到的总得分），所以无论Alice还是Bob，选完石子后都要加上自己的得分再递归，这和Stone Game II的语义完全不同，不能直接套用相同的逻辑。

内容的提问来源于stack exchange，提问作者Alec