如何使用曼哈顿距离来解决这个游戏

Question

每个玩家轮流，从50个香蕉篮中取出1或2个香蕉。排空篮子的球员获胜。

应将其用于距离的权重，矩阵大小应该是多少？每当有人采取行动时，矩阵应该改变吗？玩家1的动作是否应该是水平的，玩家2的移动垂直移动？

感谢您的阅读

Answer 1

我不确定为什么您要专门使用动态编程和/或曼哈顿距离来进行此难题。这是您可以找到固定解决方案的游戏。

如果您先去，有3个香蕉，无论您玩什么，我都会赢。您选择一个，我选择两个，反之亦然。如果有六个香蕉，相同的逻辑可以使我可以将游戏减少到3个香蕉盒。实际上，对于任何3N香蕉，我都可以将游戏减少到3(n-1(香蕉。如果香蕉的数量不是三个中的倍数，那么您可以将其作为三个中的倍数(通过去除一两个香蕉(，并确保胜利。

对于K香蕉，您始终删除k % 3。如果k % 3 == 0，除非您的对手犯错，否则您会丢失，所以请玩任何喜欢的东西。就是这样。

Answer 2

我同意@pdpi，但是如果您坚持使用动态编程解决此问题，那么您应该做这样的事情：

f(left_in_the_basket, mine)
    if left_in_the_basket is 2 && turn is mine:
        return 1
    if left_in_the_basket is 1 && turn is mine:
        return 1
    if left_in_the_basket is 2 && turn is not mine:
        return -1
    if left_in_the_basket is 1 && turn is not mine:
        return -1
    return max (f(left_in_the_basket - 1, not mine), f(left_in_the_basket - 2, not mine))