¿Existen posiciones de ajedrez que requieran un número exponencial de movimientos para alcanzarlas?

Question

Por "ajedrez" aquí me refiero al ajedrez jugado en un $n\times n$ tablero con un número ilimitado de piezas (no rey). Hay que tener cierto cuidado si se quieren generalizar algunas de las reglas más sutiles del ajedrez a un $n\times n$ tablero, pero no me detendré en este punto porque la respuesta a la pregunta que me interesa debería ser la misma bajo cualquier generalización razonable. A saber, ¿existe una secuencia infinita $(A_n, B_n)$ de pares de posiciones de ajedrez en un $n\times n$ tablero tal que el número mínimo de movimientos legales requeridos para llegar desde $A_n$ a $B_n$ es exponencial en $n$ ? Aquí permito cualquier legal movimientos y no sólo movimientos estratégicamente inteligentes.

Técnicamente, esta pregunta podría clasificarse como un "problema abierto" (que es ilegal en MO) porque fue planteada implícitamente por A. Fraenkel y D. Lichtenstein en "Computing a perfect strategy for $n\times n$ el ajedrez requiere un tiempo exponencial en $n$ ," J. Comb. Th. A 31 (1981), 199-214. Sin embargo, creo que es un juego justo para MO porque estoy bastante seguro de que esto no se ha mirado mucho. Fraenkel y Liechtenstein demostraron que determinar si una posición de ajedrez dada está ganada para las blancas (con el mejor juego) es EXPTIME-completo y preguntaron por la complejidad computacional del problema de alcanzabilidad del ajedrez ("es $B_n$ accesible desde $A_n$ ?"). Claramente la alcanzabilidad del ajedrez está en NPSPACE = PSPACE, y Hans Bodlaender ha demostrado que es NP-difícil . Si la respuesta a la pregunta que he planteado más arriba es "No, siempre se puede hacer con un número polinomial de movimientos", entonces se resolvería este problema demostrando que la alcanzabilidad del ajedrez es NP-completa, porque al exponer la secuencia de movimientos se obtiene un certificado corto.

Si tiene alguna experiencia con problemas de ajedrez retrógrados y si ha leído el precioso libro de Hearn y Demaine Juegos, rompecabezas y computación entonces se puede intuir que barajar las piezas de ajedrez recuerda a otros rompecabezas de reordenación que se han demostrado como completos en PSPACE. Sin embargo, he preguntado tanto a Demaine como a Hearn y ninguno de ellos ha visto inmediatamente cómo demostrar que la alcanzabilidad del ajedrez es PSPACE-completa.

[Edición: Buscando con más cuidado en el libro de Hearn y Demaine, veo que enumeran este problema en su lista de problemas abiertos al final del libro bajo el nombre de "Ajedrez retrógrado". No me di cuenta antes porque por alguna razón esa página no aparece en el índice bajo "ajedrez". Tal vez se me pueda culpar por usar el nombre "Ajedrez retrógrado" para este problema porque así lo llamé cuando publiqué por primera vez esta pregunta en USENET hace tiempo. Creo que "reachability" es un nombre mejor para ello].

Answer 1

He aquí un resumen de la solución propuesta en este artículo de arXiv . Un par de posiciones en el $n\times n$ se construye el tablero de ajedrez para el que (1) existe una secuencia $\sigma$ de jugadas legales de ajedrez que conducen de $P$ a $P'$ (2) la longitud de $\sigma$ no puede ser inferior a $\exp\Theta(n)$ .

La idea es construir una posición que consiste esencialmente en $m$ pistas cada uno de los cuales se encuentra en algún estado en cada momento. El conjunto de estados posibles de $i$ es un grupo de ciclos de orden igual a $(i+3)$ rd primo, y la posición se define de forma única por los estados de todas las vías. A "mover" aumenta cada estado en $1$ o disminuye cada estado en $1$ . Transformando $(0,0,\ldots,0)$ a $(1,0,\ldots,0)$ es posible mediante los restos chinos, pero requiere al menos $p_5\ldots p_{m}=\exp(p_m+o(p_m))$ "movimientos".

---

  (fuente)

---

Las posiciones de ajedrez que representan pistas utilizan el patrón anterior que es un ejemplo específico correspondiente a $m=3$ . Los puntos denotan peones, y suponemos que los reyes están situados en otro lugar del tablero. En el documento se explica (en términos diferentes) por qué podemos pensar en los ciclos oscuros como pistas, en las posiciones de los alfiles blancos en ellas como estados, y en las "jugadas" como secuencias mínimas de movimientos legales de ajedrez cuyas posiciones iniciales y resultantes coinciden hasta un color de piezas.

Answer 2

Con $n/100$ reyes negros y un rey blanco, es posible.

La idea es hacer un "cambio", una habitación que está en uno de los dos estados, tiene 1 entrada, e, y 2 salidas; x e y, el rey blanco entra en la habitación a través de un túnel de peones, si está en estado 1, debe salir por x, mientras que al cambiar el estado de la habitación a 0, en estado 0 debe salir por y dejando la habitación en estado 1.

Con k interruptores etiquetados de 1 a k, conecte todos los $x_i$ con $e_1$ y $y_j$ a $e_{j+1}$ para todos los j. Empezarlo con el rey en $e_1=x_i$ y todos los interruptores a 0, para encender el último interruptor se verá que hay que transitar por todos los estados posibles, dando un mínimo de $2^k$ se mueve.

El interruptor realmente necesita un diagrama, pero la idea es tener un rey negro para cada interruptor, el rey negro bloqueará una torre negra impidiendo el jaque, para que el rey blanco pueda llegar a una siguiente habitación, donde bloqueará una torre blanca, para que el rey negro pueda llegar a una tercera habitación, bloqueando una torre negra, teniendo el rey blanco la salida, el rey negro no puede volver sin el rey blanco, pero puede continuar hasta la entrada negra de una segunda secuencia de habitaciones, cuya salida negra está conectada a la entrada negra de esta secuencia. Las dos entradas blancas están conectadas, y las dos salidas blancas son x e y. Por lo tanto, el rey negro está en uno de los dos túneles, correspondientes a los estados 0/1, lo que determina qué salida está disponible para el rey blanco.

Puede que haya alguna forma de construir los interruptores sin reyes también.

Debe haber una fila de peones debajo y encima del diagrama del componente del interruptor.
Acoplar 4 de estos de cada color para hacer 1 interruptor.

Answer 3

Creo que se merece al menos una respuesta parcial a su pregunta parcial.

Se está dando un gran salto al no especificar las reglas generalizadas, incluyendo la regla de los cincuenta movimientos .

Si esta regla se queda como está en el ajedrez (50), o se generaliza a un polinomio de su elección (acotado por $O(n^k)$ para un fijo $k$ ), entonces la respuesta a su pregunta es "No", aparte de la posibilidad de pares de posiciones completamente inalcanzables. Un límite superior en la longitud de cualquier secuencia legal de movimientos es $O(n^{k+3})$ dado que se permite a lo sumo $n^2$ piezas por jugador y que cada pieza puede aportar menos de $n$ movimientos de peones.

Answer 4

Si la alcanzabilidad está en PSPACE, entonces está en NP porque durante la búsqueda una vez que se alcanza el objetivo se puede parar inmediatamente, sin resultados de backtracking. A diferencia de Othello, en el que una configuración requiere que las configuraciones hijas devuelvan un valor, la alcanzabilidad puede hacerse con una máquina no determinista. No requiere mantener la lista de configuraciones visitadas. Puede olvidarse de ellas inmediatamente. Si todavía no entiendes lo que digo, contrasta la diferencia entre la evaluación de Othello y la alcanzabilidad.

P.D. La posibilidad de longitud exponencial queda descartada ya que está en PSPACE. De lo contrario, PSPACE no es suficiente para almacenar el camino actual. Aquí es necesario almacenar el camino porque las máquinas PSPACE no son no deterministas (o ramificadas), por lo que tiene que retroceder.