No existe ninguna posición de ajedrez alcanzable con más de 218 movimientos posibles

• No existe una posición con más movimientos posibles que la posición de ajedrez de 218 movimientos presentada por Nenad Petrović en 1964
• Como explorar todas las posiciones es imposible en la práctica, se demostró el límite usando optimización matemática y técnicas de modelado por computadora
• Se redujo eficazmente el espacio de búsqueda eliminando piezas innecesarias, permitiendo colocación parcial de piezas y simplificando el enroque, entre otras medidas
• Finalmente, se confirmó con la herramienta de optimización Gurobi que 218 es el máximo, y además se verificaron otros registros, como 144 movimientos (sin promociones)
• Gracias a esta investigación, los desarrolladores de motores de ajedrez y de compresión pueden eliminar la incertidumbre sobre el límite máximo de movimientos

---

Introducción: la controversia sobre la posición de ajedrez de 218 movimientos

Desde que el gran maestro de composición ajedrecística Nenad Petrović publicó en 1964 una posición con 218 movimientos posibles, han continuado los intentos por superar ese récord. El autor, como científico de la computación, buscó cerrar definitivamente esta pregunta analizando posiciones con ayuda de computadoras. Aunque existen aproximadamente 4.8 × 10^44 posiciones de ajedrez alcanzables, una exploración de tal magnitud es irrealizable en la práctica.

Introducción de la optimización matemática

Minimización de piezas y combinaciones innecesarias

• Los casos en que las piezas negras aumentan adicionalmente la cantidad de movimientos son limitados
  • Por ejemplo, cuando permiten que un peón blanco capture o cuando evitan una situación de jaque al rey rival
• La mayoría de las piezas negras pueden eliminarse sin afectar el número máximo de movimientos
• Mientras la cantidad de piezas lo permita, es posible reemplazar piezas negras por piezas más débiles o ajustar su colocación bajo ciertas restricciones (como clavadas)
• En el caso de las piezas blancas ocurre lo contrario: si en una posición óptima se reemplazan todas por piezas fuertes como la dama, puede surgir una posición ilegal, por lo que se requieren ajustes finos

Situaciones de jaque y límites en la cantidad de movimientos

• No es necesario considerar posiciones en las que el rey negro esté en jaque, porque no son posiciones legales
• Cuando el rey blanco está en jaque, su movilidad se restringe severamente (máximo 120 movimientos), por lo que es imposible llegar a 218
• Por lo tanto, la búsqueda puede limitarse únicamente a posiciones sin jaque

Colocación parcial de piezas y modelado matemático

Para reducir la complejidad combinatoria, se adoptó un modelo con colocación parcial (fractional) de piezas, movimientos, y una relajación de algunas reglas del ajedrez

• Por ejemplo, una pieza puede estar con 27.3% de probabilidad en e4 y con 72.7% en otra casilla
• De esta forma, se implementó como un problema de programación lineal entera (ILP, Integer Linear Programming) en herramientas modernas de optimización como Gurobi
• Al principio se toparon con límites de memoria y tiempo (agotamiento de memoria tras unas 55 mil segundos)
• Para simplificar el espacio de búsqueda, se aplicaron medidas adicionales como simplificar las reglas de enroque, ignorar el jaque, ignorar las clavadas y simplificar la condición de captura al paso

Optimización y conclusión

Finalmente, tras mejorar el modelo con restricciones auxiliares que bloqueaban la exploración de combinaciones innecesarias, la optimización se completó con el programa Gurobi

• La cota superior se fue reduciendo de 305 movimientos → 271.67 movimientos → 218 movimientos
• Se confirmó que solo 12 posiciones representativas con 218 movimientos posibles son alcanzables
• Se demostró que estas posiciones son legales y pueden alcanzarse sin problemas mediante partidas de prueba (proof game)

Además, también se verificó un máximo de 144 movimientos sin promociones, 288 movimientos en posiciones ilegales, y 271 movimientos en posiciones legales pero inalcanzables

Resultados e importancia

• Gracias a este resultado, los desarrolladores de motores de ajedrez y los investigadores de algoritmos de compresión pueden tener la certeza de que un límite de 256 movimientos es suficiente para el diseño de memoria y otros aspectos
• Quedó demostrado matemáticamente que no existe ninguna posición con 218 o más movimientos posibles por una vía legal

Resumen del FAQ

• Una partida de ajedrez puede durar más que 218 movimientos, pero este estudio trata el máximo de opciones posibles en un solo turno
• Si algunas posiciones parecen inalcanzables, se menciona que puede haber varias rutas, por ejemplo cuando la jugada previa termina en captura
• Este método de investigación aplicó una técnica de oráculo matemático para descartar rápidamente combinaciones absolutamente imposibles dentro de un espacio combinatorio enorme
• También se publicaron el código utilizado y la validez matemática de la evidencia obtenida para reforzar la confiabilidad

Tareas futuras y propuestas de investigación adicional

Aplicando esta técnica, sería posible abordar otros problemas de ajedrez como el "máximo número de capturas", "máximo número de tablas por ahogado", "máximo número de jaques", "máximo número de jaque mate" o "máximo número de mates en 2". Sin embargo, en algunos casos podrían requerirse algoritmos de optimización creativos adicionales.

Conclusión

• 218 es el máximo número oficial de movimientos posibles en un turno dentro de una posición de ajedrez
• En términos prácticos, el software de ajedrez y los investigadores pueden diseñar sus estructuras en torno a 218 (o 256)
• El código relacionado y los resultados de optimización están publicados en GitHub

Referencia

• Se incluyen enlaces a partidas de prueba y posiciones como la posición de 218 movimientos de Nenad Petrović y la de 144 movimientos de Jenő Bán (sin promociones)
• Para más detalles y el código, se puede consultar el repositorio de GitHub

[GN⁺]

Comentarios de Hacker News

• Aunque no lo expresan de forma directa, lo que quieren decir aquí es: "en esta posición, el jugador tiene 218 jugadas legales entre las que puede elegir"
  • Me sorprende darme cuenta de que había estado leyendo mal este artículo todo este tiempo, gracias. Yo lo había entendido como "el máximo número de movimientos necesarios para llegar a alguna posición de ajedrez es 218". Por eso me preguntaba por qué el artículo no tenía ningún sentido para mí
  • Yo también pensé: "¿cuántos movimientos se necesitan en una partida para llegar a esta posición?"
  • Sí, es realmente extraño que el artículo nunca use la expresión "possible moves". La palabra clave es "possible". El artículo sigue diciendo algo como "have moves", pero esa no es una forma de hablar familiar para el público general (aunque quizá sea más común en la terminología ajedrecística)
  • Gracias. Yo también estaba confundido con este artículo; pensé que se trataba de la posición que requería la mayor cantidad de movimientos
• Quiero elogiar especialmente a Lichess. Ofrece un servicio y contenido fantásticos gratis, y funciones que Chess.com cobra también están disponibles gratis. Además, tiene muchísimas variantes del juego
  En Lichess, el nivel de juego en variantes como 960 o Crazyhouse es muchísimo más alto que en Chess.com
  • Es gratis, ofrece las mismas funciones que los servidores comerciales, es de código abierto y amigable para desarrolladores. Tampoco tiene anuncios (ni siquiera en las cuentas gratuitas) y tiene una estructura organizativa transparente bajo la ley francesa
    Literalmente es absurdamente bueno. Recomiendo donar si pueden
• En https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow, el autor explica que al principio eliminó algunas reglas complejas y que estaba dispuesto a reintroducirlas si era necesario (si el resultado de la solución violaba esas reglas)
  Lo interesante es que los solucionadores de programación lineal entera mixta (MILP) ya soportan este tipo de manejo. En términos técnicos se llama row generation, y suele usarse cuando el problema se escribe en forma matricial, donde las filas son restricciones y las columnas son variables
  Agregar nuevas filas de forma (dinámica) es equivalente a introducir restricciones solo cuando se violan
  Este enfoque se usa sobre todo para resolver el problema del viajante (Traveling Salesman Problem)
  (Por cierto, en Wikipedia existe Column generation, pero no row generation)
  • Hola, soy el autor del artículo de Lichess
    Relajar u omitir reglas de ajedrez también influyó en la elección de variables. Antes de entrar al modelado matemático, probé cosas como lazy constraints, pero no hubo una mejora significativa en velocidad. Por ejemplo, solo con no considerar si el rey blanco está en jaque ya se simplificaban muchas cosas
  • A esto normalmente se le llama más bien lazy constraints (explicación relacionada)
  • De verdad me pregunto si un solver MILP podría terminar en un espacio de búsqueda tan enorme; mi intuición es que no
• Pregunto por curiosidad genuina: si el solver de programación entera de Gurobi no encontró una solución mejor que 218, ¿eso garantiza que no existe una mejor que 218? Y también me pregunto si eso equivale a una prueba matemática
  (Suponiendo para esta discusión que Gurobi no tiene bugs y que tampoco hay bugs en la definición e implementación del problema por parte del autor)
  Me pregunto si existe la posibilidad de que Gurobi se haya quedado atorado en un óptimo local, o si realmente probó que se trata del óptimo global
  • Gurobi no solo da la mejor solución entera encontrada hasta ahora, sino también una cota del posible óptimo. Para esa cota usa varias técnicas como la relajación lineal del problema, planos de corte, etc. Así que, si el solver no tiene bugs, entonces sí es realmente óptimo
  • ¡Soy el autor!
    Si Gurobi y mi código funcionaron como se pretendía, y no hubo errores lógicos al simplificar el modelo de ajedrez, entonces lo que obtuve prueba que "el máximo número posible de jugadas legales entre todas las posiciones de ajedrez alcanzables desde la posición inicial por una secuencia legal de jugadas tiene cota inferior y superior de 218". Es decir, Gurobi demostró mediante cotas sobre todo el espacio de búsqueda que "no existe un caso mejor que este"
  • No sé exactamente cómo se aplicó Gurobi en este caso, pero en general estos solvers de optimización combinatoria construyen un árbol de prueba que muestra que no puede haber una solución mejor bajo ninguna asignación de variables. En casos simples, incluso puedes revisar ese árbol tú mismo y seguir la deducción por contradicción. En este artículo, el árbol de prueba probablemente sería gigantesco. Pero, si quisieras, en principio sí podría revisarse
  • En teoría no es una prueba, pero en la práctica es casi como si lo fuera

• No hay ninguna posición de ajedrez alcanzable con más de 218 jugadas
  Sería mucho más claro decir: "no hay más de 218 jugadas legales posibles desde una posición"

¿Revisar las aproximadamente 8.7x10^45 posiciones de ajedrez alcanzables?
Esa cifra en realidad es una sobreestimación
En https://github.com/tromp/ChessPositionRanking estiman con mayor precisión la cantidad de posiciones legales de ajedrez en unas 4.8x10^44

• ¿Esa estimación no es simplemente como 20 veces distinta? A esta escala no parece una gran diferencia
• Una es "legal" y la otra es "todo el espacio del problema"
  Desde la perspectiva computacional, importa más el espacio total del problema. Porque hay que "calcularlas" todas antes de determinar si son legales o no. No existe un método sencillo para iterar solo sobre posiciones legales
• Hola a todos
  Una persona conocida me avisó que mi artículo se estaba discutiendo aquí
  Perdón por haber elegido un título poco claro; espero que ahora quede más claro. Gracias por los comentarios y por las palabras amables
  Si tienen preguntas sobre probar hechos similares en ajedrez, también puedo responderlas ^^
  Gracias
  Tobi
  • Entonces, para confirmar: ¿esto significa que en cualquier posición del tablero no puede haber más de 218 jugadas entre las que elegir? ¿Esa es la interpretación correcta?
• ¿Cuál sería la cantidad mínima de bits necesaria para representar un tablero de ajedrez alcanzable?
  Actualización: el artículo dice que hay aproximadamente 8.7x10^45 posiciones de ajedrez alcanzables, y https://github.com/lechmazur/ChessCounter usa esa cifra como cota superior
  (Eso equivale a unos 153 bits)
  • Si son aproximadamente 4.8x10^44, entonces log2(4.8x10^44) da 149 bits
    Pero para poder decodificarlo eficientemente necesitas 153 bits, usando el techo de log2 del número recomendado por el proyecto ChessPositionRanking (8726713169886222032347729969256422370854716254). ChessCounter no proporciona código de decodificación eficiente
  • El rey puede estar en cualquiera de las 64 casillas
    Lo mismo pasa con torres/reinas/caballos, pero como en ajedrez pueden haber sido capturados, se necesitan 65 estados posibles para cada una de esas 5 piezas
    Los alfiles solo pueden ir en la mitad de esas casillas, así que 33 estados cada uno
    Los peones tienen 4 promociones posibles, pueden haber sido capturados, y según el caso pueden estar en unas 20 a 30 posiciones distintas; en total, unos 290 estados por peón
    Con eso, para un color se necesitan unos 112 bits para representar el estado del tablero; redondeando, 224 bits para ambos lados
    En passant y las restricciones de enroque (por ejemplo, imposibilidad de enrocar) no requieren bits extra si redondeas, porque solo añaden algunos estados más a cada pieza
    Probablemente esta sea la forma más comprimida de una representación de tablero de longitud fija
    En una representación dispersa, como siempre existen ambos reyes, puedes representar las piezas vivas con un número decimal de n dígitos y n+2 números de 64 bits para sus posiciones, además de un poco de información extra para enroque, en passant, etc. Si en promedio ha desaparecido la mitad de las piezas, eso da aproximadamente 180 bits para representar el estado del tablero
    El historial de jugadas también requiere unos 10 bits por jugada (una pareja blanco/negro; un ply son 5 bits), así que alcanzaría para unas 18 jugadas. Eso es algo más corto que la mitad de la duración media de una partida de ajedrez
    Para comprimir más, parecería necesario implementar un diccionario gigantesco
  • El tipo y color de pieza pueden representarse con 4 bits
    Así que una codificación de longitud fija de todo el tablero sería 644 = 256 bits = 32 bytes
    O bien, si haces una representación de longitud variable solo para las piezas, puedes usar 6 bits por índice de casilla entre las 64, así que serían cantidad10 bits
    Por ejemplo, la posición inicial sería 32*10 = 320 bits = 40 bytes
  • Ese valor "restricted" de 8.7e45 en ese GitHub limita algunos patrones de promoción de peones
    5.68e50 en "general" es la verdadera cota superior y permite todas las promociones posibles
• El peón negro en b2 está reduciendo bastante la cantidad de jugadas posibles de las demás piezas
  Ese peón solo tiene una jugada posible (capturar al caballo que está al lado). Si ese peón no estuviera, cuatro reinas blancas y un caballo podrían entrar a b2. Pero en realidad esas jugadas no pueden existir porque el rey negro ya estaría en jaque mate
  Resulta tentador poner la reina de e5 en otro lugar para que no sea jaque mate inmediato, y al mismo tiempo abrir más la casilla b2
  Posdata: parece que ese peón debe sobrevivir ahí para evitar el ahogado
  • El peón negro en b2 no puede moverse en una posición con White to move
    Si fuera el turno de negras, el rey también estaría inmovilizado por la reina blanca en e5 (está clavado), así que tampoco podría moverse. Si no estuviera clavado, podría tener 4 movimientos. También serían posibles las subpromociones
  • A mí también me confundió la expresión "las piezas negras son inútiles". Parecía que, en vez de hacer que dos reinas se miraran entre sí, una de ellas podría hacerse negra para crear jugadas de captura mutua... pero luego entendí que "solo un bando puede mover"
  • Soy el autor
    La posición es con White to move. Incluso si el peón de b2 no clavara al rey por la reina blanca, el peón negro tampoco podría moverse
    El peón de b2 es absolutamente necesario para proteger al rey negro del jaque. Si no estuviera, la posición en sí no sería legal
    Revisé todo con muchísimo cuidado, así que pueden estar tranquilos: fue imposible construir algo con más de 218 jugadas para blancas. Aun así, me sorprende y me alegra que tanta gente se interesara en mi artículo, jaja ^^
  • Es turno de blancas. Si fuera turno de blancas mientras negras están en jaque, eso no sería legal y sería un estado inalcanzable. No habría forma de que se produjera legalmente en el turno anterior de negras
    Parece que podrías aumentar la cantidad de jugadas cambiando uno de los peones negros por un caballo blanco, pero ambos caballos ya existen y todos los peones ya fueron promocionados, así que no es posible. (Si cambias ambos peones, entonces negras no podrían haber llegado a este estado en el turno anterior)
• Estoy confundido. Pero después del modelo de 271, quisiera saber qué cambio llevó a la solución óptima. Solo dice: "con este modelo mejorado..."
  • ¡Soy el autor!
    ¿Leíste el artículo completo?
    No es 271, sino 271.666... :) Ese valor sale de un modelo en el que todas las decisiones (0 o 1) se relajan a valores continuos (0.0~1.0 y los intermedios). O sea, puedes asumir que una pieza existe en un 0.23, por ejemplo. Y la posibilidad de hacer cierta jugada también se trata como algo tipo 0.843
    Con esa clase de "magia negra", el cálculo se vuelve mucho más rápido y puede arrojar más jugadas de las que realmente existen
    Entonces esta técnica sirve para descartar rápidamente subespacios particularmente malos. Sin técnicas así, sería imposible revisar exhaustivamente todo el espacio de búsqueda
• ¿Se me está escapando algo, o la posición presentada al principio en realidad no es alcanzable? Es turno de blancas, pero los peones negros están en sus posiciones iniciales y el rey no tiene casillas vacías adyacentes; parece atrapado entre piezas y peones, así que no veo cómo se podría llegar a esa posición
  • Aquí hay una demostración de que esa posición sí es alcanzable: https://lichess.org/study/PLtuv3v5/zWPNxbSA
    Por cierto, creo que entendiste mal eso de que los peones negros están en sus posiciones iniciales. En realidad, el peón negro avanzó hasta el lado opuesto del tablero (el campo blanco)
  • El peón negro está en el campo blanco (rangos 1 y 2)