El ajedrez por computadora incluye tanto hardware (computadoras dedicadas) 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 para el análisis, el entretenimiento y el entrenamiento. Las aplicaciones de ajedrez por computadora que juegan al nivel de un gran maestro de ajedrez o superior están disponibles en hardware que va 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 para ordenador, 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 a partir de la posición actual e intentan ejecutar la mejor secuencia de ese tipo durante el juego. Estos árboles suelen ser bastante grandes, de miles a millones de nodos. La velocidad computacional de los ordenadores modernos, 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 eficaz.
Las primeras máquinas de ajedrez capaces de jugar al ajedrez o a juegos reducidos similares al ajedrez eran programas de software que se ejecutaban en computadoras digitales a principios de la era de las computadoras de tubo de vacío (década de 1950). Los primeros programas jugaban tan mal que incluso un principiante podía derrotarlos. En 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 está hecha". Sin embargo, resolver ajedrez no es posible actualmente para las computadoras modernas debido a la cantidad extremadamente grande de posibles variantes del juego . [1]
En su día, el ajedrez por ordenador se consideraba la « Drosophila de la IA», la vanguardia de la ingeniería del conocimiento . Hoy en día, se considera que este campo es un paradigma científicamente completo y jugar al ajedrez es una actividad informática mundana. [2]
Las máquinas y programas de ajedrez están disponibles en diferentes formas: máquinas de ajedrez independientes (normalmente un microprocesador que ejecuta un programa de ajedrez de software, 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, utilizan unos pocos megabytes de memoria (pero pueden utilizar 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 tener suficiente memoria para albergar una tabla de transposición grande (hasta varios gigabytes o más) es más importante para la fuerza de juego que la velocidad del procesador.
La mayoría de los programas y máquinas de ajedrez comerciales disponibles pueden jugar a un nivel de supergran maestro (Elo 2700 o superior) y aprovechar las arquitecturas de CPU de computadoras multinúcleo e hiperprocesadas. Los programas más destacados, como Stockfish, han superado incluso a jugadores de calibre campeón mundial. La mayoría de los programas de ajedrez incluyen un motor de ajedrez conectado a una interfaz gráfica de usuario, como Winboard o Chessbase . La fuerza de juego, los controles de tiempo y otros ajustes relacionados con el rendimiento se pueden ajustar desde la interfaz gráfica de usuario. La mayoría de las interfaces gráficas de usuario también permiten al jugador configurar y editar posiciones, revertir movimientos, ofrecer y aceptar tablas (y abandonar), solicitar y recibir recomendaciones de movimientos y mostrar el análisis del motor a medida que avanza la partida.
Hay miles de motores de ajedrez como Sargon , IPPOLIT , Stockfish , Crafty , Fruit , Leela Chess Zero y GNU Chess que pueden descargarse (o obtenerse el código fuente de otro modo) de Internet de forma gratuita.
Quizás el tipo más común de software de ajedrez son 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 se turnan hasta que termina la partida. El motor de ajedrez , que calcula los movimientos, y la interfaz gráfica de usuario (GUI) a veces son programas separados. Se pueden conectar diferentes motores a la GUI, lo que permite jugar contra diferentes estilos de oponentes. Los motores a menudo tienen 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 3D o animadas. Debido a que los motores recientes son tan capaces, los motores o las GUI pueden ofrecer alguna forma de limitar la capacidad del motor, para mejorar las probabilidades de una victoria del jugador humano. Los motores de Interfaz Universal de Ajedrez (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 Hándicap y un modo Diversión para limitar el motor actual o cambiar el porcentaje de errores que comete o cambiar su estilo. Fritz también tiene un Modo Amigo donde 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] Gerhard Kalab's Chess PGN Master para Android [6] o Giordano Vicoli's Chess-Studio para iOS. [7]
Programas como Playchess permiten a los jugadores jugar unos contra otros a través de Internet.
Los programas de entrenamiento de ajedrez enseñan ajedrez. Chessmaster tenía tutoriales de partidas del MI Josh Waitzkin y el GM Larry Christiansen . Stefan Meyer-Kahlen ofrece Shredder Chess Tutor basado en los libros de texto Step de Rob Brunia y Cor Van Wijgerden. La empresa 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 el cribado 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 con puntajes inusualmente altos para reexaminar al evaluar otras ramas, pero en la década de 1970 la mayoría de los mejores ajedrecistas creían que las computadoras pronto no podrían jugar a un nivel de Maestro . [9] En 1968, el maestro internacional David Levy hizo una famosa apuesta de que ninguna computadora de ajedrez sería capaz de vencerlo en diez años, [10] y en 1976 el maestro senior y profesor de psicología Eliot Hearst de la Universidad de Indiana escribió que "la única forma en que un programa de computadora actual podría ganar una sola partida contra un jugador maestro sería que el maestro, tal vez en un estupor de borrachera mientras juega 50 partidas simultáneamente, cometa algún error que ocurra una vez al año". [9]
A finales de los años 1970, los programas de ajedrez empezaron a derrotar a jugadores humanos muy habilidosos. [9] El año de la declaración de Hearst, el Chess 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 de una computadora contra un jugador de clase magistral en el nivel de torneo al ganar una de las seis partidas. [10] En 1980, Belle empezó a derrotar a menudo a los maestros. En 1982, dos programas jugaban en el nivel Maestro 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 microcomputadoras Sargon , estimaron que el 90% de la mejora se debía a una mayor velocidad de evaluación y sólo el 10% a evaluaciones mejoradas. New Scientist afirmó en 1982 que las computadoras "juegan un ajedrez terrible ... torpe, ineficiente, difuso y simplemente feo", pero los humanos perdían ante ellas al cometer "errores horribles, lapsus asombrosos, descuidos incomprensibles, errores de cálculo graves y similares" con mucha más frecuencia de lo que creían; "en resumen, las computadoras ganan principalmente por su capacidad de encontrar y explotar errores de cálculo en las iniciativas humanas". [9]
En 1982, los programas de ajedrez para microcomputadoras podían evaluar hasta 1.500 movimientos por segundo y eran tan potentes como los programas de ajedrez para mainframes de cinco años antes, capaces de derrotar a la mayoría de los jugadores aficionados. Aunque sólo podían mirar hacia delante una o dos jugadas más que en su debut a mediados de los años 1970, al hacerlo mejoraban 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 hace accesible una rica cosecha de errores humanos", escribió New Scientist . [9] Al revisar SPOC en 1984, BYTE escribió que "las computadoras (mainframes, minis y micros) tienden a jugar un ajedrez feo y poco elegante", pero tomó nota de la declaración de Robert Byrne de que "tácticamente están más libres de errores que el jugador humano promedio". 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 de Ajedrez Informático de Norteamérica de 1982 , Monroe Newborn predijo que un programa de ajedrez podría convertirse en campeón mundial en 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 nunca sucedería. La opinión más extendida, sin embargo, afirmó que ocurriría alrededor del año 2000. [12] En 1989, Levy fue derrotado por Deep Thought en un partido de exhibición. Deep Thought, sin embargo, todavía estaba considerablemente por debajo del nivel del Campeonato Mundial, como lo demostró el campeón mundial reinante, Garry Kasparov , en dos fuertes victorias en 1989. No fue hasta un partido de 1996 con Deep Blue de IBM que Kasparov perdió su primera partida contra una computadora en los controles de tiempo del torneo en Deep Blue versus Kasparov, 1996, juego 1. Esta partida fue, de hecho, la primera vez que un campeón mundial reinante perdió contra una computadora usando controles de tiempo regulares. Sin embargo, Kasparov se reagrupó para ganar tres y empatar dos de los cinco juegos 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 que trataba principalmente sobre el enfrentamiento, titulado Game Over: Kasparov and the Machine .
Con el aumento de la potencia de procesamiento y las funciones de evaluación mejoradas, los programas de ajedrez que se ejecutaban 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-3. Sin embargo, la mayoría de esas partidas no se jugaron con controles de tiempo normales. De las ocho partidas, cuatro fueron partidas blitz (cinco minutos más cinco segundos de retraso de Fischer para cada movimiento); Rebel ganó 3-1. Dos fueron partidas semi-blitz (quince minutos para cada lado) que Rebel también ganó (1½-½). Finalmente, dos partidas se jugaron como partidas de torneo regulares (cuarenta movimientos en dos horas, una hora de muerte súbita); aquí fue Anand quien ganó ½-1½. [13] En partidas rápidas, las computadoras jugaron 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 fue tan clara.
A principios de la década de 2000, programas disponibles comercialmente como Junior y Fritz pudieron empatar partidos 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 encuentro de ocho partidas Brains in Bahrain , que terminó en tablas. Kramnik ganó las partidas 2 y 3 con tácticas anti-computadoras "convencionales" (jugar de manera conservadora para obtener una ventaja a largo plazo que la computadora no puede ver en su búsqueda del árbol de partidas) . Sin embargo, Fritz ganó la partida 5 después de un grave error de Kramnik. La partida 6 fue descrita por los comentaristas del torneo como "espectacular". Kramnik, en una mejor posición en el medio juego temprano , intentó un sacrificio de pieza para lograr un fuerte ataque táctico, una estrategia que se sabe que es muy arriesgada contra las computadoras que se defienden mejor contra tales ataques. Fiel a su estilo, Fritz encontró una defensa hermética y el ataque de Kramnik se desvaneció dejándolo en una mala posición. Kramnik abandonó la partida, creyendo que la posición estaba perdida. Sin embargo, el análisis posterior de los partidos, realizado por humanos y por ordenador, ha demostrado que era poco probable que el programa Fritz hubiera podido forzar una victoria y Kramnik sacrificó efectivamente una posición de empate. Los dos últimos partidos terminaron en tablas. Dadas las circunstancias, la mayoría de los comentaristas siguen considerando a Kramnik como el jugador más fuerte del partido. [ cita requerida ]
En enero de 2003, Kasparov jugó contra Junior , otro programa informático de ajedrez, en la ciudad de Nueva York. La partida 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 5½–½ en un partido de seis juegos (aunque la preparación de Adams fue mucho menos exhaustiva que la de Kramnik para la serie de 2002). [14]
En noviembre-diciembre de 2006, el campeón mundial Vladimir Kramnik jugó contra Deep Fritz. Esta vez, la computadora ganó; la partida terminó 2-4. Kramnik pudo ver el libro de aperturas de la computadora. En las primeras cinco partidas, Kramnik llevó la partida a una típica competencia posicional "anti-computadora". Perdió una partida ( pasando por alto un mate en una ) y entabló las cuatro siguientes. En la última partida, en un intento de empatar la partida, 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 picada como resultado del encuentro Kramnik-Deep Fritz de 2006. [15] Según Newborn, por ejemplo, "la ciencia está hecha". [16]
A finales de los años 1990, las partidas de ajedrez entre humanos y ordenadores mostraron que los mejores sistemas informáticos superaban a los campeones humanos. Durante los 40 años anteriores, la tendencia había sido que las mejores máquinas ganaban unos 40 puntos al año en la clasificación Elo, mientras que los mejores humanos solo ganaban unos 2 puntos al año. [17] La calificación más alta obtenida por un ordenador en una competición entre humanos fue la calificación USCF de Deep Thought de 2551 en 1988 y la FIDE ya no acepta los resultados de ordenadores humanos en sus listas de clasificación. Se han creado grupos de clasificación Elo especializados solo para máquinas, pero esos números, aunque son similares en apariencia, no se comparan directamente. [18] En 2016, la Asociación Sueca de Computación de Ajedrez calificó al 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 han alcanzado 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 que se ejecuta dentro de Pocket Fritz 4 en el teléfono móvil HTC Touch HD ganó el torneo Copa Mercosur en Buenos Aires , Argentina con 9 victorias y 1 empate del 4 al 14 de agosto de 2009. [19] Pocket Fritz 4 busca menos de 20.000 posiciones por segundo. [20] Esto contrasta con supercomputadoras como Deep Blue que buscaron 200 millones de posiciones por segundo.
El ajedrez avanzado es una modalidad 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 afirmaba que el jugador "avanzado" resultante era más fuerte que un humano o una computadora por separado. Esto se ha demostrado en numerosas ocasiones, como en eventos de ajedrez de estilo libre.
En la actualidad, los jugadores tienden a tratar a los motores de ajedrez como herramientas de análisis en lugar de como oponentes. [21] El gran maestro de ajedrez Andrew Soltis declaró en 2016 que "las computadoras son demasiado buenas" y que el campeón mundial Magnus Carlsen no juega ajedrez con computadoras 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 torre y rey y las máquinas eléctricas que jugaban otros juegos como el hexadecimal 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 el conocimiento, y el juego de ajedrez, debido a su abrumadora 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 conocidas popularmente como "cerebros electrónicos". A partir de la segunda mitad del siglo XX se idearon varios esquemas diferentes para representar el conocimiento y el pensamiento, tal como se aplica al juego de ajedrez (y otros juegos como las damas):
Utilizando la heurística de "fines y medios", un jugador de ajedrez humano puede determinar intuitivamente los resultados óptimos y cómo alcanzarlos 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 mirar al menos cinco movimientos por delante (diez plies ) cuando es necesario es necesario para jugar bien. Las reglas normales de torneo dan a cada jugador un promedio de tres minutos por movimiento. En promedio, hay más de 30 movimientos legales por posición de ajedrez, por lo que una computadora debe examinar un cuatrillón de posibilidades para mirar hacia delante diez plies (cinco movimientos completos); una que pudiera examinar un millón de posiciones por segundo requeriría más de 30 años. [9]
Los primeros intentos de representación procedimental del juego de ajedrez fueron anteriores a la era electrónica digital, pero fue la computadora digital con programa almacenado la que dio alcance al cálculo de tal complejidad. Claude Shannon, en 1949, expuso los principios de la solución algorítmica del ajedrez. En ese artículo, el juego se representa mediante un "árbol", o estructura de datos digitales de opciones (ramas) correspondientes a los 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 fue inmediatamente evidente: hay un promedio de 36 movimientos por posición en ajedrez y una partida promedio dura alrededor de 35 movimientos hasta la rendición (60-80 movimientos si se juega a jaque mate, ahogado u otro tipo de tablas). Hay 400 posiciones posibles después del primer movimiento de cada jugador, alrededor de 200.000 después de dos movimientos cada uno y casi 120 millones después de solo 3 movimientos cada uno.
Por lo tanto, se propuso una búsqueda anticipada limitada con cierta profundidad, seguida por el uso de conocimiento específico del dominio para evaluar las posiciones terminales resultantes. Se obtendría una especie de posición intermedia, dadas las buenas jugadas de ambos bandos, 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 eran adecuadas para el cálculo informático; la representación del conocimiento sutil del ajedrez en la función de evaluación no lo era. Los primeros programas de ajedrez sufrieron en ambas áreas: la búsqueda 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 del 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, entre ellas:
Adriaan de Groot entrevistó a varios jugadores de ajedrez de distintos niveles y llegó a la conclusión de que tanto los maestros como los principiantes analizan entre cuarenta y cincuenta posiciones antes de decidir qué jugada realizar. Lo que hace que los primeros sean mucho mejores jugadores es que utilizan habilidades de reconocimiento de patrones adquiridas a partir de la experiencia. Esto les permite examinar algunas líneas con mucha mayor profundidad que otras simplemente sin tener en cuenta jugadas que pueden suponer que son malas. Otra prueba de que esto es así es la forma en que a los buenos jugadores humanos les resulta mucho más fácil recordar posiciones de partidas de ajedrez auténticas, dividiéndolas en un pequeño número de subposiciones reconocibles, en lugar de disposiciones completamente aleatorias de las mismas piezas. En cambio, los jugadores mediocres tienen el mismo nivel de memoria para ambas.
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 entrenarlas, como el ajuste de Texel, el descenso de gradiente estocástico y el aprendizaje de refuerzo , que corresponde a la construcción de experiencia en jugadores humanos. Esto permite que los programas modernos examinen algunas líneas con mucha mayor profundidad que otras mediante el uso de poda hacia adelante y otras heurísticas selectivas para simplemente no considerar movimientos que el programa asume como malos 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 del horizonte en una medida mucho mayor de lo que es posible con los jugadores humanos.
Los programas de ajedrez por computadora 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 solo entendían la notación algebraica larga , pero hoy los usuarios esperan que los programas de ajedrez entiendan la notación algebraica estándar de ajedrez .
A partir de finales de los años 90, los programadores comenzaron a desarrollar por separado motores (con una interfaz de línea de comandos que calcula qué movimientos son los 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 pueden mover. Los motores comunican sus movimientos a la GUI mediante un protocolo como el Protocolo de comunicación de motores de ajedrez (CECP) o la Interfaz universal de ajedrez (UCI). Al dividir los programas de ajedrez en estas dos partes, los desarrolladores pueden escribir solo la interfaz de usuario, o solo el motor, sin necesidad de escribir ambas partes del programa. (Véase también motor de ajedrez .)
Los desarrolladores tienen que decidir si conectar el motor a un libro de aperturas y/o tablas 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 rendimiento de la generación de movimientos y la evaluación de posiciones . Los métodos incluyen piezas almacenadas en una matriz ("mailbox" y "0x88"), posiciones de piezas almacenadas en una lista ("piece list"), colecciones de conjuntos de bits para ubicaciones de piezas (" bitboards ") y posiciones codificadas por Huffman para almacenamiento compacto a largo plazo.
Los programas de ajedrez por ordenador consideran las jugadas de ajedrez como un árbol de juego . En teoría, examinan todas las jugadas, luego todas las contrajugadas a esas jugadas, luego todas las jugadas que las contrarrestan, y así sucesivamente, donde cada jugada individual de un jugador se denomina " jugada ". Esta evaluación continúa hasta que se alcanza una determinada profundidad máxima de búsqueda 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 ordenador son los algoritmos de búsqueda minimax , en los que en cada jugada se selecciona la "mejor" jugada del jugador; un jugador intenta maximizar la puntuación, el otro, minimizarla. Mediante este proceso alterno, se llega a un nodo terminal particular cuya evaluación representa el valor buscado de la posición. Su valor se respalda en 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 denomina minimax.
Una implementación ingenua del algoritmo minimax solo puede buscar a una pequeña profundidad en un tiempo práctico, por lo que se han ideado varios métodos para acelerar en gran medida la búsqueda de buenos movimientos. La poda alfa-beta , un sistema que define límites superiores e inferiores en los posibles resultados de búsqueda y busca 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 quiescencia , la poda hacia adelante, 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, extensiones de jaque, peones pasados en la séptima fila , etc.). Sin embargo, estas heurísticas de búsqueda selectiva deben usarse con mucho cuidado. Si se extienden demasiado, el programa pierde demasiado tiempo mirando posiciones poco interesantes. Si se poda o reduce demasiado, existe el riesgo de eliminar nodos interesantes.
La búsqueda en árbol de Monte Carlo (MCTS) es un algoritmo de búsqueda heurística 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 en árbol de Monte Carlo que se usa comúnmente en ajedrez por computadora es PUCT, Predictor y límites de confianza superior aplicados a árboles.
AlphaZero y Leela Chess Zero de DeepMind utilizan MCTS en lugar de minimax. Estos motores utilizan el procesamiento por lotes en unidades de procesamiento gráfico para calcular sus funciones de evaluación y política (selección de movimientos) y, por lo tanto, requieren un algoritmo de búsqueda paralela , ya que los cálculos en la GPU son inherentemente paralelos. Los algoritmos de poda minimax y alfa-beta utilizados en el ajedrez por computadora son inherentemente algoritmos seriales, 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 árboles 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 utilizan MCTS en lugar de alfa-beta.
Se pueden utilizar muchas otras optimizaciones para hacer que los programas de ajedrez sean más fuertes. Por ejemplo, las tablas de transposición se utilizan para registrar posiciones que se han evaluado previamente, para ahorrar el recálculo de las mismas. Las tablas de refutación registran movimientos clave que "refutan" lo que parece ser un buen movimiento; estos se prueban normalmente primero en posiciones variantes (ya que un movimiento que refuta una posición es probable que refute otra). El inconveniente es que las tablas de transposición en profundidades de juego 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, tení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 al tiempo ahorrado por las entradas encontradas. Muchos motores de ajedrez utilizan la ponderación , buscando a niveles más profundos en el tiempo del oponente, de forma similar a los seres humanos, para aumentar su fuerza de juego.
Por supuesto, un hardware más rápido y una memoria adicional pueden mejorar la potencia de juego de un programa de ajedrez. Las arquitecturas con hiperprocesamiento pueden mejorar el rendimiento de forma modesta 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 propósito general y asignar la generación de movimientos, la búsqueda paralela o la evaluación a procesadores dedicados o coprocesadores especializados.
El primer artículo sobre búsqueda en ajedrez fue escrito por Claude Shannon en 1950. [23] Él predijo las dos principales estrategias de búsqueda posibles que se utilizarían, que denominó "Tipo A" y "Tipo B", [24] antes de que alguien hubiera programado una computadora para jugar al ajedrez.
Los programas de tipo A utilizarían un enfoque de " fuerza bruta ", examinando cada posición posible para una cantidad fija de movimientos utilizando un algoritmo minimax puro e ingenuo . Shannon creía que esto sería poco práctico por dos razones.
En primer lugar, con aproximadamente treinta movimientos posibles en una posición típica de la vida real, esperaba que la búsqueda de las aproximadamente 10 9 posiciones involucradas en mirar tres movimientos hacia adelante para ambos lados (seis plies ) tomaría alrededor de dieciséis minutos, incluso en el caso "muy optimista" de que la computadora de ajedrez evaluara un millón de posiciones cada segundo. (Tomó alrededor de cuarenta años lograr esta velocidad). Un algoritmo de búsqueda posterior llamado poda alfa-beta , un sistema de definición de límites superiores e inferiores en posibles resultados de búsqueda y búsqueda hasta que los límites coincidieran, redujo el factor de ramificación del árbol de juego logarítmicamente, pero todavía no era factible para los programas de ajedrez en ese momento explotar la explosión exponencial del árbol.
En segundo lugar, ignoró el problema de la quietud, intentando 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 adaptar el minimax para hacer frente a esto aumentaría en gran medida el número de posiciones que se necesitaban examinar y ralentizaría aún más el programa. Esperaba que adaptar el tipo A para hacer frente a esto aumentaría en gran medida el número de posiciones que se necesitaban examinar y ralentizaría aún más el programa.
Esto condujo naturalmente a lo que se conoce como "búsqueda selectiva" o "búsqueda de tipo B", que utiliza el conocimiento del ajedrez (heurística) para seleccionar unas pocas jugadas presuntamente buenas de cada posición para buscarlas y eliminar las demás sin buscarlas. En lugar de desperdiciar potencia de procesamiento examinando jugadas malas 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") en las líneas más significativas en un tiempo razonable. Sin embargo, los primeros intentos de búsqueda selectiva a menudo dieron como resultado que se eliminaran la mejor jugada o las mejores jugadas. 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 período inicial 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 por 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 necesario para simplemente buscar todos los movimientos era mucho menor que el tiempo necesario para aplicar heurísticas intensivas en conocimiento para seleccionar solo algunos de ellos, y el beneficio de no eliminar de manera prematura o inadvertida los buenos movimientos resultó en un rendimiento sustancialmente mejor.
En los años 1980 y 1990, finalmente se logró un progreso en el paradigma de búsqueda selectiva, con el desarrollo de la búsqueda de quiescencia , la poda de movimiento nulo 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ían la pena el tiempo adicional que ahorraban porque podían buscar más profundamente y fueron ampliamente adoptadas por muchos motores. Si bien muchos programas modernos usan la búsqueda alfa-beta como sustrato para su algoritmo de búsqueda, estas heurísticas de búsqueda selectiva adicionales utilizadas en los programas modernos significan que el programa ya no realiza una búsqueda de "fuerza bruta". En cambio, 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 se podan la mayoría de los nodos en el árbol de búsqueda, lo que permite a los programas modernos buscar muy profundamente.
En 2006, Rémi Coulom creó la búsqueda de árboles 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 superior aplicados a árboles o UCT para abreviar. En 2011, Chris Rosin desarrolló una variación de UCT llamada Predictor + Límites de confianza superior aplicados a árboles o PUCT para abreviar. PUCT se utilizó luego en AlphaZero en 2017 y, más tarde, 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 las Control Data Cyber 176 o Cray-1, lo que indica que durante ese período de desarrollo del ajedrez por computadora, la capacidad de procesamiento era el factor limitante en el rendimiento. La mayoría de los programas de ajedrez tenían dificultades para buscar a una profundidad mayor de 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 duplicar la velocidad de la computadora genera aproximadamente entre cincuenta y setenta puntos Elo en fuerza de juego (Levy y Newborn 1991:192).
En la mayoría de las posiciones de ajedrez, los ordenadores no pueden prever todas las posiciones finales posibles. En lugar de ello, deben prever unas cuantas jugadas y comparar las posiciones posibles, 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 los distintos programas de ajedrez. Las funciones de evaluación suelen evaluar las 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 dan como resultado porcentajes de victoria/empate/derrota en lugar de centipeones.
Históricamente, las funciones de evaluación artesanales consideran el valor del material junto con otros factores que afectan la fuerza de cada lado. Al contar el material para cada lado, los valores típicos para las piezas son 1 punto para un peón , 3 puntos para un caballo o alfil , 5 puntos para una torre y 9 puntos para una reina . (Véase Valor relativo de la pieza de ajedrez ). Al rey a veces se le da un valor arbitrariamente alto, como 200 puntos ( artículo de Shannon ) para asegurar que un jaque mate supere a 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 suele valer más, las piezas centralizadas valen más, etc. Normalmente se considera la protección de los reyes, así como la fase del juego (apertura, medio juego o final). Las técnicas de aprendizaje automático, como el giro de Texel, el descenso de gradiente estocástico o el aprendizaje de refuerzo , se utilizan habitualmente para optimizar funciones de evaluación elaboradas manualmente.
La mayoría de las funciones de evaluación modernas hacen uso de redes neuronales . La función de evaluación más común en uso hoy en día es la red neuronal actualizable de manera eficiente , que es una red neuronal superficial cuyas entradas son tablas de cuadrados de piezas . Las tablas de cuadrados de piezas son un conjunto de 64 valores correspondientes a los cuadrados del tablero de ajedrez, y normalmente existe una tabla de cuadrados de piezas para cada pieza y color, lo que da como resultado 12 tablas de cuadrados de piezas y, por lo tanto, 768 entradas en la red neuronal. Además, algunos motores utilizan redes neuronales profundas en su función de evaluación. Las redes neuronales generalmente se entrenan utilizando algún algoritmo de aprendizaje de refuerzo , junto con el aprendizaje supervisado o el aprendizaje no supervisado .
La salida de la función de evaluación es un único escalar, 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, la salida de la cabeza de la red neuronal. La evaluación supuestamente representa o aproxima el 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, una evaluación se compara con evaluaciones de otras hojas, eliminando nodos que representan movimientos malos o deficientes para cualquiera de los lados, para producir un nodo que, por convergencia, representa el valor de la posición con el mejor juego de ambos lados.
El juego de finales ha sido durante mucho tiempo una de las grandes debilidades de los programas de ajedrez debido a la profundidad de búsqueda necesaria. Algunos programas de nivel experto no eran capaces de ganar en posiciones en las que incluso jugadores humanos de nivel intermedio podían forzar una victoria.
Para resolver este problema, se han utilizado ordenadores para analizar por completo algunas posiciones de finales de ajedrez , empezando por rey y peón contra rey. Estas tablas de finales se generan de antemano utilizando una forma de análisis retrógrado , empezando por posiciones en las que se conoce el resultado final (por ejemplo, en las que se ha dado mate a un bando) y viendo qué otras posiciones están a un movimiento de ellas, después cuáles están a un movimiento de esas, etc. Ken Thompson fue un pionero en esta área.
Los resultados del análisis informático a veces sorprendían a la gente. En 1977, la máquina de ajedrez Belle de Thompson utilizó la base de datos de finales de rey y torre contra rey y reina y pudo empatar ese final teóricamente perdido contra varios maestros (véase la posición de Philidor nº Reina contra torre ). Esto se produjo a pesar de no seguir la estrategia habitual de retrasar la derrota manteniendo al rey y la torre defensores juntos durante 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 devolvía 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 estableció una posición de dama 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 aceptó el empate, al no poder forzar el jaque mate o 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 jugó contra la computadora nuevamente 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 número quincuagésimo, lo que le dio una posición ganadora (Levy y Newborn 1991:144-148), (Nunn 2002:49).
Otras posiciones, que durante mucho tiempo se creyeron ganadas, resultaron requerir más movimientos contra el juego perfecto para ganar que los permitidos por la regla de los cincuenta movimientos del ajedrez. Como consecuencia, durante algunos años las reglas oficiales de ajedrez de la FIDE se cambiaron para ampliar el número de movimientos permitidos en estos finales. Después de un tiempo, la regla volvió a ser de 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 supuso 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 publicado otros formatos de bases de datos de finales, incluyendo Edward Tablebase, De Koning Database y Nalimov Tablebase, que es utilizada por muchos programas de ajedrez como Rybka , Shredder y Fritz . Hay bases de datos de finales disponibles 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 base de datos de finales de ajedrez para todos los finales con siete piezas o menos (se excluyen las posiciones de finales triviales, como seis piezas blancas contra un rey negro solitario ). [27] [28] En todas estas bases de datos de finales se supone que el enroque ya no es posible.
Muchas tablas de ajedrez no tienen en cuenta la regla de los cincuenta movimientos, según la cual una partida en la que transcurren cincuenta movimientos sin que se produzca una captura o un movimiento de peón puede considerarse tablas para cualquiera de los jugadores. Esto hace que la tabla de ajedrez devuelva resultados como "Mate forzado en sesenta y seis movimientos" en algunas posiciones que en realidad serían tablas 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 tales posiciones, no sería necesario regenerar todas las tablas de ajedrez. También es muy fácil para el programa que utiliza las tablas de ajedrez notar y tener en cuenta esta "característica" y, en cualquier caso, si se utiliza una tabla de ajedrez de finales, elegirá la jugada que lleve a la victoria más rápida (incluso si infringiera la regla de los cincuenta movimientos con un juego perfecto). Si se juega contra un oponente que no utiliza una tabla de ajedrez, dicha elección dará buenas posibilidades de ganar en cincuenta movimientos.
Las bases de datos de Nalimov, que utilizan técnicas de compresión de última generación , requieren 7,05 GB de espacio en el disco duro para todos los finales de cinco piezas. Para cubrir todos los finales 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 tuvieron un papel destacado en 1999, cuando Kasparov jugó una partida de exhibición en Internet contra el resto del mundo . Se llegó a un final de siete piezas de dama y peón , en el que el Equipo Mundial luchó por salvar un empate. Eugene Nalimov ayudó generando la base de datos de finales de seis piezas en la que ambos bandos tenían dos damas, lo que se utilizó mucho para facilitar el análisis por parte de ambos bandos.
La base de datos de finales más popular es syzygy, que es la utilizada por la mayoría de los programas informáticos más importantes, como Stockfish , Leela Chess Zero y Komodo . También es significativamente más pequeña que otros formatos, ya que las bases de datos de 7 piezas 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 menor en la fuerza de 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 variantes fuertes, tal como las exponen los maestros, haciendo referencia a un libro de aperturas almacenado en una base de datos en disco. Los libros de aperturas cubren las jugadas iniciales de una partida con una profundidad variable, según la apertura y la variante, pero por lo general hasta las primeras 10 o 12 jugadas (20 a 24 jugadas). Dado que los maestros han estudiado las aperturas en profundidad durante siglos, y algunas se conocen hasta bien entrada la mitad del juego, las valoraciones de variantes específicas por parte de los maestros generalmente serán superiores a la heurística general del programa.
Si bien en algún momento, realizar una jugada fuera de libro para que el programa de ajedrez dependiera de sus propios recursos podría haber sido una estrategia eficaz porque los libros de aperturas de ajedrez eran selectivos en cuanto al estilo de juego del programa y los programas tenían debilidades notables en relación con los humanos, eso ya no es así hoy en día. [ ¿Cuándo? ] Los libros de aperturas almacenados en bases de datos de computadoras son muy probablemente mucho más extensos que incluso los humanos mejor preparados, y realizar una jugada fuera de libro en forma temprana puede resultar en que la computadora encuentre la jugada inusual en su libro y cargue al oponente con una desventaja aguda. Incluso si no lo hace, 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 variante desconocida sobre el tablero.
En los torneos de motores modernos, se utilizan libros de apertura para obligar a los motores a jugar aperturas intencionalmente desequilibradas para reducir la tasa de empates 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 fanáticos comparar la fuerza 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 pone a prueba la solidez de los motores de ajedrez computacionales haciendo que los programas compitan 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 utiliza tres listas diferentes: 40/40 (40 minutos por cada 40 movimientos jugados), 40/4 (4 minutos por cada 40 movimientos jugados) y 40/4 FRC (mismo control de tiempo pero en Chess960). [Nota 2] La ponderación (o el cerebro permanente ) se desactiva y el tiempo 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 la partida junto con tablas de 4 o 5 jugadores . [40] [41] [42]
La idea de crear una máquina que jugara al ajedrez se remonta al siglo XVIII. Alrededor de 1769, el autómata que jugaba al ajedrez llamado El Turco , creado por el inventor húngaro Farkas Kempelen , se hizo famoso antes de ser descubierto como un engaño. Antes del desarrollo de la computación digital , los ensayos serios basados 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 complejos y limitados 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, con crecientes grados de seriedad y éxito, máquinas de juego de ajedrez y programas informáticos. Uno de los pocos grandes maestros del ajedrez que se dedicó seriamente al ajedrez informático fue el ex campeón mundial de ajedrez Mikhail Botvinnik , que escribió varias obras 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 de tipo B de Shannon, como se discutió junto con Max Euwe en 1958 en la televisión holandesa. Al trabajar 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 ese momento, solo las computadoras más potentes podían lograr mucho más que una búsqueda de ancho completo de tres capas, y Botvinnik no tenía tales máquinas. En 1965, Botvinnik fue consultor del equipo ITEP en una partida de ajedrez por ordenador 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 (véase Kotok-McCarthy ). Más tarde, 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 de ataque y trayectorias en el Club Central de Ajedrez de Moscú en 1966, encontró a Vladimir Butenko como partidario 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 se negó a seguir cooperando y comenzó a escribir su propio programa, llamado Eureka. En los años 70 y 80, al frente de 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 la inteligencia artificial. En los años 90, Botvinnik, ya octogenario, trabajó en el nuevo proyecto "CC Sapiens".
Un hito en el desarrollo se produjo cuando el equipo de la Universidad Northwestern , responsable de la serie de programas Chess y que ganó los tres primeros Campeonatos de Ajedrez Informático de la ACM (1970-72), abandonó la búsqueda de tipo B en 1973. El programa resultante, Chess 4.0, ganó el campeonato de ese año y sus sucesores llegaron al segundo puesto tanto en el Campeonato ACM de 1974 como en el Campeonato Mundial de Ajedrez Informático inaugural de ese año , antes de ganar el Campeonato ACM de nuevo en 1975, 1976 y 1977. La implementación de tipo A resultó ser igual de rápida: en el tiempo que solía llevar decidir qué movimientos eran dignos de ser buscados, era posible simplemente buscarlos todos. De hecho, Chess 4.0 estableció el paradigma que fue y sigue siendo seguido esencialmente por todos los programas de ajedrez modernos de la actualidad, y que había sido iniciado con éxito por el ITEP ruso en 1965.
En 1978, una versión temprana de la máquina de ajedrez de hardware Belle de Ken Thompson participó y ganó el Campeonato de Ajedrez Informático de América del Norte contra el dominante Northwestern University Chess 4.7.
Los avances tecnológicos en potencia de procesamiento han hecho que el método de fuerza bruta sea mucho más incisivo que en los primeros años. El resultado es que un jugador de IA muy sólido y táctico, 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 el 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, lo que marcó la primera vez que una computadora derrotó a un campeón mundial de ajedrez en el control de tiempo estándar.
En 2016, la NPR pidió a los expertos que caracterizaran el estilo de juego de los motores de ajedrez informáticos. Murray Campbell, de IBM, afirmó que "los ordenadores no tienen ningún sentido de la estética... Juegan lo que creen que es objetivamente el mejor movimiento en cualquier posición, incluso si parece absurdo, y pueden realizar cualquier movimiento sin importar lo feo que sea". Los grandes maestros Andrew Soltis y Susan Polgar afirmaron que los ordenadores tienen más probabilidades de retirarse que los humanos. [22]
Si bien las redes neuronales se han utilizado en las funciones de evaluación de los motores de ajedrez desde fines 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 por computadora en 2018 por Yu Nasu, [48] [49] y tuvieron que ser portadas primero a un derivado de Stockfish llamado Stockfish NNUE el 31 de mayo de 2020, [50] e integradas 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 condujo a la adopción generalizada de redes neuronales en los motores de ajedrez. [53] Sin embargo, AlphaZero influyó en muy pocos motores para comenzar a usar redes neuronales, y estos tendían a ser nuevos motores experimentales como Leela Chess Zero , que comenzó específicamente a replicar el artículo de 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 solo usan unidades centrales de procesamiento , y el cálculo y 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 hechas a mano hasta que las redes neuronales actualizables de manera eficiente se trasladaron al ajedrez por computadora en 2020, lo que no requirió ni el uso de GPU ni bibliotecas como CUDA en absoluto. Aun así, las redes neuronales utilizadas en el ajedrez por computadora son bastante superficiales, y los métodos de aprendizaje de refuerzo profundo desarrollados por AlphaZero todavía son extremadamente raros en el ajedrez por computadora.
Estos sistemas de juego de ajedrez incluyen hardware personalizado con fechas aproximadas de introducción (excluidas las microcomputadoras dedicadas):
.jpg/1280px-thumbnail.jpg)
A finales de los años 70 y principios de los 90, existía un mercado competitivo para los ordenadores dedicados al ajedrez. Este mercado cambió a mediados de los 90, cuando los ordenadores con procesadores dedicados ya no podían competir con los rápidos procesadores de los ordenadores personales.
Recientemente, algunos aficionados han estado usando el Multi Emulator Super System para ejecutar los programas de ajedrez creados para Fidelity o los ordenadores 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 Mephisto de Hegener & Glaser que escribió para que funcionen como motores UCI. [75]
Estos programas se pueden ejecutar en MS-DOS y se pueden ejecutar en Windows 10 de 64 bits a través de emuladores como DOSBox o Qemu : [76]
Entre los teóricos del ajedrez informático más conocidos se incluyen:
En general, se considera que las perspectivas de resolver por completo el ajedrez son bastante remotas. Se conjetura ampliamente que no existe un método computacionalmente económico para resolver el ajedrez, ni siquiera en el sentido débil de determinar con certeza el valor de la posición inicial, y por lo tanto, la idea de resolver el ajedrez en el sentido más fuerte de obtener una descripción prácticamente utilizable de una estrategia para un juego perfecto para cualquiera de los bandos parece poco realista hoy en día. Sin embargo, no se ha demostrado que no exista una forma computacionalmente económica de determinar la mejor jugada en una posición de ajedrez, ni siquiera que un buscador alfa-beta tradicional que se ejecute en el hardware informático actual no pueda resolver la posición inicial en una cantidad de tiempo aceptable. La dificultad de probar esto último radica en el hecho de que, si bien el número de posiciones del tablero que podrían ocurrir en el curso 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 solo 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 arbitrario de piezas en un tablero de ajedrez arbitrariamente grande) es EXPTIME-completo , [79] lo que significa que determinar el lado ganador en una posición arbitraria de ajedrez generalizado lleva demostrablemente un tiempo exponencial en el peor de los casos; sin embargo, este resultado teórico no da un límite inferior a la cantidad de trabajo requerido para resolver el ajedrez 8x8 ordinario.
Se ha resuelto el Miniajedrez de Martin Gardner , jugado en un tablero de 5x5 con aproximadamente 10 a 18 posiciones posibles en el tablero; su valor en teoría de juegos es 1/2 (es decir, cualquier bando puede forzar un empate) y se ha descrito la estrategia de forzamiento 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 dada. Los autores de motores se centran en mejorar el juego 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 hoy omnipresente Interfaz Universal de Ajedrez desarrollada por Stefan Meyer-Kahlen y Franz Huber. Hay otros, como el Protocolo de Comunicación de Motor de Ajedrez 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 un protocolo pueden ser portados a otros SO o protocolos.
Los motores de ajedrez se enfrentan periódicamente entre sí en torneos dedicados a ellos .
En 1997, el Internet Chess Club lanzó su primer cliente Java para jugar al ajedrez en línea contra otras personas dentro del navegador web. [80] Esta fue probablemente una de las primeras aplicaciones web de ajedrez. Poco después, Free Internet Chess Server siguió 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 ajedrez en vivo en 2007. [83] Chessbase / Playchess tiene desde hace 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 al año siguiente, [86] y Chess.com agregó su Tactics Trainer en 2008. [87] Chessbase agregó una aplicación web de entrenamiento táctico en 2015. [88]
Chessbase puso en línea su base de datos de partidas de ajedrez en 1998. [89] Otra de las primeras bases de datos de partidas de ajedrez fue Chess Lab, que comenzó en 1999. [90] New In Chess había intentado inicialmente competir con Chessbase lanzando un programa NICBase para Windows 3.x , pero finalmente decidió renunciar al software y, en su lugar, centrarse en su base de datos en línea a partir de 2002. [91]
Se puede jugar contra el motor Shredder en línea desde 2006. [92] En 2015, Chessbase agregó una aplicación web para jugar Fritz, [93] así como My Games 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] Grandes Maestros de primer nivel como Sam Shankland y Walter Browne han contribuido con lecciones.
{{cite web}}: CS1 maint: bot: estado de URL original desconocido ( enlace ){{cite web}}: CS1 maint: copia archivada como título ( enlace )Este artículo incorpora texto de Chess Programming Wiki disponible bajo la licencia CC BY-SA 3.0.
