¿Hay un juego simple con complejidad asimétrica?

Considere la información completa de los juegos combinatorios de dos jugadores que terminan después de un número polinómico de movimientos, y de manera alterna, los jugadores eligen entre un número finito de movimientos permitidos. La pregunta habitual es cuán difícil es distinguir desde una posición determinada al ganador. Otra sería, lo difícil que es elegir un movimiento ganador desde una posición ganadora. (Aquí llamo a un movimiento ganador, si la posición sigue siendo ganadora después de jugarlo). Para diferenciar, llamaré a la POSICION-COMPLEJIDAD y la última MOVIMIENTO-COMPLEJIDAD.

Es fácil ver que si la MOVILIDAD-COMPLEJIDAD está en o , también lo es la POSICIÓN-COMPLEJIDAD: podemos calcular los movimientos óptimos y verificar quién gana al final. (Realmente no he pensado qué pasa si MOVE-COMPLEXITY está en , probablemente POSITION-COMPLEXITY está en algo así como .) Sin embargo, hay ejemplos ficticios cuando MOVE-COMPLEXITY es trivial y POSITION -COMPLEXITY es arbitrariamente difícil, como el juego (no muy interesante) de verificar cuál es la salida de un algoritmo, con los jugadores haciendo los siguientes pasos, permitiéndose solo un movimiento. Me he desviado un poco, mi pregunta principal es la siguiente.P S P A C E N P P N $P$$PSPACE$$NP$$P^{NP}$

¿Existe un juego natural, donde la MOVILIDAD-COMPLEJIDAD de los dos jugadores es diferente?

Por ejemplo, el juego donde el primer jugador elige los valores de las variables de un CNF (que podría no tener una solución), mientras que el segundo jugador está tratando de resolver un rompecabezas SOKO-BAN (que podría no tener una solución), es Tal ejemplo.

Quizás un juego bastante natural es el siguiente:

El jugador 1 se coloca en el medio de un laberinto y debe llegar a la salida para ganar.

El jugador 2 está en el mismo laberinto y debe recoger un conjunto de "componentes" para construir un controlador de radio que le permita cerrar la salida (y ganar).

$n$$n$

Para que el juego sea más "interactivo", también podemos agregar algunas acciones adicionales al Jugador 2 que solo pueden causar una desaceleración polinómica en el cálculo del próximo movimiento para el Jugador 1; por ejemplo permitiéndole bloquear un número fijo de corredores del laberinto.

$C$

Entonces es suficiente mirar algunos juegos naturales donde la POSICION-COMPLEJIDAD es asimétrica. Siempre necesitaremos cierta asimetría entre los jugadores para crear tales situaciones, pero esperamos que sea lo más natural posible.

$\cap$

$P_1$$P_2$$p(n)$$i$$P_i$

De hecho, en los llamados juegos Picker-Chooser o Chooser-Picker es fácil construir ejemplos para los cuales la mejor estrategia de un jugador es una estrategia de emparejamiento simple, mientras que el otro tiene que resolver un 3-SAT en cualquier CNF especificado anteriormente, ese es un problema NP-completo.

Digamos, un juego Picker-Chooser es un juego asimétrico en una hipergrafía H = (V, E): Picker elige dos elementos no seleccionados de V, luego Chooser toma uno de estos y devuelve el otro a Picker. El seleccionador gana si obtiene todos los elementos de una A de E. Ahora, dada una fórmula F de CNF de 3-SAT, V es el conjunto de literales y E se da cuenta de algún dispositivo. Con todo, Picker siempre debe ofrecer x_i y x_i negado en todos los pasos (de lo contrario, pierde de inmediato), mientras que la selección del Selector es una entrada arbitraria de 0-1 para cualquier x_i, y gana al satisfacer F.

Vea los detalles en: A. Csernenszky, R. Martin y A. Pluhár, Sobre la complejidad de los juegos posicionales de selector-selector. Enteros 11 (2011).

o en: http://www.inf.u-szeged.hu/~pluhar/complexity_2011.pdf