简单游戏的制胜策略算法[2名玩家在网格场上移动]

Question

我在这个游戏中寻找一个获胜的算法：

-game在网格上播放(我们可以说它的无限网格)

-there是两个球员，1(橙色)先发，他的移动是长的1，2 (绿)是第二，他的移动是长的，他们轮流。

对于第二个玩家来说，-goal是指先发(他赢了，即使1人到达那里)。

对于第一个玩家来说，-goal就是永远不要到达起点，或者以某种方式阻止游戏，这样就不会有更多的动作了。

-they不能通过他们已经到达的路径(点)

以下是游戏的一些例子(在第3场中，橙色玩家获胜，因为没有更多的动作)

我将非常感谢在这方面的任何帮助(链接，如果这是已知的解决算法，或伪代码，或只是简单的纯文本，从中可以理解的策略)。

谢谢

m，

Answer 1

试试这个：

由于橙色玩家只移动一个，移动方向远离起点的方向。1.一开始移动顶部(建议)，格林可以在移动后得到7个可能的分数。检查从现在开始的方向。2.如果它是起点左下角，则向下或向左移动橙色。这样，你就永远不会向起点移动。

为了进一步改进这一点，您可以在数据库中存储到此之前播放的所有移动，并根据以下内容决定是向下移动还是向左移动(在步骤2中)：

如果在当前位置的左边有更多的移动，与当前位置底部的移动相比

PS:最初的动作可以是任何东西。我们的策略是离开，避免在两次行动之间陷入僵局。

Answer 2

橙色总是可以通过不断地远离原点而赢得胜利。基于平面上不相交的随机游动，这种策略对任何绿色的尝试都是鲁棒的。

如果你想做正确的分析，下面是开始的方法。

对于大多数博弈论的问题，关键是从最后向后工作。让我们先做绿色的，然后假设我们有最后一步。现在，为了保持简单，让我们忽略“避免优先路径”的条件。一旦我们理解了更简单的版本，我们就可以把它加回去。

让我们先离题一下，在我们的简化版本中，“距离”一定是“距离”。一旦我们考虑障碍，所谓的“两点之间的距离”，我们指的是最短路径的长度，不相交现有的游戏路径之间的给定点。如果没有这样的路径，假设距离是无限的。

在简单的版本中，每个green的移动都会改变到原点的距离0或2，而每个橙色的移动都会改变到原点的距离1。

如果我们击中了原点，我们就赢了，所以如果橙色使我们距离原点2的话，我们就会赢。因为橙色每次移动一步，如果我们从原点降落距离1，我们就赢了(因为橙色必须移动到距离0或距离2)。如果我们把距离从原点降到3，那么如果橙色移动到距离2，那么我们就赢了，但如果他移动到距离4，我们就不一定赢了。在这种情况下，我们可以很快地看到，橘子总是能不断地远离原点(就像在一个不相交的随机游走中)，我们永远也不会回来。然而，我们仍然有有用的信息，即有两个因素是关键：

1. 均等很重要。格林想从一个偶数的距离出发去赢得胜利。
2. 绿色必须绕着小径绕来绕去，以阻止橘子跑开。