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

Question

每位玩家轮流从装有 50 根香蕉的篮子中取出 1 或 2 根香蕉。清空篮子的玩家获胜。

距离应该使用什么权重，矩阵大小应该是多少？每次有人移动时矩阵都应该改变吗？玩家 1 的移动应该是水平的，而玩家 2 的移动应该是垂直的吗？

感谢阅读

Answer 1

我不确定您为什么特别想使用动态规划 and/or 曼哈顿距离来解决这个难题。这是一款可以找到固定解法的游戏

如果你先走，有3个香蕉，不管你怎么玩，我赢。你选一个，我选两个，反之亦然。如果有 6 个香蕉，同样的逻辑允许我将游戏减少到 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))