Resolución del ajedrez , la enciclopedia libre

La resolución del ajedrez es el proceso por el cual se busca encontrar una estrategia óptima para jugar al ajedrez, es decir, una mediante la cual uno de los jugadores (blanco o negro) siempre puede forzar una victoria, o ambos pueden forzar las tablas (ver juego resuelto). También significa resolver de forma más general juegos similares al ajedrez (es decir, juegos combinatorios de información perfecta), como el ajedrez infinito. Según el teorema de Zermelo, existe una estrategia óptima determinable para el ajedrez y otros juegos similares.

En un sentido más débil, resolver el ajedrez puede referirse a demostrar cuál de los tres resultados posibles (las blancas ganan; las negras ganan; empate) es el resultado de dos jugadores perfectos, sin revelar necesariamente la estrategia óptima en sí misma (ver prueba por contradicción).^[1]

No se conoce una solución completa para el ajedrez en ninguno de los dos sentidos, ni se espera que el ajedrez se resuelva en un futuro próximo. Existe un desacuerdo sobre si el actual crecimiento exponencial de la potencia informática continuará el tiempo suficiente para permitir algún día resolverlo por "fuerza bruta", es decir, comprobando todas las posibilidades.

Resultados parciales

Una posición de mate en 546 jugadas que se encuentra en la base de Lomonosov con finales de 7 piezas. Juegan blancas. (En este ejemplo, se agrega una octava pieza con una captura trivial de primera jugada).

Las tablas de finales han resuelto el ajedrez en un grado limitado, lo que determina el juego perfecto en una serie de finales, incluidos todos los finales no triviales con no más de siete piezas o peones (incluidos los dos reyes).^[2]

Una consecuencia del desarrollo de la base de la mesa de finales de 7 piezas es que se han encontrado muchos finales teóricos interesantes de ajedrez. Un ejemplo es una posición de "mate en 546", que con un juego perfecto es un jaque mate forzado en 546 movimientos, ignorando la regla de los 50 movimientos.^[3] Tal posición está más allá de la capacidad de resolución de cualquier humano, y ningún motor de ajedrez la juega correctamente sin acceso a la base de finales.

Predicciones sobre cuándo/si se resolverá el ajedrez

El teórico de la información Claude Shannon argumentó en 1951 que no es factible que ninguna computadora realmente resuelva el ajedrez, ya que necesitaría comparar unas 10¹²⁰ jugadas posibles o tener un "diccionario" que denota un movimiento óptimo para cada una de las 10⁴³ posiciones posibles en el tablero.^[4] Por tanto, es teóricamente posible resolver el ajedrez, pero el marco de tiempo requerido (según Shannon, 10⁹⁰ años) pone esta posibilidad más allá de los límites de cualquier tecnología factible.

Sin embargo, el número de operaciones matemáticas necesarias para resolver el ajedrez puede ser significativamente diferente del número de operaciones necesarias para producir el árbol de juego completo del ajedrez. En particular, si las blancas tienen una victoria forzada, solo un subconjunto del árbol de juego requeriría una evaluación para confirmar que existe una victoria forzada (es decir, sin refutaciones de las negras). Además, el cálculo de Shannon para la complejidad del ajedrez asume una duración promedio del juego de 40 movimientos, pero no hay una base matemática para decir que una victoria forzada por cualquiera de los lados tendría alguna relación con la duración del juego. De hecho, algunos juegos jugados por expertos (juego de nivel de gran maestro) han sido tan cortos como 16 movimientos. Por estas razones, los matemáticos y teóricos de los juegos se han mostrado reacios a afirmar categóricamente que resolver el ajedrez es un problema insoluble.^[4]^[5]

Hans-Joachim Bremermann, profesor de matemáticas y biofísica de la Universidad de California en Berkeley, argumentó además en un artículo de 1965 que "la velocidad, la memoria y la capacidad de procesamiento de cualquier posible equipo informático futuro están limitadas por barreras físicas específicas: la barrera de la velocidad de la luz, la barrera cuántica y la barrera termodinámica. Estas limitaciones implican, por ejemplo, que ninguna computadora, cualquiera que sea su construcción, podrá examinar el árbol completo de posibles secuencias de movimientos del juego de ajedrez ". No obstante, Bremermann no descartó la posibilidad de que una computadora algún día pudiera resolver el ajedrez. Escribió: "Para que una computadora juegue un juego perfecto o casi perfecto, será necesario analizar el juego por completo ... o analizar el juego de una manera aproximada y combinar esto con una cantidad limitada de búsqueda de árboles. ... Sin embargo, todavía falta una comprensión teórica de dicha programación heurística."^[6]

Los avances científicos recientes no han cambiado significativamente estas evaluaciones. El juego de damas se resolvió (débilmente) en 2007,^[7] pero tiene aproximadamente la raíz cuadrada del número de posiciones en el ajedrez. Jonathan Schaeffer, el científico que dirigió el esfuerzo, dijo que se necesitaría un avance como la computación cuántica antes de que se pudiera intentar resolver el ajedrez, pero no descarta la posibilidad, diciendo que lo único que aprendió de su esfuerzo de 16 años de resolver damas "es nunca subestimar los avances tecnológicos".^[8]

Variantes de ajedrez

Se han resuelto algunas variantes de ajedrez que son más sencillas que el ajedrez. Una estrategia ganadora para las negras en Maharajah y los cipayos se puede memorizar fácilmente. La variante 5 × 5 del miniajedrez de Gardner se ha resuelto débilmente como un empate.^[9] Aunque el ajedrez pierde-gana se juega en un tablero de 8x8, su regla de captura forzada limita en gran medida su complejidad y un análisis computacional logró resolver débilmente esta variante como una victoria para las blancas.^[10]

La perspectiva de resolver juegos individuales, específicos, similares al ajedrez se vuelve más difícil a medida que aumenta el tamaño del tablero, como en variantes de ajedrez con tablero grande, y el ajedrez infinito.^[11]

Véase también

Referencias

↑ Allis, V. (1994). «PhD thesis: Searching for Solutions in Games and Artificial Intelligence». Department of Computer Science. University of Limburg. Archivado desde el original el 22 de noviembre de 2020. Consultado el 14 de julio de 2012.
↑ «Lomonosov Tablebases». Consultado el 24 de abril de 2013.
↑ "Who wins from this puzzle?" A mate-in-546 chess position, with discussion (Post 1: Position, Post 7: Playable).
↑ ^a ^b Shannon, C. (March 1950). «Programming a Computer for Playing Chess». Philosophical Magazine. 7 41 (314). Archivado desde el original el 15 de marzo de 2010. Consultado el 27 de junio de 2008.

"Con el ajedrez es posible, en principio, jugar un juego perfecto o construir una máquina para hacerlo de la siguiente manera: se consideran en una posición dada todos los movimientos posibles, luego todos los movimientos del oponente, etc., hasta el final de la juego (en cada variación). El final debe ocurrir, según las reglas de los juegos después de un número finito de movimientos (recordando la regla de dibujo de 50 movimientos). Cada una de estas variaciones termina en victoria, pérdida o empate. Trabajando hacia atrás desde el final, uno puede determinar si hay una victoria forzada, la posición es un empate o se pierde. Sin embargo, es fácil de demostrar que incluso con la alta velocidad de cálculo disponible en las calculadoras electrónicas, este cálculo no es práctico. En las posiciones típicas de ajedrez habrá del orden de 30 jugadas legales. El número se mantiene bastante constante hasta que el juego está casi terminado, como lo muestra De Groot, quien promedió el número de movimientos legales en una gran cantidad de juegos maestros. Por lo tanto, un movimiento para las blancas y luego uno para las negras da aproximadamente 10³ posibilidades. Un juego típico dura alrededor de 40 movimientos hasta la renuncia de una de las partes. Esto es conservador para nuestro cálculo, ya que la máquina calcularía el jaque mate, no la resignación. Sin embargo, incluso en esta cifra, habrá 10¹²⁰ variaciones que se calcularán desde la posición inicial. ¡Una máquina que funciona a razón de una variación por microsegundo necesitaría más de 10⁹⁰ años para calcular el primer movimiento!"
↑ http://www.chessgames.com Magnus Carlsen vs Viswanathlan Anand, King's Indian Attack: Double Fianchetto (A07), 1/2-1/2, 16 moves.
↑ Bremermann, H.J. (1965). «Quantum Noise and Information». Proc. 5th Berkeley Symp. Math. Statistics and Probability. Archivado desde el original el 27 de mayo de 2001.
↑ Schaeffer, Jonathan; Burch, Neil; Björnsson, Yngvi et al. (14 de septiembre de 2007). «Checkers Is Solved». Science 317 (5844): 1518-1522. PMID 17641166. doi:10.1126/science.1144079. (requiere suscripción)
↑ Sreedhar, Suhas. «Checkers, Solved!». Spectrum.ieee.org. Archivado desde el original el 25 de marzo de 2009. Consultado el 21 de marzo de 2009.
↑ Mhalla, Mehdi; Prost, Frederic (2013-07-26). «Gardner's Minichess Variant is solved». arXiv:1307.7118 [cs.GT].
↑ Watkins, Mark. «Losing Chess: 1. e3 wins for White».
↑ Aviezri Fraenkel; D. Lichtenstein (1981), «Computing a perfect strategy for n×n chess requires time exponential in n», J. Combin. Theory Ser. A 31 (2): 199-214, doi:10.1016/0097-3165(81)90016-9 .

Enlaces externos

"Infinite Chess, PBS Infinite Series"

Datos: Q7559040

[1] Allis, V. (1994). «PhD thesis: Searching for Solutions in Games and Artificial Intelligence». Department of Computer Science. University of Limburg. Archivado desde el original el 22 de noviembre de 2020. Consultado el 14 de julio de 2012.

[Lomonosov_Tablebases-2] «Lomonosov Tablebases». Consultado el 24 de abril de 2013.

[3] "Who wins from this puzzle?" A mate-in-546 chess position, with discussion (Post 1: Position, Post 7: Playable).

[CSpaper-4] Shannon, C. (March 1950). «Programming a Computer for Playing Chess». Philosophical Magazine. 7 41 (314). Archivado desde el original el 15 de marzo de 2010. Consultado el 27 de junio de 2008.

"Con el ajedrez es posible, en principio, jugar un juego perfecto o construir una máquina para hacerlo de la siguiente manera: se consideran en una posición dada todos los movimientos posibles, luego todos los movimientos del oponente, etc., hasta el final de la juego (en cada variación). El final debe ocurrir, según las reglas de los juegos después de un número finito de movimientos (recordando la regla de dibujo de 50 movimientos). Cada una de estas variaciones termina en victoria, pérdida o empate. Trabajando hacia atrás desde el final, uno puede determinar si hay una victoria forzada, la posición es un empate o se pierde. Sin embargo, es fácil de demostrar que incluso con la alta velocidad de cálculo disponible en las calculadoras electrónicas, este cálculo no es práctico. En las posiciones típicas de ajedrez habrá del orden de 30 jugadas legales. El número se mantiene bastante constante hasta que el juego está casi terminado, como lo muestra De Groot, quien promedió el número de movimientos legales en una gran cantidad de juegos maestros. Por lo tanto, un movimiento para las blancas y luego uno para las negras da aproximadamente 10³ posibilidades. Un juego típico dura alrededor de 40 movimientos hasta la renuncia de una de las partes. Esto es conservador para nuestro cálculo, ya que la máquina calcularía el jaque mate, no la resignación. Sin embargo, incluso en esta cifra, habrá 10¹²⁰ variaciones que se calcularán desde la posición inicial. ¡Una máquina que funciona a razón de una variación por microsegundo necesitaría más de 10⁹⁰ años para calcular el primer movimiento!"

[5] ttp://www.chessgames.com Magnus Carlsen vs Viswanathlan Anand, King's Indian Attack: Double Fianchetto (A07), 1/2-1/2, 16 moves.

[6] Bremermann, H.J. (1965). «Quantum Noise and Information». Proc. 5th Berkeley Symp. Math. Statistics and Probability. Archivado desde el original el 27 de mayo de 2001.

[7] Schaeffer, Jonathan; Burch, Neil; Björnsson, Yngvi et al. (14 de septiembre de 2007). «Checkers Is Solved». Science 317 (5844): 1518-1522. PMID 17641166. doi:10.1126/science.1144079. (requiere suscripción)

[8] Sreedhar, Suhas. «Checkers, Solved!». Spectrum.ieee.org. Archivado desde el original el 25 de marzo de 2009. Consultado el 21 de marzo de 2009.

[9] Mhalla, Mehdi; Prost, Frederic (2013-07-26). «Gardner's Minichess Variant is solved». arXiv:1307.7118 [cs.GT].

[10] Watkins, Mark. «Losing Chess: 1. e3 wins for White».

[11] Aviezri Fraenkel; D. Lichtenstein (1981), «Computing a perfect strategy for n×n chess requires time exponential in n», J. Combin. Theory Ser. A 31 (2): 199-214, doi:10.1016/0097-3165(81)90016-9 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]