Una versión simplificada del juego de cartas Winner

He preguntado este problema en MathOverflow , sin ninguna respuesta satisfactoria.

Considere el siguiente juego de dos jugadores, que es una simplificación del juego de cartas llamado Winner . (La siguiente formulación fue tomada de un comentario de Guillaume Brunerie sobre MathOverflow).

Hay dos jugadores A y B. Cada jugador tiene un conjunto de cartas (un subconjunto de ), visibles desde ambos jugadores. El objetivo del juego es deshacerse de sus propias cartas. El primer jugador juega cualquier carta en la mesa, luego el otro jugador debe jugar una carta (estrictamente) más grande, y así hasta que uno de los jugadores no pueda jugar o decida pasar. Luego, las cartas sobre la mesa se descartan, y el otro jugador comienza nuevamente jugando cualquier carta (que será seguida por una carta más grande). Y así sucesivamente hasta que uno de los dos jugadores se quede sin cartas y gane el juego.$\{1,\dots,n\}$

Quiero saber la mejor estrategia para los jugadores (si puede ganar).

Definicion formal

Denote con la configuración del juego donde el conjunto de las cartas del primer jugador es , el conjunto de las cartas del segundo jugador es y la carta más grande en la mesa es , donde significa que no hay cartas sobre la mesa. Me gustaría un algoritmo para calcular, dado , si el primer jugador tiene una estrategia ganadora en la configuración .A B i i = 0 i , A , B w ( i , A , B $w(i,A,B)$$A$$B$$i$$i=0$$i,A,B$$w(i,A,B)$

Formalmente, me gustaría un algoritmo para calcular la función definida de la siguiente manera:$f$

Deje que , .B o o l = { F a l s e , T r u e$\mathbb{Z}_n = \left\{1, 2, \cdots, n\right\}$$\mathrm{Bool} = \left\{\mathrm{False}, \mathrm{True}\right\}$

Función$f:\;\left\{ 0, 1, \cdots, n \right\} \times 2^{\mathbb{Z}_n} \times 2^{\mathbb{Z}_n} \to \mathrm{Bool}$

donde

Estrategias equivocadas

Aquí hay algunas estrategias equivocadas:

1. Siempre juega la carta más pequeña. Sea , la estrategia ganadora para el jugador A en la configuración es jugar la carta . Si el jugador A juega la carta 1, perderá.w ( 0 , A , B ) $n = 3, A = \{1,3\}, B = \{2\}$$w(0, A, B)$$3$
2. Juega la carta más pequeña a menos que el otro jugador tenga solo una carta. Es una estrategia más fuerte que la estrategia 1, pero también está mal. Solo piense en la configuración . Si el jugador A usa la estrategia 2, perderá: , por lo que el jugador A pierde.1 → 2 → 4 → 5 → 6 → 8 → pasar → $w(0, \{1, 4, 6, 7\}, \{2, 3, 5, 8\})$$1\rightarrow2\rightarrow4\rightarrow5\rightarrow6\rightarrow8\rightarrow\textrm{pass}\rightarrow3$

Esto probablemente debería ser un comentario, pero es demasiado largo.

$n$$2n$$1$ $\ldots$ $2n$

Probaron una serie de datos interesantes sobre la estrategia óptima, pero no pudieron encontrar un algoritmo eficiente para un juego óptimo, y tampoco pudieron demostrar que era NP-difícil.

Para el juego misère , donde cada persona trata de hacer la menor cantidad de trucos, fueron capaces de dar la estrategia óptima.

En su mayor parte, estos resultados se obtuvieron primero mirando los resultados de un programa de computadora que encontró la estrategia óptima para pequeñas instancias, luego buscando patrones para obtener conjeturas y finalmente probando estas conjeturas. Sospecho que este también sería un enfoque fructífero para el juego del OP.