Analizando una versión modificada del juego de cartas "Guerra"

Un juego simple que generalmente juegan los niños, el juego de Guerra lo juegan dos personas usando una baraja estándar de 52 cartas. Inicialmente, el mazo se baraja y todas las cartas se reparten entre los dos jugadores, de modo que cada uno tiene 26 cartas al azar en un orden aleatorio. Asumiremos que los jugadores pueden examinar (pero no cambiar) ambos mazos, para que cada jugador conozca las cartas y el orden de las cartas en ambos mazos. Esto normalmente se hace en la práctica, pero no cambiaría nada sobre cómo se juega el juego, y ayuda a mantener esta versión de la pregunta completamente determinista.

Luego, los jugadores revelan las mejores cartas de sus respectivos mazos. El jugador que revela la carta más grande (según el orden habitual: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Reina, Rey, As) gana la ronda, colocando primero su carta (el carta alta) en la parte inferior de su mazo, y luego la carta de su oponente (la carta baja) en la parte inferior de la baraja (normalmente, el orden de esto no se aplica, pero para mantener la primera versión de esta pregunta determinista, como se aplicará un pedido).

En caso de empate, cada jugador revela cuatro cartas adicionales desde la parte superior de sus mazos. Si la cuarta carta mostrada por un jugador es más alta que la cuarta carta mostrada por otro jugador, el jugador con la cuarta carta más alta gana todas las cartas jugadas durante el desempate, en cuyo caso las cartas del ganador se colocan primero en la parte inferior del mazo del ganador (en orden de entrada, primero en salir; en otras palabras, las cartas más antiguas se colocan primero en la parte inferior), seguidas de las cartas del perdedor (en el mismo orden).

En caso de empates posteriores, el proceso se repite hasta que se determine un ganador del empate. Si un jugador se queda sin cartas y no puede continuar rompiendo el empate, el jugador que todavía tiene cartas se declara ganador. Si ambos jugadores se quedan sin cartas para jugar al mismo tiempo, el juego se declara empatado.

Las rondas se juegan hasta que un jugador se queda sin cartas (es decir, no tiene más cartas en su mazo), momento en el cual el jugador que todavía tiene cartas se declara ganador.

Como el juego se ha descrito hasta ahora, ni la habilidad ni la suerte están involucradas en la determinación del resultado. Dado que hay un número finito de permutaciones de 52 cartas, hay un número finito de formas en las que los mazos se pueden repartir inicialmente, y se deduce que (dado que la única información de estado en el juego es el estado actual de los mazos de ambos jugadores ) el resultado de la configuración de cada juego se puede decidir a priori. Ciertamente, es posiblemente ganar el juego de Guerra, y de la misma manera, perderlo. También dejamos abierta la posibilidad de que un juego de guerra pueda resultar en un empate o en un bucle infinito; para la versión completamente determinista descrita anteriormente, tal puede o no ser el caso.

Varias variaciones del juego que intentan hacerlo más interesante (y no, no todas implican convertirlo en un juego de beber). Una forma en la que he pensado para hacer que el juego sea más interesante es permitir que los jugadores declaren "triunfos" automáticos en ciertas rondas. En cada ronda, cualquiera de los jugadores (o ambos jugadores) puede declarar "triunfo". Si un jugador declara "triunfo", ese jugador gana la ronda independientemente de las cartas que se juegan. Si ambos jugadores declaran "triunfo", la ronda se trata como un empate y el juego continúa en consecuencia.

Uno puede imaginar una variedad de reglas que limitan la capacidad de los jugadores para triunfar (el triunfo ilimitado siempre resultaría en un juego de empate, ya que los jugadores triunfarían en cada turno). Propongo dos versiones (justo fuera de mi cabeza; probablemente sean posibles versiones más interesantes a lo largo de estas líneas) de Guerra basada en esta idea pero usando diferentes mecanismos de limitación de triunfo:

1. Frequency-War: los jugadores solo pueden triunfar si no han triunfado en las rondas anteriores .$k$
2. Guerra de venganza: los jugadores solo pueden triunfar si no han ganado una ronda en las rondas anteriores .$k$

Ahora para las preguntas, que se aplican a cada una de las versiones descritas anteriormente:

1. ¿Existe una estrategia tal que, para algún conjunto de posibles configuraciones iniciales del juego, el jugador que lo usa siempre gane (estrategia fuertemente ganadora)? Si es así, ¿cuál es esta estrategia? ¿Si no, porque no?
2. ¿Existe una estrategia tal que, para algún conjunto de posibles configuraciones iniciales del juego, el jugador que la usa siempre pueda ganar o forzar un empate (estrategia ganadora)? Si es así, ¿cuál es esta estrategia? ¿Si no, porque no?
3. ¿Son sus configuraciones iniciales del juego tales que no hay una estrategia ganadora (es decir, un jugador que usa una estrategia fija siempre puede ser derrotado por un jugador que usa la estrategia fija )? Si es así, ¿cuáles son y explican?$S$$S'$

Para ser claros, estoy pensando en una "estrategia" como un algoritmo fijo que determina en qué rondas debe triunfar el jugador que usa la estrategia. Por ejemplo, el algoritmo "triunfa siempre que puedas" es una estrategia y un algoritmo (un algoritmo heurístico). Otra forma de lo que pregunto es esto:

¿Hay alguna heurística buena (o demostrablemente óptima) para jugar estos juegos?

Se agradecen las referencias a los análisis de dichos juegos (no conozco ningún análisis de esta versión de War o de juegos esencialmente equivalentes). Los resultados para cualquier son interesantes y apreciados (tenga en cuenta que, en ambos casos, conduce a un triunfo ilimitado, que ya he discutido).$k$$k=0$

Si entiendo correctamente, toda la información sobre el juego está disponible para ambos jugadores. Es decir, la configuración inicial y todos los movimientos posibles son conocidos por ambos jugadores (principalmente porque ambos jugadores pueden mirar las cartas del otro jugador). Esto hace que el juego sea un juego de suma cero de información perfecta. Por lo tanto, existe una estrategia perfecta disponible para ambos jugadores que lograría el mejor resultado en cada juego para ese jugador. Esto fue probado en 1912 por el matemático alemán Ernst Zermelo.

No sé cuál es la estrategia, pero uno podría imaginar construir un gran árbol de juegos para él y hacer que una computadora encuentre la estrategia para mí usando el algoritmo min-max .

El árbol para cada juego tendría como raíz las manos de los dos jugadores. Las ramas en el árbol corresponden a los movimientos de los jugadores. En el caso más simple, estos consisten en simplemente colocar las cartas requeridas. En los casos más avanzados, se puede hacer el movimiento de "triunfo". Los nodos internos del árbol registran cuál es la configuración actual de las tarjetas junto con cualquier información sobre el estado 'triunfos' del wrt. Las hojas del árbol corresponden a las posiciones finales del juego, que se etiquetarán con, por ejemplo, +1 para una victoria para el Jugador 1, 0 para un empate y -1 para una victoria para el Jugador 2. Ignore los juegos en bucle por ahora.

Ahora el algoritmo min-max funcionará de la siguiente manera (desde la perspectiva del Jugador 1). Suponga que mira un nodo donde el jugador 1 hace un movimiento y que los nodos a continuación están anotados con un +1, 0 o -1 (la recompensa) junto con las elecciones que el jugador debe hacer para obtener el resultado dado. El jugador 1 simplemente selecciona el nodo con el mayor pago, registra ese pago y la elección requerida para obtenerlo. Para el nodo donde el jugador 2 está haciendo el movimiento, se elige el nodo con el pago mínimo y se registra la elección. Esto refleja que el jugador 2 está apuntando al puntaje más bajo para ganar. Esto se propaga a la del árbol. Las elecciones registradas en cada nodo corresponden a la mejor estrategia que puede hacer un jugador. La recompensa final determina quién gana. En última instancia, esta es una función en términos de rentabilidad, aunque la elección exacta de los movimientos puede variar.

Se pueden incorporar configuraciones de bucle potencial en el árbol del juego simplemente agregando bucles que vuelven a una configuración ya vista (cuando se computa desde la parte superior). Para tales nodos, usted toma el punto fijo más grande si es un nodo donde juega el Jugador 1 y el punto menos fijo cuando juega el Jugador 2.

Tenga en cuenta que si no hubiera asumido que ambos jugadores podrían examinar ambos mazos, entonces este enfoque no se aplicaría. El juego implicaría una oportunidad y la estrategia seleccionada sería específica del juego.

Que exista o no una estrategia ganadora fuerte o débil para uno de los jugadores depende del resultado del algoritmo min-max aplicado a todos los árboles. Pero seguro que hay muchos de ellos ... Calcular el árbol para uno es probablemente bastante fácil, ya que no hay muchas elecciones hechas a través del juego.