¿La guerra tiene una duración esperada infinita?

Question

Mi pregunta se refiere al juego de cartas (completamente determinista) conocido como Guerra , interpretado por niños de siete años en todas partes, como mi hijo Horacio, y a veces también por otros, como sus padres.

La pregunta es: ¿la duración prevista del juego es infinita?

Las reglas. (de http://en.wikipedia.org/wiki/War_(juego_cartas) ) El mazo se divide en partes iguales entre los dos jugadores, dando a cada uno una pila boca abajo. Al unísono, cada jugador revela la carta superior de su pila (una "batalla"), y el jugador con la carta más alta toma las dos cartas jugadas y las mueve al fondo de su pila. Si las dos cartas jugadas son de igual valor, cada jugador pone tres cartas boca abajo y una cuarta carta boca arriba (una "guerra"), y la carta de mayor valor gana todas las cartas de la mesa, que se añaden al fondo de su pila. En caso de otro empate, el proceso de guerra se repite hasta que no haya empate. Un jugador gana al recoger todas las cartas. Si un jugador se queda sin cartas mientras reparte las cartas boca abajo de una guerra, puede jugar la última carta de su mazo como su carta boca arriba y seguir teniendo una oportunidad de seguir en el juego.

Supongamos que las cartas se devuelven al mazo de una manera bien definida. Por ejemplo, en el orden en que se juegan las cartas, con las cartas del ganador de la ronda anterior en primer lugar (y un primer jugador seleccionado para la batalla inicial).

En la página de Wikipedia, se tabulan los resultados de 1 millón de partidas aleatorias simuladas, informando de una partida de duración media de 248 batallas. Pero esto no responde realmente a la pregunta, porque podría ser que hubiera una disposición inicial tortuosa de las cartas que llevara a una partida periódica que durara eternamente. Dado que sólo hay un número finito de barajados, este barajado tortuoso contribuirá infinitamente a la Valor esperado . Por lo tanto, la pregunta realmente equivale a:

Pregunta. ¿Existe un barajado tortuoso en la Guerra, que lleva a un juego infinitamente largo?

Por supuesto, el juego descrito anteriormente no es más que un caso especial del juego más general que podría llamarse Guerra universal El juego se juega con N jugadores utilizando una baraja de cartas que representan elementos de un preorden parcial finito. Cualquier carta estrictamente dominante gana la baza; en caso contrario, hay guerra entre los jugadores cuyas cartas no estaban estrictamente dominadas. ¿Tiene alguna instancia de la Guerra Universal una duración esperada infinita?

Answer 1

En realidad, acabamos de demostrar que "se puede alcanzar el estado final desde cualquier estado". La prueba es de estilo Euler, es decir, no es una prueba constructiva. Así que no sabemos nada sobre la longitud del juego. Sabemos que es finito suponiendo que los jugadores utilizan regularmente las dos formas posibles de devolver cartas a su mano.

Otra cuestión es si existe una estrategia.

Evgeny Lakshtanov

Answer 2

Siempre he jugado a la guerra donde las cartas capturadas van a un montón que se barajan antes de volver a jugar. En este caso, una partida de guerra rara vez será eterna.

Un fallo en las reglas es este, y acabo de jugarlo con mi hija. Me quedaban 6 cartas, la siguiente jugada eran 2 reyes (realmente no importa) así que pusimos nuestras cartas y ambos subimos 3 otra guerra. Ahora me queda 1 carta, así que le doy la vuelta a un 8 y mi hija juega otro 3 y le da la vuelta a un 8. ¡Así que ahora no me quedan cartas y las últimas cartas se jugaron con 3 guerras seguidas! ?? ¿Cuál es la probabilidad de que eso ocurra? Debería salir y comprar un billete de lotería...

De todas formas creo que las reglas dirían que el jugador con cartas continuara jugando otros 3 y se diera la vuelta para intentar ganar al 8 pero no estoy seguro, no hay reglas para eso así que... qué se supone que pasa. Mientras tanto el juego está en un punto de estancamiento.

Sin embargo, las estadísticas del juego son interesantes. Aunque la mayoría de las veces es al azar, las estadísticas son sólo de interés.

Answer 3

En mi clase de programación estábamos haciendo el juego de la guerra y me topé con un juego que duró una eternidad, pero siguió las reglas de mi código, que no estaba configurado como siempre jugué el juego. Originalmente jugaba: el ganador agarra las dos cartas y las pone en una "pila muerta" separada para usarla cuando se agote la "pila activa", barajando adecuadamente las cartas antes de usarlas. Mi código siempre cogía la carta del jugador 1 y luego la del jugador 2 y las colocaba en el fondo del mazo del jugador ganador. Esto llevó a un juego que, cuando se ejecutaba, tenía una guerra que organizaba el mazo de tal manera que nunca tenía otra guerra y continuamente cambiaba las cartas entre los jugadores que iban en un gran bucle... Era interesante.

Answer 4

Hace muchos años, Amir Dembo y yo analizamos la duración prevista de una variante sencilla del juego de la guerra. Se tiene $n$ tarjetas etiquetadas como ' $1$ ', , ' $n$ ', y los divides al azar. En cada ronda gana la carta más alta. En esta versión hay "batallas" pero no "guerras" y la identidad del ganador se determina de antemano ya que el jugador que tiene ' $n$ '. Pudimos estimar la duración esperada de este juego como propocional a $n^2\log n$ pero no la constante precisa. (Tenga en cuenta que todavía hay algunas variantes posibles con respecto a lo que debe hacer cuando se queda sin su paquete).

Answer 5

[No puedo comentar (no tengo reputación) así que añado esto como respuesta].

Se me ocurrió escribir un programa de Guerra por mi cuenta, para practicar mi (principiante) Python. Siempre había estado añadiendo las cartas al fondo de la pila del ganador de la misma manera, y frecuentemente tenía partidas en las que, después de varias guerras (probablemente entre 5 y 20) no había más guerras y el juego nunca terminaba (lo corté a los 10.000 turnos, y más tarde a los 100.000 turnos). Basándome en lo anterior, empecé a barajar las cartas "ganadas" y dejé de ver estas partidas "en bucle". Sin embargo, también había corregido otros errores. Así que, ahora mismo, como experimento, he eliminado el barajado de las cartas "ganadas". De nuevo, veo con frecuencia partidas que no terminan después de 100.000 turnos. Por cierto, barajo el mazo cinco veces (y con la semilla basada en el tiempo del sistema). Así que, por lo que sé, el orden inicial debería ser diferente cada vez.

Tengo curiosidad. Acabo de tener 28 partidas, de un total de treinta, que han llegado a los 100.000 turnos. Evidentemente es posible que aún tenga algún fallo en el barajado, o en el juego. ¿Alguna conjetura sobre si colocar las cartas ganadas en la parte inferior de la pila de ganadores, siempre en el mismo orden, podría realmente conducir a este número de juegos en bucle?

Me parece bien dar mi código, si alguien está interesado. O los montones iniciales, después de barajar.

gracias. Paul