Encontrar un algoritmo para equilibrar este juego

Question

He tratado de extraer solo la parte del problema donde estoy teniendo problemas, esto es parte de un proyecto más grande que estoy haciendo (no deberes). Creo que es más fácil describirlo como un juego (ya que lo necesito para terminar un juego en el que estoy trabajando). Este es un juego para un jugador, tal como lo describo.

START Se empieza con una de dos posiciones:

• peso (2,0,-1) y uno red juego
• peso (3,1,-1) y dos red juega

FIN El juego termina cuando no tener más juegos. El objetivo es terminar el juego con peso (0,0,0).

Hay dos tipos de juegos red y blue. Dado un juego, eliges una de las cuatro piezas: A,B,C,D que te dan peso adicional y posiblemente jugadas adicionales. Estas son las reglas:

• En un red juego:

  • Un añade peso (0,-2,-1)
  • B añade peso (1,-1,-1) y añade un red juego
  • C añade peso (2,0,-1) y dos red obras
  • D agrega peso (0,2,1) y dos blue jugar s

Las reglas para blue jugadas son similares, pero las dos primeras columnas de pesos se intercambian y la última columna es inversa y los tipos de obras se invierten, por lo que se obtiene de esta forma:

• En un blue juego:

  • un añade peso (-2,0,1)
  • B añade peso (-1,1,1) y añade un blue juego
  • C añade peso (0,2,1) y dos blue jugadas
  • D añade peso (2,0,-1) y dos red jugadas

PREGUNTA ¿Puede este juego puede ganar ?

Estoy tratando de escribir un programa que gane el juego eligiendo jugadas para que el saldo final sea (0,0,0) cuando no tenga más jugadas. Solo que no puedo hacerlo. Entonces ahora creo que tal vez no hay algoritmo para ganar el juego. Realmente me gustaría saber por qué es eso.Si alguien tiene alguna idea de cómo puedo probar eso, ¡por favor, hágamelo saber! O, si lo intentas y encuentras una manera de ganar, entonces dímelo también. ¡¡Gracias!!

Answer 1

Probablemente me esté faltando algo, pero solo por inspección, parece que esta secuencia de pasos debería funcionar? :

• comienzo con "peso (2,0,-1) y uno red obra"
• tomar un juego red, pieza C, que "añade peso (2,0,-1) y dos red obras", dejándole con peso (4,0,-2) y dos red jugadas.
• juego red, pieza A, que "agrega peso (0,-2,-1)", dejándolo con peso (4,-2,-3) y red juego.
• echar un red juego, pieza D, que "añade peso (0,2,1)blue y dos jugadas", dejándole con peso (4,0,-2) y dos blue jugadas.
• juego blue, pieza A, que "agrega peso (-2,0,1)", dejándolo con peso (2,0,-1) y blue juego.
• echar un juego blue, pieza A, que "añade peso (-2,0,1)", dejándole con peso (0,0,0) y no se reproduce.

Un poco más esquemáticamente:

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

. . . ¿no?

---

Editado para añadir:

cómo encontré esto:

Dado que esta cuestión se ha ganado mucho interés, tal vez debería explicar cómo encontré la solución anterior. Fue básicamente suerte; Me encontré con dos observaciones clave:

• red A y red D se anulan entre sí peso-Wise (la antigua añade (0,-2,-1), este último añade (0,2,1)), y añadir un total de dos blue obras de teatro (ambos de red D) y sin red juega; así que si juegas uno tras otro, "conviertes" dos jugadas red en dos jugadas blue.
• blue A cancela el peso inicial (agrega (2,0,-1)) y no agrega reproducciones, por lo que todo el problema se puede resolver "reproduciendo" un juego red en un juego blue.

Eso me dio un buen comienzo. Empecé con red C para obtener las dos jugadas red que podía "convertir" a dos jugadas blue, e inmediatamente vi que red C era también el "opuesto" de blue A en peso, por lo que también podría cancelarse con blue A. En mi cabeza, todo parecía cancelarse perfectamente; luego lo escribí para asegurarme.

prueba de que es mínimo:

Asimismo, si bien no me molesté a la razón a través de él en el momento, que puede también demostrar que se trata de una secuencia ganadora "mínimo" para esa posición de partida — por lo que quiero decir es que si una secuencia comienza con "peso (2,0,-1) y uno red juega" y finaliza con peso (0,0,0) y no se reproduce, entonces la secuencia debe contener al menos cinco movimientos. Para hacerlo, supongamos que tenemos una secuencia que cumple esta condición y tiene menos que cinco movimientos. Entonces:

1. Desde el primer componente del peso comienza positivo, y no red juego disminuye, la secuencia se requieren por lo menos un blue juego, lo que significa que incluirá necesariamente red D al menos una vez (ya que es la única forma de adquirir un juego blue si no comienzas con uno).
2. Dado que la secuencia incluye red D al menos una vez, y red D nos da dos blue jugadas, la secuencia necesariamente incluirá blue al menos dos veces (ya que el juego no termina hasta que no quedan jugadas).
3. Puesto que la secuencia incluye red D al menos una vez, y red D añade 2 al segundo componente del peso, será necesariamente ya sea contener red A al menos una vez, o bien contener red B al menos dos veces (ya que no hay otra forma de disminuir el segundo componente del peso por al menos 2). Pero claramente, si contiene red D al menos una vez, blue al menos dos veces, y red B al menos dos veces, entonces contendrá al menos cinco movimientos, lo cual está prohibido por suposición; por lo tanto, debe usar el enfoque red A.
4. Por lo tanto, la secuencia contiene red D al menos una vez, blue al menos dos veces y red A al menos una vez. Y por suposición, contiene menos de cinco movimientos. Por lo tanto, debe constar de exactamente uno red D, dos blue s, uno red A, y cero otros movimientos.
5. La posición inicial nos da solo un juego red, y la secuencia incluye exactamente dos juegos red. Por lo tanto, la secuencia debe contener un movimiento que produzca exactamente un juego red. Pero el único movimiento posible que podría hacer eso es red B, que la secuencia no contiene.

Por lo tanto, tal secuencia no es posible.

la otra posición de inicio:

también puedo demostrar, usando tipos similares de argumentos, que cualquier solución comenzando con el "peso (3,1,-1) y dos jugadas red" opción debe también contener al menos cinco movimientos. Una de tales soluciones de cinco movimiento es:

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

Answer 2

Tenga en cuenta que la cantidad de juegos en rojo y azul son dos dimensiones adicionales a su posición. Esto reduce en gran medida la complejidad del problema.

A continuación, el problema se actualiza con las dos últimas dimensiones que representan las reproducciones en rojo y azul restantes.

START Se empieza con una de dos posiciones:

• peso (2, 0,-1, 1, 0)
• peso (3,-1,-1, 2, 0)

FIN El juego termina cuando se tiene el peso (0, 0, 0, 0, 0).

Dado un juego, eliges una de las ocho piezas: Ar,Br,Cr,Dr,Ab,Bb,Cb,Db que te dan peso adicional. Estas son las reglas:

• Ar añade peso (0,-2,-1,-1, 0)
• Br añade peso (1,-1,-1, 0, 0)
• Cr añade peso (2, 0,-1, 1, 0)
• Dr añade peso (0, 2, 1,-1, 2)
• Ab añade peso (-2,0, 1, 0,-1)
• Bb añade peso (-1,1, 1, 0, 0)
• Cb agrega peso (0, 2, 1, 0, 1)
• Db añade peso (2, 0,-1, 2,-1)

Por otra parte, las dos últimas dimensiones no pueden ser negativos.

Ahora, se puede resolver como una ecuación de 8 variables.

Answer 3

Éstos son soluciones para cada posición de partida:

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 

Encontrado instantáneamente por el siguiente programa # C que hace un paseo aleatorio y da después de un pequeño número de movimientos.

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