动态编程：棋盘

白车队从标准的8乘8棋盘的左上角开始。两名选手轮流将车向右或垂直向下水平移动，尽可能多的方格。固定移动不允许，玩家1先走。获胜者是将车放在右下角广场上的选手。说谁会赢，并描述赢球策略。动态编程：棋盘

我有上述声明的问题，我很感兴趣看到别人会如何解决这个问题。我知道有办法计算出车的不同路径。我尝试着用手去解决问题，并且总是好像球员2一直赢得胜利，但我可能会简单地想到它。以动态编程方式接近它似乎是一个好方法。无论如何，任何人都有任何见解，算法或类似的方法来解决这个问题！

来源

2013-02-27 NuNu

解释“固定动作是不允许的”。 – RBarryYoung 2013-02-27 04:17:22

@RBarryYoung在你不能传递轮到你（你不能说你的举动是保持当前的现货您的，因为它会导致僵持）。你必须做出向右移动或向下 – NuNu 2013-02-27 04:27:46

你试过玩这个游戏？你可能能够推理出一个胜利的策略，而不是诉诸于使用电脑。 – 2013-02-27 12:29:10

enter image description here

H8是一个胜利者框，以便高于一切，离开的是失败者框。

一切权利和以下G7（G8和H7）是一个失败者的盒子，所以它是一个胜利者的盒子。

G7是一个胜利者的盒子，所以上面和左边的一切都是输家。

等等......

启动游戏

球员一个只选择去一个失败者框，以便玩家俩永赢。

所有玩家要做的每一件事都是每次轮到他时移动到w箱子。

来源

2013-02-27 04:38:21 jurgenreza

。它使它对描述有帮助 – NuNu 2013-02-27 04:53:00

@NuNu我的荣幸。 – jurgenreza 2013-02-27 04:54:33

玩家二总是赢得任何尺寸的棋盘。通过电路板的大小进行归纳证明。

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

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

QED

来源

2013-02-27 04:49:16 Glenn

甲获胜位置具有以下性质：

所有终端位置获胜。在这种情况下，位置（8,8）是获胜位置
所有可以达到目标位置的位置都是获胜位置。 I.e.最后的行或列中所有的位置都在赚钱的仓位
如果我们能那么我们是在一个成功的位置移动到一个失败的位置，因为未来的球员无法赢得比赛
如果我们只能够移动到一个获胜的位置，那么我们处于失败的位置

考虑到这一点，我们可以创建一个算法，可以告诉我们，如果当前位置是胜利的位置还是失败的位置。使用表（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），你可以通过玩优化和false赢得比赛时，有没有办法让你开始在（X，Y），赢得了isWinning(x, y)函数返回true。

来源

2013-02-27 12:18:48

我认为这是值得大家注意的，所描述的游戏实际上是一个Nim游戏两桩7枚硬币每。 Nim游戏的胜者可以通过在每一堆中硬币的数量来确定。他们称之为Nim-sum，它给出了Sprague-Grundy函数的值。只要Nim-sum是肯定的，这个位置就是胜利。所以考虑你的游戏：7^7 = 0，这是一个失败的位置。每一个对角位置失去，因为无论什么x是，x^x始终为0
的好处是，使用这种技术，你可以在4-在3维和任意大的发挥空间（赢得）这个游戏，以及，5维等。

来源

2013-02-27 12:37:25

动态编程：棋盘

回答

相关问题