El ajedrez informático incluye tanto hardware (ordenadores dedicados) como software capaz de jugar al ajedrez . El ajedrez por computadora brinda oportunidades para que los jugadores practiquen incluso en ausencia de oponentes humanos, y también brinda oportunidades de análisis, entretenimiento y entrenamiento. Las aplicaciones de ajedrez por computadora que juegan al nivel de un gran maestro de ajedrez o superior están disponibles en hardware desde supercomputadoras hasta teléfonos inteligentes . También hay disponibles máquinas de ajedrez independientes. Stockfish , Leela Chess Zero , GNU Chess , Fruit y otras aplicaciones gratuitas de código abierto están disponibles para varias plataformas.
Las aplicaciones de ajedrez por computadora, ya sea implementadas en hardware o software, utilizan estrategias diferentes a las de los humanos para elegir sus movimientos: utilizan métodos heurísticos para construir, buscar y evaluar árboles que representan secuencias de movimientos desde la posición actual e intentan ejecutar la mejor secuencia durante el juego. . Estos árboles suelen ser bastante grandes, de miles a millones de nodos. La velocidad computacional de las computadoras modernas, capaces de procesar decenas de miles a cientos de miles de nodos o más por segundo, junto con las heurísticas de extensión y reducción que reducen el árbol a los nodos más relevantes, hacen que este enfoque sea efectivo.
Las primeras máquinas de ajedrez capaces de jugar ajedrez o juegos reducidos similares al ajedrez fueron programas de software que se ejecutaban en computadoras digitales a principios de la era de las computadoras de tubos de vacío (década de 1950). Los primeros programas funcionaban tan mal que incluso un principiante podía derrotarlos. Al cabo de 40 años, en 1997, los motores de ajedrez que se ejecutaban en supercomputadoras o hardware especializado eran capaces de derrotar incluso a los mejores jugadores humanos . En 2006, los programas que se ejecutaban en PC de escritorio habían alcanzado la misma capacidad. En 2006, Monty Newborn , profesor de Ciencias de la Computación en la Universidad McGill , declaró: "la ciencia ya está hecha". Sin embargo, actualmente no es posible resolver ajedrez en los ordenadores modernos debido a la enorme cantidad de variaciones posibles del juego . [1]
El ajedrez por ordenador alguna vez fue considerado la " Drosophila de la IA", la vanguardia de la ingeniería del conocimiento . Este campo se considera ahora un paradigma científicamente completo y jugar al ajedrez es una actividad informática mundana. [2]
Las máquinas/programas de ajedrez están disponibles en varias formas diferentes: máquinas de ajedrez independientes (normalmente un microprocesador que ejecuta un programa de ajedrez, pero a veces como una máquina de hardware especializada), programas de software que se ejecutan en PC estándar, sitios web y aplicaciones para dispositivos móviles. . Los programas se ejecutan en todo, desde supercomputadoras hasta teléfonos inteligentes. Los requisitos de hardware para los programas son mínimos; las aplicaciones no ocupan más de unos pocos megabytes en el disco, usan unos pocos megabytes de memoria (pero pueden usar mucha más, si está disponible) y cualquier procesador de 300 Mhz o más rápido es suficiente. El rendimiento variará modestamente con la velocidad del procesador, pero suficiente memoria para contener una tabla de transposición grande (hasta varios gigabytes o más) es más importante para la potencia del juego que la velocidad del procesador.
La mayoría de los programas y máquinas de ajedrez comerciales disponibles pueden jugar con la potencia de un súper gran maestro (Elo 2700 o más) y aprovechar las arquitecturas de CPU de computadora multinúcleo e hiperproceso. Los mejores programas como Stockfish han superado incluso a jugadores de calibre mundial. La mayoría de los programas de ajedrez comprenden un motor de ajedrez conectado a una GUI, como Winboard o Chessbase . La fuerza de ejecución, los controles de tiempo y otras configuraciones relacionadas con el rendimiento se pueden ajustar desde la GUI. La mayoría de las GUI también permiten al jugador configurar y editar posiciones, revertir movimientos, ofrecer y aceptar empates (y renunciar), solicitar y recibir recomendaciones de movimientos y mostrar el análisis del motor a medida que avanza el juego.
Hay miles de motores de ajedrez como Sargon , IPPOLIT , Stockfish , Crafty , Fruit , Leela Chess Zero y GNU Chess que se pueden descargar (u obtener el código fuente de otro modo) de Internet de forma gratuita.
Quizás el tipo más común de software de ajedrez sean los programas que simplemente juegan al ajedrez. Un jugador humano hace un movimiento en el tablero, la IA calcula y realiza un movimiento posterior, y el humano y la IA alternan turnos hasta que termina el juego. El motor de ajedrez , que calcula los movimientos, y la interfaz gráfica de usuario (GUI) son a veces programas separados. Se pueden conectar diferentes motores a la GUI, lo que permite jugar contra diferentes estilos de oponentes. Los motores suelen tener una interfaz de línea de comandos de texto simple , mientras que las GUI pueden ofrecer una variedad de conjuntos de piezas, estilos de tablero o incluso piezas animadas o en 3D. Debido a que los motores recientes son tan capaces, los motores o GUI pueden ofrecer alguna forma de perjudicar la capacidad del motor, para mejorar las probabilidades de que gane el jugador humano. Los motores Universal Chess Interface (UCI), como Fritz o Rybka, pueden tener un mecanismo incorporado para reducir la calificación Elo del motor (a través de los parámetros uci_limitstrength y uci_elo de UCI). Algunas versiones de Fritz tienen un modo Handicap y Fun para limitar el motor actual o cambiar el porcentaje de errores que comete o cambiar su estilo. Fritz también tiene un modo amigo en el que durante el juego intenta igualar el nivel del jugador.
Las bases de datos de ajedrez permiten a los usuarios buscar en una gran biblioteca de partidas históricas, analizarlas, comprobar estadísticas y formular un repertorio de aperturas. Chessbase (para PC) es un programa común para estos fines entre los jugadores profesionales, pero existen alternativas como Shane's Chess Information Database (Scid) [3] para Windows, Mac o Linux, Chess Assistant [4] para PC, [5] Chess PGN Master de Gerhard Kalab para Android [6] o Chess-Studio de Giordano Vicoli para iOS. [7]
Programas como Playchess permiten a los jugadores jugar entre sí a través de Internet.
Los programas de entrenamiento en ajedrez enseñan ajedrez. Chessmaster contó con tutoriales de juego del IM Josh Waitzkin y del GM Larry Christiansen . Stefan Meyer-Kahlen ofrece Shredder Chess Tutor basado en los libros de texto de Step de Rob Brunia y Cor Van Wijgerden. La compañía Play Magnus del ex campeón mundial Magnus Carlsen lanzó una aplicación Magnus Trainer para Android e iOS. Chessbase tiene Fritz y Chesster para niños. Convekta ofrece una gran cantidad de aplicaciones de entrenamiento como CT-ART y su línea Chess King basadas en tutoriales del GM Alexander Kalinin y Maxim Blokh.
También existe software para manejar problemas de ajedrez .
Después de descubrir la detección de refutación (la aplicación de la poda alfa-beta para optimizar la evaluación de movimientos) en 1957, un equipo de la Universidad Carnegie Mellon predijo que una computadora derrotaría al campeón mundial humano en 1967. [8] No anticipó la dificultad de determinar el orden correcto para evaluar los movimientos. Los investigadores trabajaron para mejorar la capacidad de los programas para identificar heurísticas asesinas , movimientos inusualmente de alta puntuación para reexaminar al evaluar otras ramas, pero en la década de 1970 la mayoría de los mejores jugadores de ajedrez creían que las computadoras no pronto serían capaces de jugar a un nivel Maestro . [9] En 1968, el maestro internacional David Levy hizo una famosa apuesta a que ninguna computadora de ajedrez podría vencerlo en diez años, [10] y en 1976, el maestro principal y profesor de psicología Eliot Hearst de la Universidad de Indiana escribió que "el único La forma en que un programa de computadora actual podría ganar un solo juego contra un jugador maestro sería que el maestro, tal vez en un estupor de borrachera mientras juega 50 juegos simultáneamente, cometiera algún error garrafal una vez al año". [9]
A finales de la década de 1970, los programas de ajedrez comenzaron repentinamente a derrotar a jugadores humanos altamente capacitados. [9] El año de la declaración de Hearst, el ajedrez 4.5 de la Universidad Northwestern en el nivel Clase B del Campeonato Americano de Ajedrez Paul Masson se convirtió en el primero en ganar un torneo humano. Levy ganó su apuesta en 1978 al vencer a Chess 4.7 , pero logró la primera victoria informática contra un jugador Master-class a nivel de torneo al ganar una de las seis partidas. [10] En 1980, Belle comenzó a derrotar a menudo a Masters. En 1982, dos programas se ejecutaban a nivel de Máster y tres eran ligeramente más débiles. [9]
La mejora repentina sin un avance teórico fue inesperada, ya que muchos no esperaban que la capacidad de Belle para examinar 100.000 posiciones por segundo (unas ocho capas) fuera suficiente. Los Spracklen, creadores del exitoso programa de microcomputadora Sargon , estimaron que el 90% de la mejora provino de una velocidad de evaluación más rápida y sólo el 10% de evaluaciones mejoradas. New Scientist afirmó en 1982 que las computadoras "juegan un ajedrez terrible ... torpe, ineficiente, difuso y simplemente feo", pero los humanos perdieron ante ellas al cometer "horribles errores, errores sorprendentes, descuidos incomprensibles, errores de cálculo graves y cosas por el estilo". mucho más a menudo de lo que pensaban; "En resumen, los ordenadores ganan principalmente gracias a su capacidad para encontrar y explotar errores de cálculo en las iniciativas humanas". [9]
En 1982, los programas de ajedrez de microcomputadoras podían evaluar hasta 1.500 movimientos por segundo y eran tan potentes como los programas de ajedrez de mainframe de cinco años antes, capaces de derrotar a la mayoría de los jugadores aficionados. Si bien solo pudieron mirar hacia adelante una o dos jugadas más que en su debut a mediados de la década de 1970, al hacerlo mejoraron su juego más de lo que esperaban los expertos; Mejoras aparentemente menores "parecen haber permitido cruzar un umbral psicológico, después del cual se vuelve accesible una rica cosecha de errores humanos", escribió New Scientist . [9] Mientras revisaba SPOC en 1984, BYTE escribió que "las computadoras (mainframes, minis y micros) tienden a jugar un ajedrez feo y poco elegante", pero destacó la afirmación de Robert Byrne de que "tácticamente están más libres de errores que el ser humano promedio". jugador". La revista describió a SPOC como un "programa de ajedrez de última generación" para IBM PC con un nivel de juego "sorprendentemente alto" y estimó su calificación USCF en 1700 (Clase B). [11]
En el Campeonato Norteamericano de Ajedrez por Computadora de 1982 , Monroe Newborn predijo que un programa de ajedrez podría convertirse en campeón mundial dentro de cinco años; el director del torneo y maestro internacional Michael Valvo predijo diez años; los Spracklen predijeron 15; Ken Thompson predijo más de 20; y otros predijeron que eso nunca sucedería. La opinión más extendida, sin embargo, afirmaba que ocurriría alrededor del año 2000. [12] En 1989, Levy fue derrotado por Deep Thought en un combate de exhibición. Deep Thought, sin embargo, todavía estaba considerablemente por debajo del nivel del Campeonato Mundial, como lo demostró el actual campeón mundial, Garry Kasparov , en dos sólidas victorias en 1989. No fue hasta un partido de 1996 con Deep Blue de IBM que Kasparov perdió su primera partida ante una computadora. en los controles de tiempo del torneo en Deep Blue contra Kasparov, 1996, partida 1 . De hecho, este juego fue la primera vez que un actual campeón del mundo perdió contra una computadora usando controles de tiempo regulares. Sin embargo, Kasparov se reagrupó para ganar tres y empatar dos de las cinco partidas restantes del partido, para una victoria convincente.
En mayo de 1997, una versión actualizada de Deep Blue derrotó a Kasparov por 3½-2½ en un partido de vuelta. En 2003 se realizó un documental principalmente sobre el enfrentamiento, titulado Game Over: Kasparov and the Machine .
Con una potencia de procesamiento cada vez mayor y funciones de evaluación mejoradas, los programas de ajedrez que se ejecutan en estaciones de trabajo disponibles comercialmente comenzaron a rivalizar con los jugadores de primer nivel. En 1998, Rebel 10 derrotó a Viswanathan Anand , que en ese momento ocupaba el segundo lugar en el mundo, por una puntuación de 5 a 3. Sin embargo, la mayoría de esos juegos no se jugaron en los controles de tiempo normales. De las ocho partidas, cuatro fueron partidas relámpago (cinco minutos más cinco segundos de retraso de Fischer por cada movimiento); Estos rebeldes ganaron 3-1. Dos fueron partidas de semi-relámpago (quince minutos para cada lado) que Rebel también ganó (1½–½). Finalmente, se jugaron dos partidas como partidas de torneo regulares (cuarenta jugadas en dos horas, una hora de muerte súbita); aquí fue Anand quien ganó ½–1½. [13] En los juegos rápidos, las computadoras jugaban mejor que los humanos, pero en los controles de tiempo clásicos, en los que se determina la calificación de un jugador, la ventaja no era tan clara.
A principios de la década de 2000, programas disponibles comercialmente como Junior y Fritz pudieron empatar contra el ex campeón mundial Garry Kasparov y el campeón mundial clásico Vladimir Kramnik .
En octubre de 2002, Vladimir Kramnik y Deep Fritz compitieron en el partido Brains in Bahrain de ocho partidas , que terminó en empate. Kramnik ganó las partidas 2 y 3 mediante tácticas anticomputadoras "convencionales" : juegue de manera conservadora para obtener una ventaja a largo plazo que la computadora no puede ver en su búsqueda en el árbol de juegos . Fritz, sin embargo, ganó la quinta partida tras un grave error de Kramnik. La sexta partida fue calificada por los comentaristas del torneo como "espectacular". Kramnik, en una mejor posición al inicio del medio juego , intentó sacrificar una pieza para lograr un fuerte ataque táctico, una estrategia conocida por ser altamente riesgosa contra computadoras que están en su mejor momento defendiendo contra tales ataques. Fiel a su forma, Fritz encontró una defensa hermética y el ataque de Kramnik se agotó dejándolo en una mala posición. Kramnik abandonó la partida creyendo que la posición estaba perdida. Sin embargo, el análisis humano y por computadora posterior al juego ha demostrado que era poco probable que el programa de Fritz hubiera podido forzar una victoria y Kramnik efectivamente sacrificó una posición empatada. Los dos últimos juegos fueron empates. Dadas las circunstancias, la mayoría de los comentaristas todavía consideran a Kramnik como el jugador más fuerte del partido. [ cita necesaria ]
En enero de 2003, Kasparov jugó contra Junior , otro programa informático de ajedrez, en la ciudad de Nueva York. El partido terminó 3-3.
En noviembre de 2003, Kasparov jugó contra X3D Fritz . El partido terminó 2-2.
En 2005, Hydra , una computadora de ajedrez dedicada con hardware personalizado y sesenta y cuatro procesadores y también ganadora del 14º IPCCC en 2005, derrotó al séptimo clasificado Michael Adams por 5½–½ en un partido de seis partidas (aunque la preparación de Adams fue mucho menor). más completo que el de Kramnik para la serie de 2002). [14]
En noviembre-diciembre de 2006, el campeón mundial Vladimir Kramnik se enfrentó a Deep Fritz. Esta vez ganó la computadora; el partido terminó 2-4. Kramnik pudo ver el libro de aperturas del ordenador. En las primeras cinco partidas, Kramnik condujo la partida hacia una típica contienda posicional "anticomputadora". Perdió una partida ( pasando por alto un mate en una ) y empató las siguientes cuatro. En la última partida, en un intento de empatar el partido, Kramnik jugó la Defensa Siciliana más agresiva y fue aplastado.
Se especuló que el interés en la competencia de ajedrez entre humanos y computadoras caería en picado como resultado del partido Kramnik-Deep Fritz de 2006. [15] Según Newborn, por ejemplo, "la ciencia está hecha". [16]
Las partidas de ajedrez entre humanos y computadoras mostraron que los mejores sistemas informáticos superaban a los campeones de ajedrez humanos a finales de los años 1990. Durante los 40 años anteriores a eso, la tendencia había sido que las mejores máquinas ganaran alrededor de 40 puntos por año en la calificación Elo, mientras que los mejores humanos sólo ganaban aproximadamente 2 puntos por año. [17] La calificación más alta obtenida por una computadora en una competencia humana fue la calificación USCF de Deep Thought de 2551 en 1988 y la FIDE ya no acepta resultados entre humanos y computadoras en sus listas de calificación. Se han creado grupos Elo especializados solo para máquinas para calificar máquinas, pero esos números, aunque similares en apariencia, no se comparan directamente. [18] En 2016, la Asociación Sueca de Informática de Ajedrez calificó el programa informático Komodo con 3361.
Los motores de ajedrez siguen mejorando. En 2009, los motores de ajedrez que funcionan con hardware más lento alcanzaron el nivel de gran maestro . Un teléfono móvil ganó un torneo de categoría 6 con una calificación de rendimiento de 2898: el motor de ajedrez Hiarcs 13 ejecutándose dentro de Pocket Fritz 4 en el teléfono móvil HTC Touch HD ganó la Copa Mercosur en Buenos Aires , Argentina, con 9 victorias y 1 empate el 4 de agosto. 14, 2009. [19] Pocket Fritz 4 busca menos de 20.000 posiciones por segundo. [20] Esto contrasta con supercomputadoras como Deep Blue, que buscaban 200 millones de posiciones por segundo.
El ajedrez avanzado es una forma de ajedrez desarrollada en 1998 por Kasparov en la que un humano juega contra otro humano y ambos tienen acceso a computadoras para mejorar su fuerza. Kasparov argumentó que el jugador "avanzado" resultante era más fuerte que un humano o una computadora por sí solo. Esto se ha demostrado en numerosas ocasiones, como en eventos de Freestyle Chess.
Los jugadores de hoy tienden a tratar los motores de ajedrez como herramientas de análisis más que como oponentes. [21] El gran maestro de ajedrez Andrew Soltis declaró en 2016: "Las computadoras son demasiado buenas" y que el campeón mundial Magnus Carlsen no jugará ajedrez por computadora porque "simplemente pierde todo el tiempo y no hay nada más deprimente que perder sin siquiera estar en el juego." [22]
Desde la era de las máquinas mecánicas que jugaban finales de torres y reyes y de las máquinas eléctricas que jugaban a otros juegos como el hexágono en los primeros años del siglo XX, los científicos y teóricos han buscado desarrollar una representación procedimental de cómo los humanos aprenden, recuerdan, piensan y aplican. conocimiento, y el juego de ajedrez, debido a su enorme complejidad, se convirtió en la " Drosophila de la inteligencia artificial (IA)". [Nota 1] La resolución procedimental de la complejidad se convirtió en sinónimo de pensamiento, y las primeras computadoras, incluso antes de la era de los autómatas del ajedrez, fueron denominadas popularmente "cerebros electrónicos". A partir de la segunda mitad del siglo XX se idearon varios esquemas diferentes para representar el conocimiento y el pensamiento, aplicados al juego de ajedrez (y otros juegos como las damas):
Utilizando heurísticas de "fines y medios", un jugador de ajedrez humano puede determinar intuitivamente resultados óptimos y cómo lograrlos independientemente del número de movimientos necesarios, pero una computadora debe ser sistemática en su análisis. La mayoría de los jugadores están de acuerdo en que para jugar bien es necesario mirar al menos cinco movimientos por delante (diez capas ) cuando sea necesario. Las reglas normales de los torneos dan a cada jugador un promedio de tres minutos por jugada. En promedio, hay más de 30 movimientos legales por posición de ajedrez, por lo que una computadora debe examinar mil billones de posibilidades para anticipar diez jugadas (cinco movimientos completos); uno que pudiera examinar un millón de posiciones por segundo requeriría más de 30 años. [9]
Los primeros intentos de representaciones procedimentales del juego de ajedrez son anteriores a la era electrónica digital, pero fue la computadora digital con programas almacenados la que dio margen para calcular tal complejidad. Claude Shannon, en 1949, estableció los principios de la solución algorítmica del ajedrez. En ese documento, el juego está representado por un "árbol", o estructura de datos digitales de opciones (ramas) correspondientes a movimientos. Los nodos del árbol eran posiciones en el tablero resultantes de las elecciones de movimiento. La imposibilidad de representar una partida completa de ajedrez construyendo un árbol desde el primer movimiento hasta el último se hizo evidente de inmediato: hay un promedio de 36 movimientos por posición en el ajedrez y una partida promedio dura alrededor de 35 movimientos hasta la resignación (60-80 movimientos si se juega). jaque mate, punto muerto u otro empate). Hay 400 posiciones posibles después del primer movimiento de cada jugador, unas 200.000 después de dos movimientos cada uno y casi 120 millones después de sólo 3 movimientos cada uno.
Por lo tanto, se propuso una anticipación limitada (búsqueda) hasta cierta profundidad, seguida del uso de conocimientos específicos del dominio para evaluar las posiciones terminales resultantes. Se obtendría una especie de posición intermedia, dadas las buenas jugadas de ambos lados, y su evaluación informaría al jugador sobre la bondad o maldad de las jugadas elegidas. Las operaciones de búsqueda y comparación en el árbol se adaptaban bien al cálculo por computadora; la representación de conocimientos sutiles de ajedrez en la función de evaluación no lo era. Los primeros programas de ajedrez sufrieron en ambas áreas: buscar en el vasto árbol requería recursos computacionales mucho más allá de los disponibles, y se necesitarían décadas para descubrir qué conocimiento de ajedrez era útil y cómo codificarlo.
Los desarrolladores de un sistema informático para jugar al ajedrez deben decidir sobre una serie de cuestiones fundamentales de implementación. Estos incluyen:
Adriaan de Groot entrevistó a varios ajedrecistas de distintos niveles y concluyó que tanto los maestros como los principiantes analizan entre cuarenta y cincuenta posiciones antes de decidir qué movimiento jugar. Lo que hace que los primeros sean mucho mejores jugadores es que utilizan habilidades de reconocimiento de patrones construidas a partir de la experiencia. Esto les permite examinar algunas líneas con mucha mayor profundidad que otras simplemente sin considerar movimientos que puedan suponer que son malos. Una prueba más de que esto es así es el hecho de que a los buenos jugadores humanos les resulta mucho más fácil recordar posiciones de partidas de ajedrez genuinas, dividiéndolas en un pequeño número de subposiciones reconocibles, en lugar de en disposiciones completamente aleatorias de las mismas piezas. Por el contrario, los jugadores pobres tienen el mismo nivel de recuerdo para ambos.
El equivalente de esto en el ajedrez por computadora son las funciones de evaluación para la evaluación de hojas, que corresponden a las habilidades de reconocimiento de patrones de los jugadores humanos, y el uso de técnicas de aprendizaje automático para entrenarlos, como el ajuste Texel, el descenso de gradiente estocástico y el aprendizaje por refuerzo , que Corresponde a la construcción de experiencia en jugadores humanos. Esto permite a los programas modernos examinar algunas líneas con mucha mayor profundidad que otras mediante el uso de poda directa y otras heurísticas selectivas para simplemente no considerar movimientos que el programa supone como deficientes a través de su función de evaluación, de la misma manera que lo hacen los jugadores humanos. La única diferencia fundamental entre un programa de computadora y un humano en este sentido es que un programa de computadora puede buscar mucho más profundamente que un jugador humano, lo que le permite buscar más nodos y evitar el efecto horizonte en una medida mucho mayor de lo que es posible con un humano. jugadores.
Los programas de ajedrez informáticos suelen admitir una serie de estándares comunes de facto . Casi todos los programas actuales pueden leer y escribir movimientos de juego como notación de juego portátil (PGN) y pueden leer y escribir posiciones individuales como notación Forsyth-Edwards (FEN). Los programas de ajedrez más antiguos a menudo sólo entendían la notación algebraica larga , pero hoy en día los usuarios esperan que los programas de ajedrez comprendan la notación algebraica estándar .
A partir de finales de la década de 1990, los programadores comenzaron a desarrollar motores separados (con una interfaz de línea de comandos que calcula qué movimientos son más fuertes en una posición) o una interfaz gráfica de usuario (GUI) que proporciona al jugador un tablero de ajedrez que puede ver y piezas. que se puede mover. Los motores comunican sus movimientos a la GUI mediante un protocolo como el Protocolo de comunicación del motor de ajedrez (CECP) o la Interfaz universal de ajedrez (UCI). Al dividir los programas de ajedrez en estas dos partes, los desarrolladores pueden escribir sólo la interfaz de usuario, o sólo el motor, sin necesidad de escribir ambas partes del programa. (Ver también motor de ajedrez ).
Los desarrolladores tienen que decidir si conectar el motor a un libro de aperturas y/o bases de datos de finales o dejar esto en manos de la GUI.
La estructura de datos utilizada para representar cada posición de ajedrez es clave para el desempeño de la generación de movimientos y la evaluación de posiciones . Los métodos incluyen piezas almacenadas en una matriz ("buzón" y "0x88"), posiciones de piezas almacenadas en una lista ("lista de piezas"), colecciones de conjuntos de bits para ubicaciones de piezas (" bitboards ") y posiciones codificadas por Huffman para compactos. almacenamiento a largo plazo.
Los programas de ajedrez informáticos consideran las jugadas de ajedrez como un árbol de juego . En teoría, examinan todos los movimientos, luego todos los contraataques a esos movimientos, luego todos los movimientos que los contrarrestan, y así sucesivamente, donde cada movimiento individual de un jugador se denomina " ply ". Esta evaluación continúa hasta una cierta profundidad de búsqueda máxima o el programa determina que se ha alcanzado una posición final de "hoja" (por ejemplo, jaque mate).
Un tipo particular de algoritmo de búsqueda utilizado en el ajedrez por computadora son los algoritmos de búsqueda minimax , donde en cada jugada se selecciona el "mejor" movimiento del jugador; un jugador intenta maximizar la puntuación y el otro minimizarla. Mediante este proceso alternativo se llega a un determinado nodo terminal cuya evaluación representa el valor buscado de la posición. Su valor está respaldado hasta la raíz, y esa evaluación se convierte en la valoración de la posición en el tablero. Este proceso de búsqueda se llama minimax.
Una implementación ingenua del algoritmo minimax sólo puede buscar a una pequeña profundidad en una cantidad de tiempo práctica, por lo que se han ideado varios métodos para acelerar enormemente la búsqueda de buenos movimientos. La poda alfa-beta , un sistema para definir límites superiores e inferiores en posibles resultados de búsqueda y buscar hasta que los límites coincidan, se utiliza normalmente para reducir el espacio de búsqueda del programa.
Además, también se utilizan varias heurísticas de búsqueda selectiva, como la búsqueda de inactividad , la poda directa, las extensiones de búsqueda y las reducciones de búsqueda. Estas heurísticas se activan en función de ciertas condiciones en un intento de eliminar movimientos obviamente malos (movimientos históricos) o para investigar nodos interesantes (por ejemplo, verificar extensiones, peones pasados en séptima fila , etc.). Sin embargo, estas heurísticas de búsqueda selectiva deben utilizarse con mucho cuidado. Si se extiende demasiado, el programa pierde demasiado tiempo buscando posiciones poco interesantes. Si se poda o reduce demasiado, existe el riesgo de eliminar nudos interesantes.
La búsqueda de árbol de Monte Carlo (MCTS) es un algoritmo de búsqueda heurístico que expande el árbol de búsqueda basándose en un muestreo aleatorio del espacio de búsqueda. Una versión de la búsqueda de árboles de Monte Carlo comúnmente utilizada en el ajedrez por computadora es PUCT, Predictor y límites de confianza superiores aplicados a los árboles.
AlphaZero y Leela Chess Zero de DeepMind usan MCTS en lugar de minimax. Dichos motores utilizan procesamiento por lotes en unidades de procesamiento de gráficos para calcular sus funciones y políticas de evaluación (selección de movimiento) y, por lo tanto, requieren un algoritmo de búsqueda paralelo ya que los cálculos en la GPU son inherentemente paralelos. Los algoritmos de poda minimax y alfa-beta utilizados en el ajedrez informático son inherentemente algoritmos en serie, por lo que no funcionarían bien con el procesamiento por lotes en la GPU. Por otro lado, MCTS es una buena alternativa, porque el muestreo aleatorio utilizado en la búsqueda de árbol de Monte Carlo se presta bien a la computación paralela, y es por eso que casi todos los motores que admiten cálculos en la GPU usan MCTS en lugar de alfa-beta.
Se pueden utilizar muchas otras optimizaciones para fortalecer los programas de ajedrez. Por ejemplo, las tablas de transposición se utilizan para registrar posiciones que han sido evaluadas previamente, para ahorrar recálculos de las mismas. Las tablas de refutación registran movimientos clave que "refutan" lo que parece ser un buen movimiento; Por lo general, estos se intentan primero en posiciones variantes (ya que un movimiento que refuta una posición probablemente refute otra). El inconveniente es que las tablas de transposición en capas profundas pueden llegar a ser bastante grandes: decenas a cientos de millones de entradas. La tabla de transposición Deep Blue de IBM en 1996, por ejemplo, ascendía a 500 millones de entradas. Las tablas de transposición que son demasiado pequeñas pueden hacer que se dedique más tiempo a buscar entradas inexistentes debido a la trilla que el tiempo ahorrado por las entradas encontradas. Muchos motores de ajedrez utilizan el pensamiento , buscando niveles más profundos en el tiempo del oponente, similar a los seres humanos, para aumentar su fuerza de juego.
Por supuesto, un hardware más rápido y memoria adicional pueden mejorar la potencia de juego del programa de ajedrez. Las arquitecturas Hyperthreaded pueden mejorar modestamente el rendimiento si el programa se ejecuta en un solo núcleo o en una pequeña cantidad de núcleos. La mayoría de los programas modernos están diseñados para aprovechar múltiples núcleos para realizar búsquedas paralelas. Otros programas están diseñados para ejecutarse en una computadora de uso general y asignar generación de movimientos, búsqueda paralela o evaluación a procesadores dedicados o coprocesadores especializados.
El primer artículo sobre búsqueda fue escrito por Claude Shannon en 1950. [23] Predijo las dos principales estrategias de búsqueda posibles que se utilizarían, a las que denominó "Tipo A" y "Tipo B", [24] antes de que alguien programara una computadora. para jugar al ajedrez.
Los programas de tipo A utilizarían un enfoque de " fuerza bruta ", examinando cada posición posible para un número fijo de movimientos utilizando un algoritmo minimax puro e ingenuo . Shannon creía que esto no sería práctico por dos razones.
Primero, con aproximadamente treinta movimientos posibles en una posición típica de la vida real, esperaba que buscar las aproximadamente 10 9 posiciones involucradas en mirar tres movimientos hacia adelante para ambos lados (seis capas ) tomaría alrededor de dieciséis minutos, incluso en la posición "muy optimista". caso de que la computadora de ajedrez evaluara un millón de posiciones cada segundo. (Se necesitaron unos cuarenta años para alcanzar esta velocidad. Un algoritmo de búsqueda posterior llamado poda alfa-beta , un sistema para definir límites superiores e inferiores en posibles resultados de búsqueda y buscar hasta que los límites coincidieran, redujo el factor de ramificación del árbol del juego de forma logarítmica. pero todavía no era factible para los programas de ajedrez de la época explotar la explosión exponencial del árbol.
En segundo lugar, ignoró el problema de la inactividad, tratando de evaluar únicamente una posición que se encuentra al final de un intercambio de piezas u otra secuencia importante de movimientos ("líneas"). Esperaba que la adaptación del minimax para hacer frente a esto aumentaría considerablemente el número de posiciones que debían examinarse y ralentizaría aún más el programa. Esperaba que la adaptación del tipo A para hacer frente a esta situación aumentaría considerablemente el número de posiciones que debían examinarse y ralentizaría aún más el programa.
Esto condujo naturalmente a lo que se conoce como "búsqueda selectiva" o "búsqueda tipo B", utilizando el conocimiento del ajedrez (heurística) para seleccionar algunos movimientos presumiblemente buenos de cada posición para buscar, y eliminar los demás sin buscar. En lugar de desperdiciar poder de procesamiento examinando movimientos malos o triviales, Shannon sugirió que los programas de tipo B utilizarían dos mejoras:
Esto les permitiría mirar más adelante ("más profundamente") las líneas más significativas en un tiempo razonable. Sin embargo, los primeros intentos de búsqueda selectiva a menudo resultaron en la eliminación del mejor movimiento o movimientos. Como resultado, se logró poco o ningún progreso durante los siguientes 25 años dominados por esta primera iteración del paradigma de búsqueda selectiva. El mejor programa producido en este primer período fue Mac Hack VI en 1967; jugaba aproximadamente al mismo nivel que el aficionado promedio (clase C en la escala de calificación de la Federación de Ajedrez de los Estados Unidos).
Mientras tanto, el hardware siguió mejorando y, en 1974, se implementó por primera vez la búsqueda de fuerza bruta en el programa Chess 4.0 de la Universidad Northwestern. En este enfoque, se buscan todos los movimientos alternativos en un nodo y no se elimina ninguno. Descubrieron que el tiempo requerido para simplemente buscar todos los movimientos era mucho menor que el tiempo requerido para aplicar heurísticas intensivas en conocimiento para seleccionar solo algunos de ellos, y el beneficio de no eliminar prematuramente o inadvertidamente buenos movimientos resultó en un rendimiento sustancialmente mejor. .
En las décadas de 1980 y 1990, finalmente se lograron avances en el paradigma de búsqueda selectiva, con el desarrollo de la búsqueda de inactividad , la poda de movimientos nulos y otras heurísticas de búsqueda selectiva modernas. Estas heurísticas tenían muchos menos errores que las heurísticas anteriores y se descubrió que valía la pena el tiempo adicional que ahorraban porque podían realizar búsquedas más profundas y ser ampliamente adoptadas por muchos motores. Si bien muchos programas modernos utilizan la búsqueda alfa-beta como sustrato para su algoritmo de búsqueda, estas heurísticas de búsqueda selectivas adicionales utilizadas en los programas modernos significan que el programa ya no realiza una búsqueda de "fuerza bruta". En lugar de eso, dependen en gran medida de estas heurísticas de búsqueda selectiva para extender las líneas que el programa considera buenas y podar y reducir las líneas que el programa considera malas, hasta el punto en que la mayoría de los nodos en el árbol de búsqueda se eliminan, lo que permite a los programas modernos realizar búsquedas muy profundas.
En 2006, Rémi Coulom creó la búsqueda de árbol de Monte Carlo , otro tipo de búsqueda selectiva de tipo B. En 2007, Levente Kocsis y Csaba Szepesvári crearon una adaptación de la búsqueda de árboles de Monte Carlo llamada límites de confianza superiores aplicados a árboles o UCT para abreviar. En 2011, Chris Rosin desarrolló una variación de UCT llamada Predictor + límites de confianza superiores aplicados a árboles, o PUCT para abreviar. Luego, PUCT se utilizó en AlphaZero en 2017 y luego en Leela Chess Zero en 2018.
En la década de 1970, la mayoría de los programas de ajedrez se ejecutaban en supercomputadoras como Control Data Cyber 176 o Cray-1, lo que indica que durante ese período de desarrollo del ajedrez informático, la potencia de procesamiento era el factor limitante en el rendimiento. La mayoría de los programas de ajedrez tuvieron dificultades para buscar a una profundidad superior a las 3 capas. No fue hasta las máquinas de ajedrez de hardware de la década de 1980 que se hizo evidente una relación entre la velocidad del procesador y el conocimiento codificado en la función de evaluación.
Se ha estimado que al duplicar la velocidad de la computadora se obtienen aproximadamente entre cincuenta y setenta puntos Elo en fuerza de juego (Levy y Newborn 1991:192).
Para la mayoría de las posiciones de ajedrez, las computadoras no pueden anticipar todas las posiciones finales posibles. En cambio, deben mirar hacia adelante algunas capas y comparar las posibles posiciones, conocidas como hojas. El algoritmo que evalúa las hojas se denomina "función de evaluación" y estos algoritmos suelen ser muy diferentes entre diferentes programas de ajedrez. Las funciones de evaluación suelen evaluar posiciones en centésimas de peón (llamado centipeón), donde por convención, una evaluación positiva favorece a las blancas y una evaluación negativa favorece a las negras. Sin embargo, algunas funciones de evaluación generan porcentajes de victorias/empates/pérdidas en lugar de centipeones.
Históricamente, las funciones de evaluación artesanales consideran el valor material junto con otros factores que afectan la resistencia de cada lado. Al contar el material para cada lado, los valores típicos para las piezas son 1 punto por un peón , 3 puntos por un caballo o alfil , 5 puntos por una torre y 9 puntos por una reina . (Ver Valor relativo de la pieza de ajedrez .) A veces se le da al rey un valor arbitrariamente alto, como 200 puntos ( artículo de Shannon ) para garantizar que un jaque mate supere todos los demás factores (Levy y Newborn 1991:45). Además de los puntos por piezas, la mayoría de las funciones de evaluación artesanales tienen en cuenta muchos factores, como la estructura de peones, el hecho de que un par de alfiles suelen valer más, las piezas centralizadas valen más, etc. Se suele considerar la protección de los reyes, así como la fase del juego (apertura, mitad o final). Las técnicas de aprendizaje automático , como el giro de Texel, el descenso de gradiente estocástico o el aprendizaje por refuerzo, se suelen utilizar para optimizar las funciones de evaluación artesanales.
La mayoría de las funciones de evaluación modernas utilizan redes neuronales . La función de evaluación más común que se utiliza hoy en día es la red neuronal actualizable de manera eficiente , que es una red neuronal poco profunda cuyas entradas son tablas de piezas cuadradas . Las tablas de piezas cuadradas son un conjunto de 64 valores correspondientes a las casillas del tablero de ajedrez, y normalmente existe una tabla de piezas cuadradas para cada pieza y color, lo que da como resultado 12 tablas de piezas cuadradas y, por lo tanto, 768 entradas a la red neuronal. Además, algunos motores utilizan redes neuronales profundas en su función de evaluación. Las redes neuronales suelen entrenarse utilizando algún algoritmo de aprendizaje por refuerzo , en conjunto con el aprendizaje supervisado o el aprendizaje no supervisado .
La salida de la función de evaluación es un escalar único, cuantificado en centipeones u otras unidades, que es, en el caso de funciones de evaluación hechas a mano, una suma ponderada de los diversos factores descritos, o en el caso de funciones de evaluación basadas en redes neuronales, el salida del jefe de la red neuronal. La evaluación supuestamente representa o se aproxima al valor del subárbol debajo del nodo evaluado como si se hubiera buscado hasta la terminación, es decir, el final del juego. Durante la búsqueda, se compara una evaluación con evaluaciones de otras hojas, eliminando nodos que representan malos o malos movimientos para cualquiera de los lados, para producir un nodo que, por convergencia, representa el valor de la posición con mejor juego por ambos lados.
El juego de finales había sido durante mucho tiempo una de las grandes debilidades de los programas de ajedrez debido a la profundidad de la búsqueda necesaria. Algunos programas de nivel maestro no pudieron ganar en posiciones donde incluso los jugadores humanos intermedios podían forzar una victoria.
Para solucionar este problema, se han utilizado ordenadores para analizar algunas posiciones de finales de ajedrez de forma completa, empezando por rey y peón contra rey. Estas tablas de finales se generan de antemano utilizando una forma de análisis retrógrado , comenzando con posiciones donde se conoce el resultado final (por ejemplo, donde un lado ha sido mate) y viendo qué otras posiciones están a un movimiento de distancia de ellas, y luego cuáles están a un movimiento. de aquellos, etc. Ken Thompson fue un pionero en esta área.
Los resultados del análisis informático a veces sorprendieron a la gente. En 1977, la máquina de ajedrez Belle de Thompson utilizó la base de la tabla de finales para un rey y una torre contra rey y reina y fue capaz de empatar ese final teóricamente perdido contra varios maestros (ver Posición de Philidor#Reina contra torre ). Esto fue a pesar de no seguir la estrategia habitual de retrasar la derrota manteniendo al rey y la torre defensores juntos el mayor tiempo posible. Cuando se le pidió que explicara las razones detrás de algunos de los movimientos del programa, Thompson no pudo hacerlo más allá de decir que la base de datos del programa simplemente arrojó los mejores movimientos.
La mayoría de los grandes maestros se negaron a jugar contra la computadora en el final de dama contra torre, pero Walter Browne aceptó el desafío. Se creó una posición de reina contra torre en la que la dama puede ganar en treinta movimientos, con un juego perfecto. A Browne se le permitieron dos horas y media para jugar cincuenta movimientos; de lo contrario, se reclamaría un empate según la regla de los cincuenta movimientos . Después de cuarenta y cinco movimientos, Browne acordó empatar, al no poder forzar el jaque mate ni ganar la torre en los siguientes cinco movimientos. En la posición final, Browne todavía estaba a diecisiete movimientos del jaque mate, pero no tan lejos de ganar la torre. Browne estudió el final y volvió a jugar con la computadora una semana después en una posición diferente en la que la dama puede ganar en treinta movimientos. Esta vez, capturó la torre en el movimiento quincuagésimo, dándole una posición ganadora (Levy & Newborn 1991:144-48), (Nunn 2002:49).
Otras posiciones, que durante mucho tiempo se creyeron ganadas, resultaron requerir más movimientos contra el juego perfecto para ganar realmente de lo que permitía la regla de los cincuenta movimientos del ajedrez. Como consecuencia, durante algunos años las reglas oficiales del ajedrez de la FIDE fueron modificadas para ampliar el número de movimientos permitidos en estos finales. Después de un tiempo, la regla volvió a cincuenta movimientos en todas las posiciones; se descubrieron más posiciones de este tipo, lo que complicó aún más la regla, y no hizo ninguna diferencia en el juego humano, ya que no podían jugar las posiciones a la perfección.
A lo largo de los años, se han lanzado otros formatos de bases de datos de finales , incluidos Edward Tablebase, De Koning Database y Nalimov Tablebase, que es utilizado por muchos programas de ajedrez como Rybka , Shredder y Fritz . Hay disponibles bases de mesa para todas las posiciones con seis piezas. [25] Marc Bourzutschky y Yakov Konoval han analizado algunos finales de siete piezas. [26] Los programadores que utilizan las supercomputadoras Lomonosov en Moscú han completado una tabla de ajedrez para todos los finales con siete piezas o menos (se excluyen las posiciones triviales de finales, como seis piezas blancas versus un rey negro solitario ). [27] [28] En todas estas bases de datos de finales se supone que el enroque ya no es posible.
Muchas bases de datos no consideran la regla de los cincuenta movimientos, según la cual un juego en el que transcurren cincuenta movimientos sin una captura o un movimiento de peón puede considerarse un empate para cualquiera de los jugadores. Esto da como resultado que la base de tablas arroje resultados como "mate forzado en sesenta y seis movimientos" en algunas posiciones que en realidad serían empatadas debido a la regla de los cincuenta movimientos. Una razón para esto es que si las reglas del ajedrez se cambiaran una vez más, dando más tiempo para ganar dichas posiciones, no será necesario regenerar todas las tablas. También es muy fácil para el programa que utiliza las tablas notar y tener en cuenta esta "característica" y, en cualquier caso, si utiliza una tabla de finales, elegirá el movimiento que conduzca a la victoria más rápida (incluso si no alcanzara los cincuenta -regla de movimiento con juego perfecto). Si juegas contra un oponente que no utiliza una base de datos, esa elección te dará buenas posibilidades de ganar en cincuenta movimientos.
Las bases de datos Nalimov, que utilizan técnicas de compresión de última generación , requieren 7,05 GB de espacio en el disco duro para todas las terminaciones de cinco piezas. Para cubrir todas las terminaciones de seis piezas se requieren aproximadamente 1,2 TB . Se estima que una base de datos de siete piezas requiere entre 50 y 200 TB de espacio de almacenamiento. [29]
Las bases de datos de finales ocuparon un lugar destacado en 1999, cuando Kasparov jugó un partido de exhibición en Internet contra el resto del mundo . Se llegó a un final de reina y peón de siete piezas con el Equipo Mundial luchando por salvar el empate. Eugene Nalimov ayudó generando la base de la tabla final de seis piezas donde ambos lados tenían dos Reinas, que fue utilizada en gran medida para ayudar al análisis por ambos lados.
La base de tablas de finales más popular es syzygy, que es utilizada por la mayoría de los principales programas informáticos como Stockfish , Leela Chess Zero y Komodo . También es significativamente más pequeño que otros formatos, con bases de datos de 7 piezas que ocupan solo 18,4 TB. [30]
Para un motor de ajedrez de última generación como Stockfish, una base de mesa solo proporciona un aumento muy pequeño en la fuerza del juego (aproximadamente 3 puntos Elo para syzygy 6men a partir de Stockfish 15). [31]
Los motores de ajedrez, al igual que los seres humanos, pueden ahorrar tiempo de procesamiento y seleccionar variaciones potentes tal como las exponen los maestros, haciendo referencia a un libro de aperturas almacenado en una base de datos en disco. Los libros de apertura cubren los primeros movimientos de un juego con una profundidad variable, dependiendo de la apertura y la variación, pero generalmente hasta los primeros 10 a 12 movimientos (20 a 24 capas). Dado que los maestros han estudiado en profundidad las aperturas durante siglos, y algunas se conocen hasta bien avanzado el medio juego, las valoraciones de variaciones específicas por parte de los maestros generalmente serán superiores a la heurística general del programa.
Si bien en un momento, realizar un movimiento fuera de los libros para poner el programa de ajedrez en sus propios recursos podría haber sido una estrategia efectiva porque los libros de aperturas de ajedrez eran selectivos para el estilo de juego del programa, y los programas tenían debilidades notables en relación con los humanos. , eso ya no es cierto hoy. [ ¿cuando? ] Los libros de aperturas almacenados en las bases de datos de las computadoras probablemente sean mucho más extensos que incluso los de los humanos mejor preparados, y realizar una jugada temprana fuera del libro puede resultar en que la computadora encuentre la jugada inusual en su libro y cargue al oponente con un golpe fuerte. desventaja. Incluso si no es así, jugar fuera de libro puede ser mucho mejor para programas de ajedrez tácticamente agudos que para humanos que tienen que descubrir movimientos fuertes en una variación desconocida sobre el tablero.
En los torneos con motores modernos, los libros de aperturas se utilizan para obligar a los motores a jugar aperturas intencionalmente desequilibradas para reducir la tasa de empate y agregar más variedad a los juegos. [32]
CEGT , [33] CSS, [34] SSDF , [35] WBEC, [36] REBEL , [37] FGRL, [38] e IPON [39] mantienen listas de clasificación que permiten a los aficionados comparar la potencia de los motores. Varias versiones de Stockfish , Komodo , Leela Chess Zero y Fat Fritz dominan las listas de clasificación a principios de la década de 2020.
CCRL (Computer Chess Rating Lists) es una organización que prueba la potencia de los motores de ajedrez informáticos jugando los programas entre sí. CCRL se fundó en 2006 para promover la competencia entre computadoras y tabular los resultados en una lista de clasificación. [40]
La organización cuenta con tres listas diferentes: 40/40 (40 minutos por cada 40 jugadas realizadas), 40/4 (4 minutos por cada 40 jugadas realizadas) y 40/4 FRC (mismo control de tiempo pero Chess960). [Nota 2] La reflexión (o cerebro permanente ) se apaga y la sincronización se ajusta a la CPU AMD64 X2 4600+ (2,4 GHz) utilizando Crafty 19.17 BH como punto de referencia. Se utilizan libros de aperturas genéricos y neutrales (a diferencia del propio libro del motor) hasta un límite de 12 movimientos en el juego junto con tablas de 4 o 5 jugadores . [40] [41] [42]
La idea de crear una máquina para jugar al ajedrez se remonta al siglo XVIII. Alrededor de 1769, el autómata de ajedrez llamado El Turco , creado por el inventor húngaro Farkas Kempelen , se hizo famoso antes de ser expuesto como un engaño. Antes del desarrollo de la informática digital , las pruebas serias basadas en autómatas como El Ajedrecista de 1912, construido por el ingeniero español Leonardo Torres Quevedo , que jugaba un final de rey y torre contra rey, eran demasiado complejas y limitadas para ser útiles para jugar partidas completas de ajedrez. El campo de la investigación del ajedrez mecánico languideció hasta la llegada de la computadora digital en la década de 1950.
Desde entonces, los entusiastas del ajedrez y los ingenieros informáticos han construido, cada vez con mayor seriedad y éxito, máquinas para jugar al ajedrez y programas informáticos. Uno de los pocos grandes maestros de ajedrez que se dedicó seriamente al ajedrez informático fue el ex campeón mundial de ajedrez Mikhail Botvinnik , quien escribió varios trabajos sobre el tema. El interés de Botvinnik por el ajedrez informático comenzó en los años 50, favoreciendo los algoritmos de ajedrez basados en la estrategia selectiva tipo B de Shannon, como se analizó junto con Max Euwe en 1958 en la televisión holandesa. Trabajando con hardware relativamente primitivo disponible en la Unión Soviética a principios de la década de 1960, Botvinnik no tuvo más remedio que investigar técnicas de selección de movimientos por software; En aquella época, sólo los ordenadores más potentes podían lograr mucho más que una búsqueda de tres capas en todo el ancho, y Botvinnik no tenía tales máquinas. En 1965, Botvinnik fue consultor del equipo ITEP en una partida de ajedrez por computadora entre Estados Unidos y la Unión Soviética que ganó una partida de ajedrez por correspondencia contra el programa Kotok-McCarthy dirigido por John McCarthy en 1967 (ver Kotok-McCarthy ). Posteriormente asesoró al equipo que creó el programa de ajedrez Kaissa en el Instituto de Ciencias de Control de Moscú. Botvinnik tenía sus propias ideas para modelar la mente de un maestro de ajedrez. Después de publicar y discutir sus primeras ideas sobre mapas y trayectorias de ataque en el Club Central de Ajedrez de Moscú en 1966, encontró en Vladimir Butenko su apoyo y colaborador. Butenko implementó por primera vez la representación del tablero de ataques vectoriales de 15x15 en una computadora M-20, determinando trayectorias. Después de que Botvinnik introdujera el concepto de Zonas en 1970, Butenko rechazó una mayor cooperación y comenzó a escribir su propio programa, denominado Eureka. En los años 70 y 80, liderando un equipo formado por Boris Stilman, Alexander Yudin, Alexander Reznitskiy, Michael Tsfasman y Mikhail Chudakov, Botvinnik trabajó en su propio proyecto "Pioneer", que era un proyecto de ajedrez basado en inteligencia artificial. En los años 90, Botvinnik, ya de 80 años, trabajó en el nuevo proyecto 'CC Sapiens'.
Un hito en el desarrollo se produjo cuando el equipo de la Universidad Northwestern , que fue responsable de la serie de programas de Ajedrez y ganó los primeros tres Campeonatos de Ajedrez por Computadora de la ACM (1970–72), abandonó la búsqueda tipo B en 1973. El programa resultante, Ajedrez 4.0, ganó. El campeonato de ese año y sus sucesores quedaron en segundo lugar tanto en el Campeonato ACM de 1974 como en el Campeonato Mundial de Ajedrez por Computadora inaugural de ese año , antes de ganar el Campeonato ACM nuevamente en 1975, 1976 y 1977. La implementación tipo A resultó ser igual de Rápido: en el tiempo que tomaba decidir qué movimientos eran dignos de ser buscados, era posible buscarlos todos. De hecho, Ajedrez 4.0 estableció el paradigma que fue y sigue siendo esencialmente seguido por todos los programas de ajedrez modernos hoy en día, y que fue iniciado con éxito por el ITEP ruso en 1965.
En 1978, una versión temprana de la máquina de ajedrez Belle de Ken Thompson , participó y ganó el Campeonato Norteamericano de Ajedrez por Computadora sobre el dominante Ajedrez 4.7 de la Universidad Northwestern.
Los avances tecnológicos de órdenes de magnitud en el poder de procesamiento han hecho que el enfoque de la fuerza bruta sea mucho más incisivo que en los primeros años. El resultado es que un jugador de IA táctico muy sólido, ayudado por un conocimiento posicional limitado incorporado por la función de evaluación y las reglas de poda/extensión, comenzó a igualar a los mejores jugadores del mundo. Resultó que se produjeron excelentes resultados, al menos en el campo del ajedrez, al permitir que las computadoras hicieran lo que mejor saben hacer (calcular) en lugar de obligarlas a imitar los procesos de pensamiento y conocimiento humanos. En 1997, Deep Blue , una máquina de fuerza bruta capaz de examinar 500 millones de nodos por segundo, derrotó al campeón mundial Garry Kasparov, siendo la primera vez que una computadora derrota a un campeón mundial de ajedrez reinante en control de tiempo estándar.
En 2016, NPR pidió a expertos que caracterizaran el estilo de juego de los motores de ajedrez informáticos. Murray Campbell de IBM afirmó que "las computadoras no tienen ningún sentido de la estética... Realizan lo que creen que es objetivamente el mejor movimiento en cualquier posición, incluso si parece absurdo, y pueden realizar cualquier movimiento sin importar cuán feo sea". es." Los grandes maestros Andrew Soltis y Susan Polgar afirmaron que es más probable que las computadoras retrocedan que los humanos. [22]
Si bien las redes neuronales se han utilizado en las funciones de evaluación de los motores de ajedrez desde finales de la década de 1980, con programas como NeuroChess, Morph, Blondie25, Giraffe, AlphaZero y MuZero , [43] [44] [45] [46] [47] Las redes neuronales no fueron ampliamente adoptadas por los motores de ajedrez hasta la llegada de redes neuronales actualizables de manera eficiente en el verano de 2020. Las redes neuronales actualizables de manera eficiente fueron desarrolladas originalmente en shogi informático en 2018 por Yu Nasu, [48] [49] y tenían que ser Se transfirió por primera vez a un derivado de Stockfish llamado Stockfish NNUE el 31 de mayo de 2020, [50] y se integró en el motor oficial de Stockfish el 6 de agosto de 2020, [51] [52] antes de que otros programadores de ajedrez comenzaran a adoptar redes neuronales en sus motores.
Algunas personas, como Venki Ramakrishnan de la Royal Society , creen que AlphaZero conducirá a la adopción generalizada de redes neuronales en los motores de ajedrez. [53] Sin embargo, AlphaZero influyó en muy pocos motores para que comenzaran a usar redes neuronales, y esos tendían a ser nuevos motores experimentales como Leela Chess Zero , que comenzó específicamente a replicar el artículo AlphaZero. Las redes neuronales profundas utilizadas en la función de evaluación de AlphaZero requerían costosas unidades de procesamiento de gráficos , que no eran compatibles con los motores de ajedrez existentes. La gran mayoría de los motores de ajedrez sólo utilizan unidades centrales de procesamiento , y la computación y el procesamiento de información en las GPU requieren bibliotecas especiales en el backend, como CUDA de Nvidia , a las que ninguno de los motores tenía acceso. Por lo tanto, la gran mayoría de los motores de ajedrez como Komodo y Stockfish continuaron usando funciones de evaluación artesanales hasta que en 2020 se trasladaron redes neuronales actualizables de manera eficiente al ajedrez por computadora, lo que no requirió en absoluto el uso de GPU ni bibliotecas como CUDA. Incluso entonces, las redes neuronales utilizadas en el ajedrez por ordenador son bastante superficiales, y los métodos de aprendizaje por refuerzo profundo iniciados por AlphaZero siguen siendo extremadamente raros en el ajedrez por ordenador.
Estos sistemas de juego de ajedrez incluyen hardware personalizado con aprox. fechas de introducción (excluidos los microordenadores dedicados):
Desde finales de la década de 1970 hasta principios de la de 1990, existía un mercado competitivo para las computadoras dedicadas al ajedrez. Este mercado cambió a mediados de la década de 1990, cuando las computadoras con procesadores dedicados ya no podían competir con los procesadores rápidos de las computadoras personales.
Recientemente, algunos aficionados han estado utilizando Multi Emulator Super System para ejecutar los programas de ajedrez creados para las computadoras Fidelity o Mephisto de Hegener & Glaser en sistemas operativos modernos de 64 bits como Windows 10 . [74] El autor de Rebel , Ed Schröder, también ha adaptado tres de los Hegener & Glaser Mephisto que escribió para que funcionen como motores UCI. [75]
Estos programas se pueden ejecutar en MS-DOS y en Windows 10 de 64 bits mediante emuladores como DOSBox o Qemu : [76]
Entre los teóricos del ajedrez informático más conocidos se incluyen:
Las perspectivas de resolver completamente el ajedrez generalmente se consideran bastante remotas. Se conjetura ampliamente que no existe ningún método computacionalmente barato para resolver ajedrez, ni siquiera en el sentido débil de determinar con certeza el valor de la posición inicial, y de ahí la idea de resolver ajedrez en el sentido más fuerte de obtener una descripción prácticamente utilizable de una estrategia para El juego perfecto para ambos lados parece poco realista hoy en día. Sin embargo, no se ha demostrado que no exista una forma computacionalmente barata de determinar el mejor movimiento en una posición de ajedrez, ni siquiera que un buscador alfa-beta tradicional ejecutado en el hardware informático actual no pueda resolver la posición inicial en una cantidad aceptable de tiempo. tiempo. La dificultad para demostrar esto último radica en el hecho de que, si bien el número de posiciones del tablero que pueden ocurrir en el transcurso de una partida de ajedrez es enorme (del orden de al menos 10 43 [78] a 10 47 ), es difícil descartar con certeza matemática la posibilidad de que la posición inicial permita a cualquiera de los lados forzar un mate o una repetición triple después de relativamente pocos movimientos, en cuyo caso el árbol de búsqueda podría abarcar sólo un subconjunto muy pequeño del conjunto de posiciones posibles. Se ha demostrado matemáticamente que el ajedrez generalizado (ajedrez jugado con un número arbitrariamente grande de piezas en un tablero arbitrariamente grande) es EXPTIME-completo , [79] lo que significa que determinar el bando ganador en una posición arbitraria del ajedrez generalizado probablemente toma un tiempo exponencial en el peor de los casos; sin embargo, este resultado teórico no ofrece un límite inferior a la cantidad de trabajo necesario para resolver ajedrez ordinario de 8x8.
El Minichess de Martin Gardner , jugado en un tablero de 5×5 con aproximadamente 10 18 posiciones posibles, ha sido resuelto; su valor en teoría de juegos es 1/2 (es decir, cualquiera de las partes puede forzar un empate), y se ha descrito la estrategia forzada para lograr ese resultado.
También se han logrado avances desde el otro lado: a partir de 2012, se han resuelto todos los finales de 7 piezas o menos (2 reyes y hasta 5 piezas más).
Un "motor de ajedrez" es un software que calcula y ordena qué movimientos son los más fuertes para jugar en una posición determinada. Los autores de motores se centran en mejorar el funcionamiento de sus motores, a menudo simplemente importando el motor a una interfaz gráfica de usuario (GUI) desarrollada por otra persona. Los motores se comunican con la GUI mediante protocolos estandarizados, como la omnipresente Universal Chess Interface desarrollada por Stefan Meyer-Kahlen y Franz Huber. Hay otros, como el protocolo de comunicación Chess Engine desarrollado por Tim Mann para GNU Chess y Winboard . Chessbase tiene su propio protocolo propietario y, en un momento, Millennium 2000 tenía otro protocolo utilizado para ChessGenius . Los motores diseñados para un sistema operativo y protocolo pueden trasladarse a otros sistemas operativos o protocolos.
Los motores de ajedrez se enfrentan regularmente entre sí en torneos dedicados a los motores de ajedrez .
En 1997, Internet Chess Club lanzó su primer cliente Java para jugar ajedrez en línea contra otras personas dentro del navegador web. [80] Esta fue probablemente una de las primeras aplicaciones web de ajedrez. Free Internet Chess Server siguió poco después con un cliente similar. [81] En 2004, la Federación Internacional de Ajedrez por Correspondencia abrió un servidor web para reemplazar su sistema basado en correo electrónico. [82] Chess.com comenzó a ofrecer Live Chess en 2007. [83] Chessbase / Playchess ha tenido durante mucho tiempo un cliente descargable y agregó un cliente basado en web en 2013. [84]
Otra aplicación web popular es la de entrenamiento táctico. El ahora desaparecido Chess Tactics Server abrió su sitio en 2006, [85] seguido por Chesstempo el año siguiente, [86] y Chess.com agregó su Tactics Trainer en 2008. [87] Chessbase agregó una aplicación web de entrenamiento de tácticas en 2015. [ 88]
Chessbase puso en línea su base de datos de juegos de ajedrez en 1998. [89] Otra de las primeras bases de datos de juegos de ajedrez fue Chess Lab, que comenzó en 1999. [90] New In Chess inicialmente había intentado competir con Chessbase lanzando un programa NICBase para Windows 3.x , pero finalmente decidió renunciar al software y centrarse en su base de datos en línea a partir de 2002. [91]
Se podía jugar contra el motor Shredder en línea desde 2006. [92] En 2015, Chessbase agregó una aplicación web de juego Fritz, [93] así como Mis juegos para almacenar las partidas. [94]
A partir de 2007, Chess.com ofreció el contenido del programa de formación Chess Mentor a sus clientes en línea. [95] Los principales gerentes generales como Sam Shankland y Walter Browne han aportado lecciones.
{{cite web}}
: Mantenimiento CS1: bot: estado de la URL original desconocido ( enlace ){{cite web}}
: Mantenimiento CS1: copia archivada como título ( enlace )Este artículo incorpora texto de Chess Programming Wiki disponible bajo la licencia CC BY-SA 3.0.