Ajedrez infinito
El ajedrez infinito es cualquier variante del ajedrez jugado en un tablero sin límites. Varios jugadores, teóricos del ajedrez y matemáticos han introducido versiones de ajedrez infinito de forma independiente, tanto como un juego jugable como un modelo para el estudio teórico. Se ha encontrado que aunque el tablero no tiene límites, hay formas en las que un jugador puede ganar en un número finito de movimientos.
El ajedrez clásico se juega en un tablero de 8 × 8 (64 casillas). Sin embargo, la historia del ajedrez incluye variantes del juego jugado en tableros de varios tamaños. Un juego predecesor llamado ajedrez Courier se jugaba en un tablero un poco más grande de 12 × 8 (96 casillas) en el siglo XII, y continuó jugándose durante al menos seiscientos años. El ajedrez japonés (shogi) se ha jugado históricamente en tableros de varios tamaños; el más grande es el taikyoku shōgi ("ajedrez definitivo"). Este juego similar al ajedrez, que data de mediados del siglo XVI, se jugaba en un tablero de 36 × 36 (1296 casillas). Cada jugador comienza con 402 piezas de 209 tipos diferentes, y un juego bien jugado requeriría varios días de juego, posiblemente requiriendo que cada jugador haga más de mil movimientos.
Para el ajedrez infinito, se ha encontrado que los problemas de mate-en- n jugadas es decidible; es decir, dado un número natural n y un jugador al que mover y las posiciones (como en ) de un número finito de piezas de ajedrez uniformemente móviles y con libertad constante y lineal, existe un algoritmo que responderá si hay un jaque mate forzado en un máximo de n jugadas. Uno de estos algoritmos consiste en expresar la instancia como una sentencia en la aritmética de Presburger y utilizar el procedimiento de decisión para la aritmética de Presburger.
Sin embargo, no se sabe si los estudios sean posiciones decidibles. Además de la falta de un límite superior obvio en el más pequeño como n cuando hay un mate-en n, también podría haber posiciones para las que hay un mate forzado pero ningún entero n tal que haya un mate-en-n . Por ejemplo, podría haber una posición tal que después de una jugada de las negras, el número de jugadas hasta que las negras tengan jaque mate será igual a la distancia a la que las negras movieron la pieza que movieron las negras.
En inglés: