Pregunta:
Pregunté 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 juego de cartas (un subconjunto de $ \ {1, \ dots, n \} $), visible para ambos jugadores. El objetivo del juego es deshacerse de sus propias cartas. El primer jugador juega cualquier carta de la mesa, luego el otro jugador debe jugar una carta (estrictamente) más grande, y así sucesivamente 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 de nuevo 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.
Quiero saber cuál es la mejor estrategia para los jugadores (si puede ganar).
Definicion formal
Denote por $ w (i, A, B) $ la configuración del juego donde el juego de cartas del primer jugador es $ A $, el juego de cartas del segundo jugador es $ B $ y la carta más grande de la mesa es $ i $, donde $ i = 0 $ significa que no hay ninguna carta sobre la mesa. Me gustaría un algoritmo para calcular, dado $ i, A, B $, si el primer jugador tiene una estrategia ganadora en la configuración $ w (i, A, B) $.
Formalmente, me gustaría un algoritmo para calcular la función $ f $ definida de la siguiente manera:
Sea $ \ mathbb {Z} _n = \ left \ {1, 2, \ cdots, n \ right \} $, $ \ mathrm {Bool} = \ left \ {\ mathrm {False}, \ mathrm {True} \ derecha \} $.
Función $ f: \; \ left \ {0, 1, \ cdots, n \ right \} \ times 2 ^ {\ mathbb {Z} _n} \ times 2 ^ {\ mathbb {Z} _n} \ to \ mathrm {Bool} $
donde $$ f (i, A, B) = \ begin {cases} \ mathrm {False} & B = \ emptyset \\ \ mathrm {True} & B \ ne \ emptyset \ land \ exist j \ in A: j > i, f (j, B, A – \ left \ {j \ right \}) = \ mathrm {False} \\ \ mathrm {True} & B \ ne \ emptyset \ land f (0, B, A) = \ mathrm {False} \\ \ mathrm {False} & \ textrm {de lo contrario} \ end {cases} $$
Estrategias equivocadas
Aquí hay algunas estrategias incorrectas:
- Juega siempre la carta más pequeña. Sea $ n = 3, A = \ {1,3 \}, B = \ {2 \} $, la estrategia ganadora para el jugador A en la configuración $ w (0, A, B) $ es jugar la carta $ 3 $. Si el jugador A juega la carta 1, perderá.
- 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 es incorrecta. Solo piensa en la configuración $ w (0, \ {1, 4, 6, 7 \}, \ {2, 3, 5, 8 \}) $. Si el jugador A usa la estrategia 2, perderá: $ 1 \ rightarrow2 \ rightarrow4 \ rightarrow5 \ rightarrow6 \ rightarrow8 \ rightarrow \ textrm {pass} \ rightarrow3 $, por lo que el jugador A pierde.
Respuesta:
Probablemente debería ser un comentario, pero es demasiado largo.
Un juego relacionado fue estudiado por Jeff Kahn, Jeff Lagarias y Hans Witsenhausen, en la serie de artículos Juego de cartas de un solo palo para dos personas I, II, III y En el juego de cartas de Laskar. En el juego que estudiaron, cada jugador tiene $ n $ cartas, repartidas desde $ 2n $ cartas numeradas $ 1 $ $ \ ldots $ $ 2n $. Cada truco consta de dos cartas, la carta más alta gana el truco y el ganador lidera. El objetivo es hacer la mayor cantidad de trucos.
Demostraron una serie de hechos interesantes sobre la estrategia óptima, pero no pudieron encontrar un algoritmo eficiente para un juego óptimo, y tampoco pudieron probar que era NP-difícil.
Para el juego de misère , donde cada persona intenta realizar la menor cantidad de trucos, pudo 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 instancias pequeñas, 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.