Найти алгоритм для баланса этой игры

Ответ 1

Наверное, мне что-то не хватает, но, просто осмотрев, похоже, эта последовательность шагов должна работать?

• начните с "weight (2,0,-1) и один red play"
• возьмите red play, шт C, который добавляет вес (2,0,-1) и два red играет ", оставив вас с весом (4,0,-2) и двумя играми red.
• возьмите red play, шт A, который добавляет вес (0,-2,-1) ", оставив вас с весом (4,-2,-3) и одним red.
• возьмите red play, шт D, который добавляет вес (0,2,1) и два blue играет ", оставив вас с весом (4,0,-2) и двумя играми blue.
• возьмите blue play, шт A, который добавляет вес (-2,0,1) ", оставив вас с весом (2,0,-1) и одним blue воспроизведением.
• возьмите blue play, шт 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)        -

., нет?

Отредактировано для добавления:

Как я нашел это:

Поскольку этот вопрос вызвал большой интерес, возможно, мне следует объяснить, как я нашел вышеупомянутое решение. Это была в основном удача; Я столкнулся с двумя ключевыми наблюдениями:

• red A и red D отменяют друг друга по весу (первый добавляет (0,-2,-1), последний добавляет (0,2,1)) и добавляет в общей сложности две игры blue (как из red D), и нет red; поэтому, если вы играете один за другим, вы "конвертируете" две игры red в две игры blue.
• blue A отменяет начальный вес (он добавляет (2,0,-1)) и не добавляет ни одной пьесы, поэтому вся проблема может быть решена путем "преобразования" одного red воспроизведения в одно воспроизведение blue.

Это дало мне хорошее начало. Я начал с red C, чтобы получить две игры red, которые я мог бы "преобразовать" в две игры blue, и я сразу увидел, что red C также был "противоположным" blue A по весу, поэтому также можно было бы отменить с помощью blue A. В моей голове все это, казалось, полностью прекратилось; затем я записал его, чтобы убедиться.

Доказательство минимальности:

Кроме того, хотя в то время я не потрудился рассуждать, я также могу доказать, что это "минимальная" победная последовательность для этой начальной позиции — под которым я подразумеваю, что если последовательность начинается с "веса (2,0,-1) и одного red воспроизведения" и заканчивается весом (0,0,0) и не играет, то последовательность должна содержать не менее пяти ходов. Для этого предположим, что у нас есть последовательность, которая соответствует этому условию и имеет менее пяти ходов. Тогда:

• Так как первый компонент веса начинается положительным, а воспроизведение no red уменьшает его, для последовательности потребуется хотя бы одно воспроизведение blue, что означает, что оно обязательно будет включать red D не реже одного раза (поскольку что единственный способ получить игру blue, если вы не начинаете с одного).
• Поскольку последовательность включает red D хотя бы один раз, а red D дает нам две игры blue, последовательность обязательно будет включать blue не реже двух раз (так как игра не заканчивается до тех пор, пока никакие пьесы не останутся).
• Поскольку последовательность включает red D не реже одного раза, а red D добавляет 2 ко второму компоненту веса, он обязательно будет либо содержать red A по крайней мере один раз, либо содержать red B по крайней мере дважды ( так как нет другого способа уменьшить второй компонент веса по крайней мере на 2). Но ясно, что если он содержит red D хотя бы один раз, blue по крайней мере дважды, а red B по крайней мере дважды, то он будет содержать не менее пяти ходов, что запрещено по предположению; поэтому он должен использовать подход red A.
• Итак, последовательность содержит red D по крайней мере один раз, blue не менее двух раз и red A по крайней мере один раз. И по предположению он содержит менее пяти ходов. Таким образом, он должен состоять только из одного red D, двух blue s, одного red A и ноль других ходов.
• Исходное положение дает нам только один ход red, и последовательность включает ровно две игры red. Поэтому последовательность должна содержать шаг, который дает ровно один ход red. Но единственный возможный ход, который может сделать это, - red B, который не содержит последовательности.

Следовательно, такая последовательность невозможна.

Другая стартовая позиция:

Я также могу доказать, используя аналогичные аргументы, что любое решение, начинающееся с опции "weight (3,1,-1) и two red play", также должно содержать не менее пяти ходов. Одним из таких решений с пятью перемещениями является:

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)        -

Ответ 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

Найдено мгновенно следующей программой на С#, которая выполняет случайное блуждание и отказывается после небольшого количества ходов.

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;
          }
        }
      }
    }
  }
}

Ответ 3

Учитывайте, что количество красных и синих пьес должно быть двумя дополнительными измерениями в вашей позиции. Это значительно снижает сложность проблемы.

Ниже, проблема пересчитывается с последними двумя измерениями, представляющими оставшиеся красные и синие.

СТАРТ. Вы начинаете с одной из двух позиций:

• вес (2, 0,-1, 1, 0)
• вес (3,-1,-1, 2, 0)

END Игра заканчивается, когда у вас есть вес (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 переменными.