我正在为我的一个CS课程解决一个问题,我很有信心我有正确的想法,当我实现它时,我没有得到正确的答案。
游戏是:有两个玩家,一个数字列表(即[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]等,直到列表中没有数字为止。对手也在尽力获得最高的分数,所以他们不会一直贪婪地选择更高的分数。球员们同样聪明,所以他们都会用同样的策略为自己获得最高的分数。
这是一个很明显的递归问题。
注意:我不是在寻找代码。由于这是一门计算机科学课程,我真的很希望得到一些提示,告诉我可能做错了什么,这样我就可以学习,而不是得到代码。
这是我写的代码:

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个。
我很感谢你的帮助,我已经在这里工作了好几个小时了,我知道一旦你尝试深入到递归的东西就会变得混乱和混乱。

最佳答案

您的函数基于这个输入返回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])

但更容易理解。
这样做的目的是说一个玩家可以从一端得到一个数字,然后其他玩家不能从剩余的数字中得到的所有点数。
如果您需要更多信息,或者我不清楚,请查看the minimax algorithm.

09-11 19:26
查看更多