Algoritmo sobre la estrategia ganadora de Winner (Juego de cartas simplificado)

Question

Aquí tienes una introducción al juego ordinario Winner:

http://en.wikipedia.org/wiki/Winner_(card_game)

Estoy pensando en una simplificación del juego.

** He copiado este problema a cstheory **

Es un juego para dos jugadores.

Usamos $w(i, A, B)$ para describir una situación ($i \in \mathbb{Z}, i \ge 0$, $A, B \subseteq\left\{1, 2, \cdots, n\right\}$)

Cada vez, uno de los dos jugadores recibirá una situación $w(i, A, B)$. (Posdata: el jugador conoce $B$)

Si $B = \emptyset$, el jugador pierde.

De lo contrario, el jugador tiene dos opciones.

Puede jugar $w(0, B, A)$, lo que significa pasar, o $w(j, B, A - \{j\})$, donde $j \in A, j > i$, al otro jugador.

El juego comienza con el primer jugador recibiendo $w(0, A_0, B_0)$.

Quiero saber la mejor estrategia para los jugadores (si es que pueden ganar).

Posdata:

1. Podemos describirlo de manera más formal.

   Sea $\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 $$ f ( i, A, B ) = \left\{ \begin{array}{ll} \mathrm{False} & B = \emptyset \\\\ \mathrm{True} & \exists j \in A: j > i, f(j, B, A - \left\{j\right\}) = \mathrm{False} \\\\ \mathrm{True} & f(0, B, A) = \mathrm{False} \\\\ \mathrm{False} & \textrm{otherwise} \end{array} \right. $$ Intenta encontrar un algoritmo para calcular $f$.

2. Ordenando $\mathrm{Bool}$ con $\mathrm{False} < \mathrm{True}$, podemos afirmar que $w(i, A, B)$ es mejor que $w(i', A', B')$ si y solo si $f(i, A, B) \ge f(i', A', B')$

3. Aquí hay algunas estrategias incorrectas:

   1. Lanzar cada vez la carta más pequeña. Sea $n = 3, A = \left\{1,3\right\}, B = \left\{2\right\}$, la estrategia ganadora para $w(0, A, B)$ es lanzar $w(3, B, A - \left\{3\right\})$ al otro jugador. Si lanza $w(1, B, A - \left\{1\right\})$, perderá.
   2. Lanzar cada vez la carta más pequeña excepto cuando el otro jugador solo tiene una carta. Es una estrategia más fuerte que la 1, pero también es incorrecta. Solo piensa en $w(0, \left\{1, 4, 6, 7\right\}, \left\{2, 3, 5, 8\right\})$. Te darás cuenta de que si sigues la estrategia 2, perderás, y hay una estrategia ganadora cuando lanzas la carta $7$ primero.

Answer 1

¿Qué quieres decir con la mejor estrategia? Dado que los jugadores no conocen la mano del otro jugador, es imposible saber cuál será una estrategia ganadora.

Por ejemplo, supongamos que soy el primer jugador y que mi mano es {1, 4}.
Si la mano del otro jugador es {4}, gano si juego 4 y pierdo si juego 1.
Pero si la mano del otro jugador es {2, 3, 5}, pierdo si juego 4 y gano si juego 1.

Entonces, si mi mano es {1, 4}, no hay una estrategia ganadora, depende de la mano del otro jugador.

(si entendí correctamente las reglas)

Editar: Si consideras que ambos jugadores conocen ambas manos, entonces el juego es finito con información perfecta, por lo que puedes dibujar el gráfico de todas las posibles resultados y determinar recursivamente las posiciones ganadoras y perdedoras (como con todos los juegos finitos con información perfecta).

Pero quizás haya una estrategia ganadora más fácil de calcular, no lo sé, intentaré ver si la hay.