Decidibilidad del ajedrez en un tablero infinito

Question

La reciente pregunta ¿Existen posiciones de ajedrez que requieran un número exponencial de movimientos para alcanzarlas? de Tim Chow me recuerda un problema que me ha interesado. ¿Es decidible el ajedrez con un número finito de hombres en un tablero infinito? En otras palabras, dada una posición en un tablero infinito (digamos $\mathbb{Z}\times \mathbb{Z}$ (aunque ahora la promoción de peones no es posible) con un número finito de hombres, digamos que con las blancas para mover, ¿existe un algoritmo para determinar si las blancas pueden dar jaque mate a las negras (o evitar que las negras den jaque mate a las blancas) contra cualquier defensa negra?

Answer 1

Existe una solución positiva para la decidibilidad de la pareja en $n$ versión del problema.

Muchos de nosotros estamos familiarizados con el Las blancas dan mate en 3 variedad de problemas de ajedrez, y podemos considerar el análogo natural en el ajedrez infinito. Así, refinamos el posición ganadora problema, que pregunta si un jugador designado tiene una estrategia ganadora desde una posición determinada, a la mate-en- $n$ problema, que pregunta si un jugador designado puede forzar una victoria en un máximo de $n$ pasa de un posición finita dada. (Y nótese que, como se discute en Johan Wästlunds jaque mate en $\omega$ ¿se mueve? hay posiciones ganadoras finitas en infinitas ajedrez que no son mate-en $n$ para cualquier $n$ .) Aun así, el compañero en $n$ El problema parece ser todavía muy complicado, naturalmente formulado por afirmaciones con $2n$ muchos cuantificadores alternos: hay un movimiento para las blancas, tal que para cada respuesta negra, hay hay una contramovida de las blancas, y así sucesivamente. Las afirmaciones con tal complejidad de cuantificadores no son no son generalmente decidibles, y no se puede esperar buscar un árbol de juegos de ramificación infinita, incluso hasta una profundidad finita. Así que uno podría naturalmente esperar que el mate-en $n$ problema sea indecidible.

A pesar de esto, el problema del mate-en-n del ajedrez infinito es decidible computacionalmente, y de manera uniforme. Dan Brumleve, yo mismo y Philipp Schlicht acabamos de presentar un artículo que establece esto a la CiE 2012 y espero hablar de ello allí en junio.

D. Brumleve, J. D. Hamkins y P. Schlicht, "El compañero en n problema del infinito de ajedrez es decidible". 10 páginas, arxiv pre-print , presentado a CiE 2012 .

Resumen. El ajedrez infinito es un ajedrez que se juega en un sin bordes. Las conocidas piezas de ajedrez se mueven según reglas habituales del ajedrez, y cada jugador se esfuerza por dar jaque mate al rey rey contrario en jaque mate. El compañero en $n$ problema del infinito es el problema de determinar si un jugador designado puede forzar una victoria desde una posición finita dada en un máximo de n movimientos. A formulación ingenua de este problema conduce a afirmaciones de alta complejidad aritmética con $2n$ cuantificadores alternos hay una jugada para las blancas, tal que para cada respuesta negra, hay una contra-movida para las blancas, y así sucesivamente. En una formulación de este tipo, el problema no parece parece ser decidible; y no se puede esperar buscar un árbol de juego de ramificación infinita, incluso con una profundidad finita. No obstante, el teorema principal de este artículo, que confirma una conjetura del primer autor y de C. D. A. Evans, establece que la pareja en $n$ problema del ajedrez infinito es decidible computacionalmente, uniformemente en el posición y en $n$ . Además, existe una estrategia computable para el juego óptimo de dicho mate en $n$ posiciones. La prueba procede mostrando que la pareja en $n$ el problema es expresable en lo que llamamos la estructura de primer orden del ajedrez $\frak{Ch}$ que demostramos (en el fragmento correspondiente) que es una estructura automática, cuya teoría es por tanto decidible. Por desgracia, esta resolución de la pareja en $n$ problema no parece resolver el decidibilidad del problema más general de la posición ganadora, el problema de determinar si un jugador designado tiene una estrategia ganadora estrategia ganadora a partir de una posición dada, ya que una posición puede admitir una estrategia ganadora sin ningún límite en el número de movimientos necesarios. Este problema está relacionado con los valores de juego transfinitos en el ajedrez infinito ajedrez, y el valor exacto de la omega del ajedrez $\omega_1^{\rm chess}$ no se conoce.

La solución también se puede plantear en términos de aritmética de Presburger, de una manera cercana a la respuesta de Dan Brumleve a esta pregunta. En concreto, una vez que nos limitamos a una determinada colección de piezas $A$ entonces podemos representar todas las posiciones utilizando sólo piezas en $A$ como una tupla de longitud fija de números naturales, y las relaciones elementales de movimiento, ataque y control son expresables para esta representación en el lenguaje de la aritmética de Presburgo, esencialmente porque las piezas a distancia -torres, alfiles y reinas- se mueven todas en líneas rectas cuyas ecuaciones son expresables en la aritmética de Presburgo. (No es necesario manejar la codificación de secuencias en general, ya que el número de piezas no aumenta durante el juego). Dado que el mate-en $n$ Por lo tanto, si el problema es expresable en la aritmética de Presburgo, se deduce que es decidible.

Answer 2

Sí, porque cualquier posición de ajedrez puede traducirse a la aritmética de Presburgo. Para una combinación inicial fija de tipos de piezas, definamos que una posición consiste en una ubicación (x, y) para cada pieza, así como un bit (c) para indicar si ha sido capturada o no. En la aritmética de Presburgo podemos definir recursivamente la proposición "Las blancas no pueden capturar el rey de las negras en menos de t jugadas partiendo de la posición inicial X", y luego aplicar el esquema de axiomas de inducción para obtener una expresión que signifique "Las blancas no pueden dar jaque mate nunca partiendo de la posición inicial X". Como la aritmética de Presburgo es completa, siempre podremos demostrar esta afirmación o su negación.

EDIT: Resumen de cómo se supone que funciona esto:

1. P(A) = Es la jugada de las blancas y éstas aún no han ganado en la posición A.
2. R(A, B) = La posición B sigue legalmente en un movimiento desde la posición A.
3. Q(A, 0) = P(A)
4. Q(A, t) = para todo B: (R(A, B) -> existe C: R(B, C) -> Q(C, t - 1))
5. S(A) = Q(A, 0) y (para todo t: Q(A, t) -> Q(A, t + 1))

Esto funciona bien al menos hasta la línea cuatro donde Q(A, t) se define recursivamente. Si Q(A, t) pudiera definirse como un predicado en aritmética de Presburgo, creo que la línea cinco también funcionaría. Pero esto es un problema serio y tal vez rompa todo el enfoque.

Answer 3

No hay tal algoritmo bajo al menos una especificación rigurosa de la pregunta.

Consideremos una posición en la que hay un rey negro en (0,0) y ninguna otra pieza negra; torres blancas en $(1,5)$ y $(-1,5)$ y posiblemente una reina blanca en una posición de la forma (0, $n$ ) para algunos grandes $n$ . Imagínate un rey metido en un largo túnel. Entonces las blancas pueden dar jaque mate a las negras (y lo hacen, desde el principio) si y sólo si la dama existe en algún lugar del túnel. Si sólo hay dos torres, creo que el rey puede evitar el jaque mate moviéndose indefinidamente hacia el infinito (véase mi explicación en los comentarios más abajo).

Usando posiciones así, dado cualquier conjunto de e.r. $K$ y cualquier número $m$ Puedo hacer una posición de ajedrez tal que las blancas puedan dar jaque mate a las negras si y sólo si $m \in K$ : Puse a la reina en $(0,n+5)$ si y sólo si $m$ está enumerado en $K$ después de exactamente $n$ pasos. Así puedo decidir la afiliación en $K$ , relativo a un oráculo para su problema. En realidad sólo necesito un oráculo que funcione para índices de posiciones computables. Esto demuestra que cualquier solución a su problema es de grado al menos $0'$ .

Nota: He considerado que una "posición" es una función que va de las ubicaciones en el tablero a las piezas. Podrías intentar evitar esta solución especificando otra cosa como "posición". Por ejemplo, usted podría hacer una posición de una función de una lista de piezas a los lugares en el tablero, y que podría conducir a una solución diferente. Sin embargo, necesita requerir que la lista diga explícitamente cuántas piezas hay desde el principio, o una variación de esta solución seguirá aplicándose.

Answer 4

Sí. Hay un tamaño de tablero finito que tiene esencialmente la misma estructura de solución que todos los tableros más grandes y un tablero infinito, y podemos encontrarlo resolviendo el juego completamente para tamaños de tablero crecientes hasta que se pueda reconocer ese tamaño final. (El tablero infinito se diferencia de un tablero muy grande sólo en que no tiene bordes ni esquinas, por lo que su estructura de solución es más pequeña). Eventualmente esto es posible, porque sólo hay un número finito de piezas, y por lo tanto sólo un número finito de clases de equivalencia de estructuras de solución. Cuando el número de tales clases de equivalencia deja de crecer, hemos terminado. Básicamente, todas las posiciones con piezas que no están cerca del borde del tablero pero sí lejos del centro (digamos las que tienen piezas dentro de un círculo) pueden identificarse con posiciones más acotadas (las que están rodeadas por ese círculo), porque las piezas con un número infinito de opciones (Reina, Torre, Alfil) pueden ir a cualquier parte (hasta la paridad) con no más de 2 movimientos, y las otras piezas se ven obligadas a recorrer largas distancias para las que lo único que importa son las longitudes relativas de sus caminos con una cierta precisión. Cuando un conjunto de piezas se aleja lo suficiente de otro conjunto de piezas como para que los dos conjuntos estén ahora en posición general, estos subproblemas interactúan de forma equivalente, por lo que la descripción de la solución completa dejará de aumentar con el tamaño del tablero.

De forma más general, esta estrategia funciona para cualquier juego de tipo ajedrez en el que las piezas pueden clasificarse en tipos "ultra-móviles" y "para-móviles" con libertad constante y lineal respectivamente. Por ejemplo, también es válida para las damas, ya que todas las piezas son para-móviles.

Todavía no puedo especificar la equivalencia entre posiciones con la suficiente precisión como para establecer un límite explícito sobre el tamaño necesario del tablero finito en términos del número de piezas n, pero supongo que es O(f(n!)) para alguna función polinómica f cuyo orden es O(n), o en otras palabras O((n!)^(k*n)) para algún k, utilizando la técnica de construcción que he sugerido. El término super-exponencial es aportado por las piezas para-móviles y el polinomio por las ultra-móviles. En cualquier caso sólo he pretendido demostrar que el tamaño necesario del tablero tiene un computable con la que se ha de contar.

Answer 5

Me gustaría convencer a todos de que este problema es indecidible. No puedo demostrarlo para el ajedrez, ya que carezco de la capacidad de diseñar ciertas configuraciones, pero creo que deben existir. E incluso si no existen, para algún juego parecido al ajedrez ciertamente existen, lo que demuestra que los intentos de demostrar la decidibilidad deben ser incorrectos.

Hm, después de leer detenidamente los comentarios a la pregunta original, me he dado cuenta de que ya hay una indicación de un argumento muy similar al mío por parte de Tsuyoshi Ito: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006 Sigo dejando mi prueba aquí, ya que de hecho dos fichas son suficientes y quizás la mía sea más detallada.

La reducción se basa en la noción de contramáquina*. Es indecidible si una máquina contadora con sólo dos contadores se detiene o no. Así que nuestro objetivo sería simular cualquier máquina de este tipo con una posición de ajedrez. Puedo ver dos maneras de hacerlo.

i, Construir dos configuraciones separadas, de manera que ambas tengan una parte inicial y una parte móvil que pueda cambiar (para almacenar el estado). Además, las partes móviles estarían conectadas, por ejemplo, por torres, que podrían dar jaque mate, si se liberan, por lo que si un estado mueve 1, el otro tiene que mover k, y así sucesivamente.

ii, Construir una única configuración, que dependiendo de su estado, se mueve l horizontalmente y -k verticalmente. Además, coloque una torre en (0,0) que nunca se mueva, pero que pueda garantizar que la configuración pueda "sentir" cuando vuelva a una ficha vacía.

Así que lo único que queda por hacer es diseñar esas configuraciones, lo que supongo que debe ser posible con algo de esfuerzo y conocimientos de ajedrez. Además, nótese que en ambos casos la construcción utiliza una pieza cuyo alcance no está acotado, me pregunto si esto es realmente necesario.

*Me he dado cuenta de que la definición de la wikipedia es diferente de lo que quiero. De hecho, mi máquina debería llamarse probablemente una máquina de 2 pilas que puede empujar sólo una letra a la pila. Así que quiero una máquina de estado finito con dos contadores que están vacíos al principio y puede aumentar o disminuir cualquier contador en uno o comprobar si un contador es cero o no. El problema de si tal máquina se detiene o no, es indecidible.