带有列表的 Python 回合制递归

Question

我正在为我的一个 CS 类(class)解决一个问题，并且非常有信心我的想法是正确的，只是在我实现它时却没有得到正确的答案。

游戏是:有两个玩家和一个数字列表(即 [3,7,8,1,6,4,5])。每个玩家轮流从列表的两端选择一个数字。一旦选择了一个数字，它就会从列表中删除，然后对手可以从这个新列表中选择他们想要的一局。目标是在列表为空时获得最大的数字总和。

我的想法:假设我们从简单列表 [1,2,3,4,5] 开始。当玩家 1 从开头或结尾选择一个数字(1 或 5)时，我们现在有一个较小的列表可供对手选择。那么让我举一个使用这个列表的例子:

我选5，新的列表是[1,2,3,4]，对手可以选择。我不知道他们会选择列表的哪一端，但我知道只能是1或者4. 如果是 1，那么当再次轮到我时，我剩下 [2,3,4]。如果他们选择 4，我就剩下 [1,2,3]。如果我选择 1，它们剩下 [2,3]，如果我选择 3，它们剩下 [1,2]，等等，直到列表中没有数字。对方也在想方设法的争取最高分，所以他们不会一直贪心的选大数。玩家同样聪明，所以他们都会使用完全相同的策略来为自己获得最高分。

这是一个明显的递归问题，每次都在较小的列表上。

注意:我不是在寻找要提供的代码。因为这是一门 CS 类(class)，所以我真的更愿意得到关于我可能做错了什么的提示，以便我可以学习而不是得到代码。

这是我写的代码:

def Recursive(A):
    # check if there is only one item left. If so, return it 
    if len(A) == 1:
         return A[0]

    # take the left item and recurse on the list if the opponent 
    # were to take the left side, and the list if the opponent 
    # were to take the right number
    takeLeftSide = A[0] + max(Recursive(A[1:-1]), Recursive(A[2:len(A)]))
    takeRightSide = A[-1] + max(Recursive(A[0:-2]), Recursive(A[1:-1]))

    return max(takeLeftSide, takeRightSide)

if __name__ == '__main__':
    A = [5,8,1,3,6]
    print Recursive(A) 

我相信我应该期望 12，但在某些情况下我的输出会给出 19 和 14。

感谢您的帮助，我已经为此工作了几个小时，而且我知道一旦您尝试深入研究递归，就会变得困惑和困惑。

Answer 1

您的函数根据此输入返回 19，它应该这样做。你从来没有真正考虑过第二个玩家的行动，你只是假设第二个玩家会选择让玩家 1 最大化他们的分数的数字。你应该使用

takeLeftSide = A[0] + (sum(A[1:]) - Recursive(A[1:]))
takeRightSide = A[-1] + (sum(A[:-1]) - Recursive(A[:-1]))

相当于

takeLeftSide = sum(A) - Recursive(A[1:])
takeRightSide = sum(A) - Recursive(A[:-1])

但更容易理解。

这是说一个玩家可以从 1 端得到一个数字，然后其他玩家没有从剩余数字中得到的所有点数。如果您需要更多信息，或者我不清楚，请查看 the minimax algorithm.