寻找一种算法来平衡这个游戏。

Question

我试图提取出问题的那一部分，这是我正在做的一个更大项目的一部分（不是作业）。我认为将其描述为游戏最容易理解（因为我需要用它来完成我正在开发的游戏）。按照我描述的方式，这是一款单人游戏。

开始你从两个位置中选择一个：

• 重量(2,0,-1)和一个 红色 操作
• 重量(3,1,-1)和两个 红色 操作

结束当你没有了任何操作时，游戏就结束了。目标是以重量 (0,0,0) 结束游戏。

有两种操作 红色 和 蓝色。给定一个操作，你可以选择其中四个棋子之一：A，B，C，D，它们会给你额外的重量，也可能给你额外的操作。以下是规则：

• 在红色 操作中：

  • A 增加重量 (0,-2,-1)
  • B 增加重量 (1,-1,-1) 并增加一个红色操作
  • C 增加重量 (2,0,-1) 并增加两个红色 操作
  • D 增加重量 (0,2,1) 并增加两个蓝色 操作

蓝色 操作的规则类似，但是重量的前两列被交换，最后一列被反转，并且操作类型被颠倒，因此你得到以下结果：

• 在蓝色 操作中：

  • A 增加重量 (-2,0,1)
  • B 增加重量 (-1,1,1) 并增加一个蓝色操作
  • C增加(0,2,1)的权重和两个蓝色操作
  • D增加(2,0,-1)的权重和两个红色操作

问题：这个游戏能赢吗？

我正在尝试编写一个程序，通过选择操作来赢得游戏，使最终平衡点达到(0,0,0)，当你没有更多的操作时。但是我似乎做不到。所以现在我认为也许没有算法可以赢得这个游戏。我真的很想知道为什么会这样。如果有人有任何想法可以帮助我证明这一点，请告诉我！或者，如果您尝试并找到了赢的方法，请也告诉我。谢谢！！

- Daniel

---

确认一下 - 你是从 (1, 0, 0) 和一个随机颜色的棋子开始吗？此外，在每个步骤中，所有棋子都可用吗？还是每个棋子只能使用一次，或者你会得到一组随机选择的棋子？ - templatetypedef

当您尝试通过枚举所有可能的移动来进行暴力破解时会发生什么？ - mbeckish

你是用什么方法做的？广度优先吗？ - Fantius

@Fantius 两种都有。我在一个处理器上使用BFS，在另一个处理器上使用DFS。 - Daniel

你尝试过查看权重的绝对和会发生什么吗？(x,y,z) -> |x| + |y| + |z| - PengOne

Answer 1

我可能错过了什么，但凭直觉看，这个步骤序列应该有效：

• 从“权重为(2,0,-1)和一个红色的棋子”开始
• 拿起一个红色的棋子、C块，它“增加权重(2,0,-1)和两个红色的棋子”，使你剩下权重为(4,0,-2)和两个红色的棋子。
• 拿起一个红色的棋子、A块，它“增加权重(0,-2,-1)”，使你剩下权重为(4,-2,-3)和一个红色的棋子。
• 拿起一个红色的棋子、D块，它“增加权重(0,2,1)和两个蓝色的棋子”，使你剩下权重为(4,0,-2)和两个蓝色的棋子。
• 拿起一个蓝色的棋子、A块，它“增加权重(-2,0,1)”，使你剩下权重为(2,0,-1)和一个蓝色的棋子。
• 再拿起一个蓝色的棋子、A块，它“增加权重(-2,0,1)”，使你最后剩下权重为(0,0,0)且没有棋子。

再来点更详细的解释：

move        weight         plays
------      ---------      -------
            (2,0,-1)       red
red C       (4,0,-2)       red x2
red A       (4,-2,-3)      red
red D       (4,0,-2)       blue x2
blue A      (2,0,-1)       blue
blue A      (0,0,0)        -

. . . 不行吗？

---

补充编辑：

我是如何找到这个解决方案的：

由于这个问题引起了很多人的兴趣，也许我应该解释一下我是如何找到上面的解决方案的。基本上是运气；我偶然发现了两个关键的观察点：

• 红 A 和 红 D 在重量方面互相抵消（前者添加（0，-2，-1），后者添加（0，2，1）），并共添加了两个蓝色 操作（均来自 红 D），没有红色操作；因此如果你在一起立即播放，你就可以"将"两个红色操作转换为两个蓝色操作。
• 蓝 A 抵消了初始重量（它添加了 （2、0、-1））并不添加任何操作，因此整个问题可以通过"将"一个红色操作转换为一个蓝色操作来解决。

那给了我一个很好的开端。我从红 C开始，以便得到我可以"转换"为两个蓝色操作的两个红色操作，我立即发现红 C在重量上也是蓝 A的 "相反"，因此也可以用蓝 A取消。在我的脑海中，它看起来完美地抵消了；然后我写下来确保。

证明它是最小的：

而且，虽然当时我没有费心去推理，但我也可以证明这是那个起始位置的“最小”获胜序列——我的意思是，如果一个序列以"重量（2，0，-1）和一个红色操作" 开始，以重量（0，0，0） 和无播放结束，则该序列必须至少包含五个动作。要做到这一点，请假设我们有一个符合这个条件的序列，并且具有少于五个动作。然后：

1. 由于权重的第一个组件起初为正，并且没有红色操作会使其减少，因此序列将需要至少一个蓝色操作，这意味着它将必然至少一次包含红色 D（因为这是除非你从未开始就拥有一个蓝色操作��则的唯一方式）。
2. 由于序列至少包括红色 D，并且红色 D给我们两个蓝色操作，因此序列必然至少包括两次蓝色操作（因为游戏直到没有播放才结束）。
3. 由于序列至少包括红色 D，并且红色 D在重量的第二个分量上添加了2，因此它必然包含红

   move        weight         plays
   ------      ---------      -------
               (3,1,-1)       red x2
   red A       (3,-1,-2)      red
   red B       (4,-2,-3)      red
   red D       (4,0,-2)       blue x2
   blue A      (2,0,-1)       blue
   blue A      (0,0,0)        -
   

- ruakh

---

谢谢！现在唯一的问题是，当我把它重新插入到我正在处理的原始问题中时，这个答案不起作用。我得看看哪里出了问题，但这对我来说看起来像一个答案。再次感谢！ - Daniel

Answer 2

以下是每个起始位置的解决方案：

Start 1: (2, 0, -1)  Reds=1  Blues=0
Red B ==> (3, -1, -2)  Reds=1  Blues=0
Red B ==> (4, -2, -3)  Reds=1  Blues=0
Red D ==> (4, 0, -2)  Reds=0  Blues=2
Blue A ==> (2, 0, -1)  Reds=0  Blues=1
Blue A ==> (0, 0, 0)  Reds=0  Blues=0

Start 2: (3, 1, -1)  Reds=2  Blues=0
Red A ==> (3, -1, -2)  Reds=1  Blues=0
Red B ==> (4, -2, -3)  Reds=1  Blues=0
Red D ==> (4, 0, -2)  Reds=0  Blues=2
Blue A ==> (2, 0, -1)  Reds=0  Blues=1
Blue A ==> (0, 0, 0)  Reds=0  Blues=0

以下是一段使用C#编写的程序，进行随机游走，在执行了少量步骤后便放弃搜索。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SO8683939
{
  struct State
  {
    public int V1;
    public int V2;
    public int V3;
    public int Reds;
    public int Blues;
    public int Tokens { get { return Reds + Blues; } }
    public string Description;
    public State(int v1, int v2, int v3, int reds, int blues)
    {
      V1 = v1;
      V2 = v2;
      V3 = v3;
      Reds = reds;
      Blues = blues;
      Description = null;
    }
    public State Add(State other)
    {
      State sum;
      sum.V1 = V1 + other.V1;
      sum.V2 = V2 + other.V2;
      sum.V3 = V3 + other.V3;
      sum.Reds = Reds + other.Reds;
      sum.Blues = Blues + other.Blues;
      sum.Description = null;
      return sum;
    }
    public override string ToString()
    {
      var detail = string.Format("({0}, {1}, {2})  Reds={3}  Blues={4}", V1, V2, V3, Reds, Blues);
      if (Description != null)
      {
        return Description + ": " + detail;
      }
      return detail;
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      var start1 = new State(2, 0, -1, 1, 0) { Description = "Start 1" };
      var start2 = new State(3, 1, -1, 2, 0) { Description = "Start 2" };

      var end = new State(0, 0, 0, 0, 0);

      var redA = new State(0, -2, -1, -1, 0) { Description = "Red A" };
      var redB = new State(1, -1, -1, 0, 0) { Description = "Red B" }; ;
      var redC = new State(2, 0, -1, 1, 0) { Description = "Red C" }; ;
      var redD = new State(0, 2, 1, -1, 2) { Description = "Red D" }; ;
      var redOptions = new[] { redA, redB, redC, redD };

      var blueA = new State(-2, 0, 1, 0, -1) { Description = "Blue A" };
      var blueB = new State(-1, 1, 1, 0, 0) { Description = "Blue B" };
      var blueC = new State(0, 2, 1, 0, 1) { Description = "Blue C" };
      var blueD = new State(2, 0, -1, 2, -1) { Description = "Blue D" };
      var blueOptions = new[] { blueA, blueB, blueC, blueD };

      var startingPosition = start1;
      var maxSolutionLength = 5;

      var rand = new Random();
      var path = new List<State>();
      while (true)
      {
        var current = startingPosition;
        path.Clear();
        //Console.WriteLine("Starting");
        //Console.WriteLine(current);
        while (true)
        {
          State selected;
          if (current.Reds == 0)
          {
            selected = blueOptions[rand.Next(4)];
          }
          else if (current.Blues == 0)
          {
            selected = redOptions[rand.Next(4)];
          }
          else
          {
            if (rand.NextDouble() < 0.5)
            {
              selected = blueOptions[rand.Next(4)];
            }
            else
            {
              selected = redOptions[rand.Next(4)];
            }
          }
          //Console.WriteLine(selected);
          path.Add(selected);
          current = current.Add(selected);
          //Console.WriteLine(current);
          if (current.Equals(end))
          {
            Console.WriteLine("Success!");
            var retrace = startingPosition;
            Console.WriteLine(retrace);
            foreach (var selection in path)
            {
              retrace = retrace.Add(selection);
              Console.WriteLine("{0} ==> {1}", selection.Description, retrace);
            }
            Console.ReadLine();
            break;
          }
          else if (current.Tokens == 0)
          {
            // fail
            //Console.WriteLine("Fail");
            break;
          }
          else if (path.Count >= maxSolutionLength)
          {
            // fail
            //Console.WriteLine("Fail");
            break;
          }
        }
      }
    }
  }
}

- Fantius

Answer 3

考虑红色和蓝色棋子数量作为你位置的另外两个维度。这极大地降低了问题的复杂性。

下面，将问题重新陈述为最后两个维度表示剩余红色和蓝色棋子。

开始时有两种初始位置:

- 重量为 (2, 0,-1, 1, 0) - 重量为 (3,-1,-1, 2, 0) 当你拥有重量为 (0, 0, 0, 0, 0) 时结束游戏。

给定一个操作，你可以选择以下任意一种增加重量的八种棋子： Ar,Br,Cr,Dr,Ab,Bb,Cb,Db。规则如下：

- 棋子 Ar 增加重量 (0,-2,-1,-1, 0) - 棋子 Br 增加重量 (1,-1,-1, 0, 0) - 棋子 Cr 增加重量 (2, 0,-1, 1, 0) - 棋子 Dr 增加重量 (0, 2, 1,-1, 2) - 棋子 Ab 增加重量 (-2,0, 1, 0,-1) - 棋子 Bb 增加重量 (-1,1, 1, 0, 0) - 棋子 Cb 增加重量 (0, 2, 1, 0, 1) - 棋子 Db 增加重量 (2, 0,-1, 2,-1) 此外，最后两个维度不能为负数。

现在，可以将其解决为一个包含8个变量的方程式。

- Drew Dormann

---

这是一个很好的重新表述问题的方式，但它并没有让我更接近解决问题，不是吗？ - Daniel

在最坏的情况下，您可以将其表述为整数规划问题。解决IP是NP难的，但至少这意味着它不是不可判定的难题。 - templatetypedef

但是我怎么知道是否有解决方案呢？我已经寻找了一个星期了。有没有办法在找到答案之前就知道是否有答案？ - Daniel

一种方法是构建一个包含所有可能移动排列的树，并在检测到重复配置时进行修剪。这是一种蛮力方法，但它是可靠的。不过，在放弃这种方法之前，您必须决定要尝试多少层深度。 - nycdan

整洁，但稍微不完整：“最后两个可能永远不会为负”的限制不足以表达这样一个想法，即如果你的red变量大于0，你只能玩前四步。(即使Br和Cr具有净非负效应，如果你没有红色移动，你仍然不能播放它们。) - tzaman

@tzaman：你说得对。你看有没有简单的方法来解决这个问题？ - Drew Dormann