algorithm - 动态规划：棋盘

Question

一个车从标准 8 x 8 棋盘的左上角开始。两名玩家轮流将车水平向右或垂直向下移动，任意数量的方块。不允许静止移动，玩家 1 先走。获胜者是将车放在右下角广场的玩家。说出谁将获胜并描述获胜策略。

我有上述陈述问题，我很想看看其他人将如何解决这个问题。我知道有办法计算车可以走的不同路径。我尝试手动解决问题，似乎玩家 2 总是赢，但我可能想得太简单了。以动态编程方式接近它似乎是一个不错的方法。无论如何，任何人都有任何见解、算法或类似的东西来解决这个问题！

Answer 1

H8是一个胜利者盒子，所以它上面和左边的所有东西都是失败者盒子。

G7 （G8 和 H7）右侧和下方的所有内容都是失败者框，因此它是获胜者框。

G7是一个胜利者盒子，所以它上面和左边的所有东西都是失败者盒子。

等等……</p>

开始游戏的玩家一只能选择进入失败者框，因此玩家二总是获胜。

玩家二所要做的就是每次轮到他时移动到aw box。

Answer 2

玩家二总是赢得任何大小的棋盘。通过感应板的大小证明。

n=1的情况可以忽略，所以从n=2开始；很明显，玩家 2 在 2x2 棋盘上获胜。

假设玩家 2 总是在大小为 n 或更小的棋盘上获胜。在大小为 n+1 的棋盘上，玩家 1 移动到左列或顶行的位置。玩家 2 然后移动到对角线上的一个位置（这就是您需要的所有策略），然后这是一个大小为 n 或更小的棋盘上的起始位置。

量子点

Answer 3

我认为值得注意的是，所描述的游戏实际上是一个Nim游戏，有两堆，每堆 7 个硬币。Nim 游戏的获胜者可以通过对每堆硬币的数量进行异或来确定。他们称之为 Nim-sum，它给出了 Sprague-Grundy 函数的值。每当 Nim-sum 为正时，该位置就获胜。所以考虑你的游戏：7^7 = 0，这是一个失败的位置。每个对角线位置都在输，因为无论x是什么，x^x总是 0。
好消息是，使用这种技术，您可以在 3 维和任意大空间以及 4 维、5 维空间中玩（并赢得）这个游戏等等。

Answer 4

获胜位置具有以下属性：

• 所有终端位置都在获胜。在这种情况下，位置 (8, 8) 是获胜位置
• 一步中能到达目标位置的所有位置都是获胜位置。即最后一行或最后一列的所有位置都是获胜位置
• 如果我们可以移动到失败的位置，那么我们就处于获胜的位置，因为下一个玩家无法赢得比赛
• 如果我们只能移动到获胜的位置，那么我们就处于失败的位置

考虑到这一点，我们可以创建一个算法来告诉我们当前位置是获胜位置还是失败位置。使用表 ( dpTable) 存储以前计算的结果将避免重复计算。

boolean isWinning(int x, int y) {
    if (dpTable[x][y] != null)
        return dpTable[x][y];

    // From the last row or the last column we can always win the game
    if (x == n || y == n)
        return true;

    for (int i = 1; x + i <= n; i++) {
        // Moving right
        if (x + i <= n && !isWinning(x+i, y) {
            dpTable[x][y] = true;
            return true;
        }

        // Moving down
        if (y + i <= n && !isWinning(x, y+i) {
            dpTable[x][y] = true;
            return true;
        }
    }

    dpTable[x][y] = false;
    return false;
}

当您从位置 (x, y) 开始时，该isWinning(x, y)函数返回true，您可以通过最佳方式赢得游戏，并且false当您无法从 (x, y) 开始并获胜时。