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 informáticas de ajedrez que se juegan al nivel de un 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 , GNU Chess , Fruit y otras aplicaciones gratuitas de código abierto están disponibles para varias plataformas.
Las aplicaciones de ajedrez por computadora, ya sean implementadas en hardware o software, emplean un paradigma diferente al de los humanos para elegir sus movimientos: usan 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 proceso. tocar. 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 heurísticas de extensión y reducción que reducen el árbol a nodos en su mayoría relevantes, hacen que este enfoque sea efectivo.
Las primeras máquinas de ajedrez capaces de jugar al 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 tubo de vacío (1950). Los primeros programas funcionaron tan mal que incluso un principiante podría vencerlos. En 40 años, en 1997, los motores de ajedrez que funcionaban en supercomputadoras o hardware especializado eran capaces de derrotar incluso a los mejores jugadores humanos . En 2006, los programas que se ejecutan en PC de escritorio habían alcanzado la misma capacidad. En 2006, Monroe Newborn , profesor de Ciencias de la Computación en la Universidad McGill , declaró: "la ciencia se ha hecho". Sin embargo, actualmente no es posible resolver ajedrez para las computadoras modernas debido a la gran cantidad de variaciones posibles del juego . [1]
El ajedrez informático alguna vez se consideró la " Drosophila de la IA", la vanguardia de la ingeniería del conocimiento . Pero el campo ahora se considera un paradigma científicamente completado, y jugar al ajedrez es una actividad informática mundana. [2]
Disponibilidad y fuerza de juego
Las máquinas / programas de ajedrez están disponibles en varias formas diferentes: como máquinas de ajedrez independientes (generalmente 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. dispositivos. 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 miden más de unos pocos megabytes en el disco, usan unos pocos megabytes de memoria (pero pueden usar mucho más, si está disponible) y cualquier procesador de 300Mhz o más rápido es suficiente. El rendimiento variará modestamente con la velocidad del procesador, pero la memoria suficiente para albergar una tabla de transposición grande (hasta varios gigabytes o más) es más importante para la potencia de reproducción que la velocidad del procesador.
La mayoría de los programas y máquinas de ajedrez comerciales disponibles tienen una fuerza de juego súper grande (Elo 2700 o más) y aprovechan las arquitecturas de CPU de computadora de múltiples núcleos y subprocesos. Los mejores programas como Stockfish han superado incluso a los jugadores de calibre campeones del mundo. La mayoría de los motores de ajedrez se conectan a una GUI como Winboard o Chessbase y la fuerza de juego, 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, retirar movimientos, ofrecer y aceptar empates (y renunciar), tener una función de "entrenador" para recomendar un movimiento cuando el jugador tiene dudas y mostrar el análisis del motor como el el juego progresa.
Hay algunos motores de ajedrez como Sargon , IPPOLIT , Stockfish , Crafty , Fruit y GNU Chess que se pueden descargar (o obtener el código fuente) de Internet de forma gratuita.
Tipos y características de software de ajedrez
Quizás el tipo más común de software de ajedrez son los programas que simplemente juegan al ajedrez. Haces un movimiento en el tablero, y la IA calcula y reproduce una respuesta, yendo y viniendo hasta que un jugador renuncia. A veces, el motor de ajedrez , que calcula los movimientos, y la interfaz gráfica de usuario (GUI) son programas separados. Se puede importar una variedad de motores a la GUI, para que pueda jugar contra diferentes estilos. Los motores a menudo tienen solo 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 en 3D o animadas. Debido a que los motores recientes son tan potentes, los motores o las GUI pueden ofrecer alguna forma de limitar la potencia del motor, por lo que el jugador tiene más posibilidades de ganar. Los motores de 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 juegos históricos, analizarlos, verificar estadísticas y elaborar un repertorio de aperturas. Chessbase (para PC) es quizás el programa más común para esto entre los jugadores profesionales, pero existen alternativas como la base de datos de información de ajedrez de Shane (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]
Los programas como Playchess te permiten jugar contra otros jugadores a través de Internet.
Los programas de entrenamiento de ajedrez enseñan ajedrez. Chessmaster tenía tutoriales de juego a cargo 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 compañía Play Magnus de los campeones mundiales Magnus Carlsen lanzó recientemente una aplicación Magnus Trainer para Android e iOS. Chessbase tiene Fritz y Chesster para niños. Convekta tiene 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 hay software para manejar problemas de ajedrez .
Computadoras versus humanos
Después de descubrir la detección de refutación (la aplicación de 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 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 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 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 "la única manera un programa de computadora actual que podría ganar un solo juego contra un jugador maestro sería para el maestro, quizás en un estupor borracho mientras juega 50 juegos simultáneamente, para cometer un error una vez al año ". [9]
A fines 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, Universidad de Northwestern 's Chess 4.5 en el Masson Paul de Ajedrez Campeonato Americano de Clase B de nivel 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 por computadora contra un jugador de clase magistral a nivel de torneo al ganar una de las seis partidas. [10] En 1980, Belle comenzó a derrotar a Masters a menudo. En 1982, dos programas se jugaban a nivel de maestría y tres eran un poco más débiles. [9]
La mejora repentina sin un avance teórico sorprendió a los humanos, que no esperaban que la capacidad de Belle para examinar 100.000 posiciones por segundo, unas ocho capas, fuera suficiente. Los Spracklens, creadores del exitoso programa de microcomputadoras Sargon , estimaron que el 90% de la mejora provino de una velocidad de evaluación más rápida y solo el 10% de evaluaciones mejoradas. New Scientist declaró en 1982 que las computadoras "juegan un ajedrez terrible ... torpe, ineficiente, difuso y simplemente feo", pero los humanos perdieron al cometer "errores horribles, lapsos asombrosos, descuidos incomprensibles, errores de cálculo graves y cosas por el estilo". mucho más a menudo de lo que pensaban; "En resumen, las computadoras ganan principalmente por su capacidad para encontrar y explotar errores de cálculo en las iniciativas humanas". [9]
Para 1982, los programas de ajedrez de microcomputadora podían evaluar hasta 1.500 movimientos por segundo y eran tan fuertes como los programas de ajedrez de computadora central de cinco años antes, capaces de derrotar a la mayoría de los jugadores aficionados. Si bien solo pudo mirar hacia adelante una o dos capas más que en su debut a mediados de la década de 1970, hacerlo mejoró 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 una rica cosecha de errores humanos se vuelve accesible", 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 señaló la declaración de Robert Byrne de que "tácticamente están más libres de errores que el humano promedio jugador". La revista describió SPOC como un "programa de ajedrez de última generación" para IBM PC con un nivel de juego "sorprendentemente alto", y calculó su calificación USCF en 1700 (Clase B). [11]
En el Campeonato Norteamericano de Ajedrez Informático 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 pronosticó diez años; los Spracklens 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 demostró el entonces campeón mundial Garry Kasparov en dos fuertes victorias en 1989. No fue hasta un partido de 1996 con Deep Blue de IBM que Kasparov perdió su primer juego contra una computadora en Controles de tiempo de torneo en Deep Blue versus Kasparov, 1996, Juego 1 . Este juego fue, de hecho, la primera vez que un campeón mundial reinante perdió contra una computadora que usaba 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 3½ – 2½ en un partido de vuelta. En 2003 se realizó un documental principalmente sobre el enfrentamiento, titulado Game Over: Kasparov and the Machine . IBM mantiene un sitio web del evento .
a | B | C | D | mi | F | gramo | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | B | C | D | mi | F | gramo | h |
Con el aumento de la potencia de procesamiento y las 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 alto nivel. En 1998, Rebel 10 derrotó a Viswanathan Anand , quien en ese momento ocupaba el segundo lugar en el mundo, por una puntuación de 5-3. Sin embargo, la mayoría de esos juegos no se jugaron con los controles de tiempo normales. De los ocho juegos, cuatro fueron juegos relámpago (cinco minutos más cinco segundos de retraso de Fischer (ver control de tiempo ) para cada movimiento); estos rebeldes ganaron 3-1. Dos fueron juegos semi-blitz (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, los 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 partido Brains in Bahrain de ocho partidos, que terminó en empate. Kramnik ganó los juegos 2 y 3 con tácticas anti-computadora "convencionales" : juega de manera conservadora para obtener una ventaja a largo plazo que la computadora no puede ver en la búsqueda del árbol de juegos. Fritz, sin embargo, ganó el juego 5 después de un grave error de Kramnik. Los comentaristas del torneo describieron el sexto partido como "espectacular". Kramnik, en una mejor posición en el medio juego temprano , intentó sacrificar piezas para lograr un fuerte ataque táctico, una estrategia conocida por ser altamente arriesgada contra las computadoras que están en su mejor momento de defensa 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 renunció al juego, creyendo que la posición había perdido. Sin embargo, el análisis humano y por computadora posterior al juego ha demostrado que era poco probable que el programa Fritz hubiera sido capaz de 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 aún consideran a Kramnik como el jugador más fuerte del partido. [ cita requerida ]
En enero de 2003, Garry Kasparov jugó con Junior , otro programa informático de ajedrez, en la ciudad de Nueva York . El partido terminó 3-3.
En noviembre de 2003, Garry Kasparov interpretó a 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 una partida de seis juegos (aunque la preparación de Adams fue mucho menor más completo que el de Kramnik para la serie 2002). [14]
En noviembre-diciembre de 2006, el campeón mundial Vladimir Kramnik jugó contra Deep Fritz . Esta vez ganó la computadora; el partido terminó 2-4. Kramnik pudo ver el libro de aperturas de la computadora. En los primeros cinco juegos, Kramnik condujo el juego hacia un típico concurso posicional "anti-computadora". Perdió un juego ( pasando por alto un mate en uno ) y empató los siguientes cuatro. En el juego final, 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". [dieciséis]
Los partidos de ajedrez entre humanos y computadoras mostraron que los mejores sistemas informáticos superaron a los campeones de ajedrez humanos a fines de la década de 1990. Durante los 40 años anteriores a eso, la tendencia había sido que las mejores máquinas ganaban alrededor de 40 puntos por año en la calificación Elo, mientras que los mejores humanos solo ganaban aproximadamente 2 puntos por año. [17] La calificación más alta obtenida por una computadora en la competencia humana fue la calificación USCF de Deep Thought de 2551 en 1988 y la FIDE ya no acepta los resultados entre humanos y computadoras en sus listas de calificación. Se han creado grupos de Elo especializados solo para máquinas para calificar máquinas, pero tales números, aunque son similares en apariencia, no deben compararse directamente. [18] En 2016, la Asociación Sueca de Computadoras de Ajedrez calificó al programa de computadora Komodo en 3361.
Los motores de ajedrez continúan 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 corriendo 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 el 4 de agosto - 14, 2009. [19] Pocket Fritz 4 busca menos de 20.000 posiciones por segundo. [20] Esto contrasta con las supercomputadoras como Deep Blue que buscaban 200 millones de posiciones por segundo.
Advanced Chess es una forma de ajedrez desarrollada en 1998 por Kasparov donde 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, esto ha sido probado en numerosas ocasiones, en eventos de Freestyle Chess.
Los jugadores de hoy tienden a tratar 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 jugará ajedrez informático porque "pierde todo el tiempo y no hay nada más deprimente que perder sin siquiera estar en el juego." [22]
Métodos informáticos
Desde la era de las máquinas mecánicas que jugaban finales de torre y rey y máquinas eléctricas que jugaban a otros juegos como hex (juego) 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, pensar y aplicar el conocimiento, y el juego de ajedrez, debido a su enorme complejidad, se convirtió en la " Drosophila de la inteligencia artificial (IA)". [23] 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, se conocían popularmente como "cerebros electrónicos". Se idearon varios esquemas diferentes a partir de la segunda mitad del siglo XX para representar el conocimiento y el pensamiento, aplicados al juego de ajedrez (y otros juegos como las damas):
- basado en búsqueda (minimax / alfabeta o búsqueda selectiva)
- basado en el conocimiento (PARADISE)
- muestreo estadístico (búsqueda de árboles de montecarlo)
- algoritmos genéticos
- aprendizaje automático
Usando heurísticas de "fines y medios", un jugador de ajedrez humano puede determinar intuitivamente los 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 se requiere mirar al menos cinco movimientos hacia adelante (diez capas ) cuando sea necesario. Las reglas normales del torneo le 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 billón de posibilidades para mirar hacia adelante diez capas (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 realizar representaciones procedimentales del juego de ajedrez fueron anteriores a la era de la electrónica digital, pero fue el programa almacenado en la computadora digital lo que permitió calcular tal complejidad. Claude Shannon, en 1949, expuso 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 elecciones (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 se hizo evidente de inmediato: hay un promedio de 36 movimientos por posición en el ajedrez y un juego promedio dura alrededor de 35 movimientos hasta la resignación (60-80 movimientos si se juega jaque mate, estancamiento u otro empate). 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 anticipación limitada (búsqueda) a una profundidad fija, seguida del uso de conocimientos específicos del dominio para evaluar las posiciones terminales resultantes. Una especie de posición intermedia (más tarde denominada "minimax"), dadas las buenas jugadas de ambos lados, resultaría, y su evaluación informaría al jugador sobre la bondad o la 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 del conocimiento sutil del 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 qué conocimiento de ajedrez era útil y cómo se codificaba llevaría décadas descubrirlo.
Un paradigma de búsqueda temprano llamado poda alfa-beta , un sistema para definir límites superior e inferior en posibles resultados de búsqueda y buscar hasta que los límites coincidieran, redujo el factor de ramificación del árbol de juego de forma logarítmica, pero aún no era factible para los programas de ajedrez explotar la explosión exponencial del árbol. Esto condujo naturalmente a lo que se conoce como "búsqueda selectiva", 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. Pero el ajedrez no es un juego dado a la inspección temática, y es posible que la bondad o la maldad de una jugada no se determinen para muchas jugadas del juego, por lo que la búsqueda selectiva a menudo resultó en la mejor jugada o en la eliminación de las jugadas. Se logró poco o ningún progreso durante los siguientes 25 años dominados por el paradigma de búsqueda selectiva. El mejor programa producido durante este tiempo fue Mac Hack VI en 1967; jugó 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).
En 1974, otro paradigma de búsqueda se implementó por primera vez en el programa de Ajedrez 4.0 de la Universidad Northwestern, la alternativa descrita en el artículo de Shannon de 1949, llamada búsqueda de ancho completo o "fuerza bruta". En este enfoque, se buscan todos los movimientos alternativos en un nodo y ninguno se elimina. 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 podar los buenos movimientos de manera prematura o inadvertida resultó en un rendimiento sustancialmente mayor. .
Los desarrolladores de un sistema informático para jugar al ajedrez deben decidir sobre una serie de cuestiones fundamentales de implementación. Éstas incluyen:
- Interfaz gráfica de usuario (GUI): cómo se ingresan los movimientos y cómo se comunican al usuario, cómo se registra el juego, cómo se configuran los controles de tiempo y otras consideraciones de la interfaz.
- Representación de la junta : cómo se representa una sola posición en las estructuras de datos;
- Técnicas de búsqueda: cómo identificar los posibles movimientos y seleccionar los más prometedores para un examen más detenido;
- Evaluación de hojas: cómo evaluar el valor de una posición en el tablero, si no se realizarán más búsquedas desde esa posición.
Interfaz gráfica del usuario
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 Portable Game Notation (PGN) y pueden leer y escribir posiciones individuales como Forsyth-Edwards Notation (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 comprendan la notación algebraica estándar .
A partir de finales de la década de 1990, los programadores comenzaron a desarrollar motores por separado (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 piezas, los desarrolladores pueden escribir solo la interfaz de usuario, o solo el motor, sin necesidad de escribir ambas partes del programa. (Ver también motores de ajedrez ).
Los desarrolladores tienen que decidir si conectar el motor a un libro de apertura y / o bases de tablas finales o dejar esto en manos de la GUI.
Representaciones de la junta
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 la posición . 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 (" tableros de bits ") y posiciones codificadas por huffman para compactos. almacenamiento a largo plazo.
Técnicas de búsqueda
Los programas de ajedrez por computadora consideran los movimientos de ajedrez como un árbol de juego . En teoría, examinan todos los movimientos, luego todos los movimientos en contra de esos movimientos, luego todos los movimientos que los contrarrestan, y así sucesivamente, donde cada movimiento individual de un jugador se llama " 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). En cada capa se selecciona el "mejor" movimiento del jugador; un jugador está tratando de maximizar la puntuación, el otro de minimizarla. Mediante este proceso alternativo, se llegará a un nodo terminal particular 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 la junta. Este proceso de búsqueda se llama 'minimax'.
Una implementación ingenua de este enfoque solo 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 en gran medida la búsqueda de buenos movimientos.
El primer artículo sobre el tema fue de Claude Shannon en 1950. [24] Él predijo las dos principales estrategias de búsqueda posibles que se utilizarían, que denominó "Tipo A" y "Tipo B", [25] antes de que alguien hubiera programado un computadora para jugar al ajedrez.
Los programas de Tipo A usarían un enfoque de " fuerza bruta ", examinando cada posición posible para un número fijo de movimientos usando el algoritmo minimax . 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 109 posiciones involucradas en mirar tres movimientos hacia adelante para ambos lados (seis capas ) tomaría alrededor de dieciséis minutos, incluso en el "muy optimista". caso de que la computadora de ajedrez evaluara un millón de posiciones por segundo. (Se necesitaron unos cuarenta años para alcanzar esta velocidad).
En segundo lugar, ignoró el problema de la inactividad, tratando de evaluar solo 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 tipo A para hacer frente a esto aumentaría considerablemente el número de puestos que deben examinarse y ralentizaría aún más el programa.
En lugar de desperdiciar el poder de procesamiento examinando movimientos malos o triviales, Shannon sugirió que los programas "tipo B" usarían dos mejoras:
- Emplea una búsqueda de reposo .
- Solo mira algunos buenos movimientos para cada posición.
Esto les permitiría mirar más adelante ("más profundo") en las líneas más significativas en un tiempo razonable. La prueba del tiempo ha confirmado el primer enfoque; todos los programas modernos emplean una búsqueda de inactividad terminal antes de evaluar las posiciones. El segundo enfoque (ahora llamado poda hacia adelante ) se ha descartado en favor de las extensiones de búsqueda.
Adriaan de Groot entrevistó a varios jugadores de ajedrez de diferentes puntos fuertes y concluyó que tanto los maestros como los principiantes miran entre cuarenta y cincuenta posiciones antes de decidir qué movimiento jugar. Lo que hace que los primeros jugadores sean mucho mejores es que utilizan habilidades de reconocimiento de patrones creadas a partir de la experiencia. Esto les permite examinar algunas líneas con mucha mayor profundidad que otras simplemente sin considerar movimientos que pueden asumir que son deficientes.
Más evidencia de que este es el caso es la forma en que los buenos jugadores humanos encuentran mucho más fácil recordar posiciones de juegos de ajedrez genuinos, dividiéndolos en una pequeña cantidad de subposiciones reconocibles, en lugar de arreglos completamente aleatorios de las mismas piezas. Por el contrario, los jugadores pobres tienen el mismo nivel de recuerdo para ambos.
El problema con el tipo B es que depende de que el programa pueda decidir qué movimientos son lo suficientemente buenos para ser dignos de consideración ('plausibles') en cualquier posición dada y esto demostró ser un problema mucho más difícil de resolver que acelerar el tipo. Búsquedas con hardware superior y técnicas de extensión de búsqueda.
Los programas de búsqueda de ancho completo ("fuerza bruta") ganaron por la sencilla razón de que sus programas jugaban mejor al ajedrez. Dichos programas no intentaron imitar los procesos de pensamiento humano, sino que se basaron en búsquedas alfa-beta y negascout de ancho completo . La mayoría de estos programas (incluidos todos los programas modernos de la actualidad) también incluían una parte selectiva bastante limitada de la búsqueda basada en búsquedas de inactividad y, por lo general, extensiones y poda (en particular, poda de movimiento nulo desde la década de 1990 en adelante) que se activaron en función de ciertas condiciones en un intento. para eliminar o reducir movimientos obviamente malos (movimientos históricos) o para investigar nodos interesantes (por ejemplo, verificar extensiones, peones pasados en el séptimo rango , etc.). Sin embargo, los activadores de extensión y poda deben usarse con mucho cuidado. Si se extiende demasiado, el programa pierde demasiado tiempo buscando posiciones poco interesantes. Si se poda demasiado, existe el riesgo de cortar nodos interesantes. Los programas de ajedrez difieren en términos de cómo y qué tipos de reglas de poda y extensión se incluyen, así como en la función de evaluación. Se cree que algunos programas son más selectivos que otros (por ejemplo, se sabía que Deep Blue era menos selectivo que la mayoría de los programas comerciales porque podían permitirse realizar búsquedas de ancho completo más completas), pero todos tienen una búsqueda básica de ancho completo como base y todos tienen algunos componentes selectivos (Q-search, poda / extensiones).
Aunque tales adiciones significaron que el programa no examinó realmente todos los nodos dentro de su profundidad de búsqueda (por lo que no sería realmente fuerza bruta en ese sentido), se encontró que los raros errores debidos a estas búsquedas selectivas valieron la pena el tiempo extra que ahorró porque podría buscar más profundamente. De esa manera, los programas de ajedrez pueden obtener lo mejor de ambos mundos.
Buscar heurísticas y otras optimizaciones
Se pueden usar muchas otras optimizaciones para fortalecer los programas de juego de ajedrez. Por ejemplo, las tablas de transposición se utilizan para registrar posiciones que se han evaluado previamente, para guardar el recálculo 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 prueban primero en posiciones variantes (ya que un movimiento que refuta una posición probablemente refuta otra). El inconveniente es que las tablas de transposición en capas profundas pueden llegar a ser bastante grandes, de decenas a cientos de millones de entradas. La tabla de transposición Deep Blue de IBM en 1996, por ejemplo, era de 500 millones de entradas. Las tablas de transposición que son demasiado pequeñas pueden hacer que se pierda más tiempo buscando entradas inexistentes debido a la trilla que el tiempo ahorrado por las entradas encontradas. Muchos motores de ajedrez usan la reflexión , buscando niveles más profundos en el tiempo del oponente, similar a los seres humanos, para aumentar su fuerza de juego.
Los programas de ajedrez modernos generalmente emplean una variedad de extensiones y reducciones independientes del dominio, buscando algunos nodos a profundidad arbitraria mientras buscan otros a profundidad reducida dependiendo de la configuración y el historial de movimientos en el árbol. Esto contrasta con la búsqueda selectiva o la poda hacia adelante de la era temprana: todos los movimientos se buscan con cierta profundidad; Los nodos se podan solo sobre la base de lo que se encuentra, en lugar de de forma preventiva aplicando conocimientos de ajedrez específicos del dominio.
Por supuesto, un hardware más rápido y una memoria adicional pueden mejorar la fuerza de juego del programa de ajedrez. Las arquitecturas con hiperproceso pueden mejorar el rendimiento modestamente 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 en paralelo. Otros programas están diseñados para ejecutarse en una computadora de propósito general y asignar generación de movimiento, búsqueda paralela o evaluación a procesadores dedicados o coprocesadores especializados.
Conocimiento versus búsqueda (velocidad del procesador)
En la década de 1970, la mayoría de los programas de ajedrez se ejecutaban en supercomputadoras como Control Data Cyber 176s o Cray-1s, lo que indica que durante ese período de desarrollo del ajedrez por computadora, 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 de cincuenta a setenta puntos Elo en fuerza de juego ( Levy y Newborn 1991 : 192).
Evaluación de hojas
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 los diferentes programas de ajedrez.
Las funciones de evaluación suelen evaluar las posiciones en centésimas de peón (llamado centipawn) y consideran el valor material junto con otros factores que afectan la fuerza de cada lado. Al contar el material de cada lado, los valores típicos de 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 el valor relativo de la pieza de ajedrez .) El rey a veces recibe un valor alto arbitrario, como 200 puntos ( papel de Shannon ) para asegurarse de que un jaque mate supere a todos los demás factores ( Levy y Newborn 1991 : 45). Por convención, una evaluación positiva favorece a las blancas y una evaluación negativa favorece a las negras.
Además de los puntos por piezas, la mayoría de las funciones de evaluación 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. Se suele considerar la protección de los reyes, así como la fase del juego (apertura, medio o final).
El resultado de la función de evaluación es un escalar único, cuantificado en centipawns u otras unidades, que es una suma ponderada de los diversos factores descritos. 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, se compara una evaluación con evaluaciones de otras hojas, eliminando los nodos que representan movimientos malos o malos para cada lado, para obtener un nodo que por convergencia, representa el valor de la posición con mejor juego de ambos lados.
No existe un marco analítico o teórico sobre lo que debe contener la función de evaluación. Tampoco es completamente ad hoc. Decenas a cientos de factores individuales se aglomeran en una constante.
Bases de tablas de finales
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 búsqueda necesaria. Algunos programas de nivel maestro no pudieron ganar en posiciones en las que incluso los jugadores humanos intermedios podían forzar una victoria.
Para resolver este problema, se han utilizado computadoras para analizar completamente algunas posiciones de finales de ajedrez , comenzando con rey y peón contra rey. Dichas tablas de finales se generan de antemano mediante una forma de análisis retrógrado , comenzando con las posiciones en las que se conoce el resultado final (p. Ej., Donde se ha emparejado un lado) y viendo qué otras posiciones están a un movimiento de ellas, luego cuáles son un movimiento. de esos, 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 la mesa de finales para un rey y una torre contra un rey y una reina y pudo dibujar ese final teóricamente perdido contra varios maestros (ver la posición de Philidor # Reina contra torre ). Esto fue a pesar de no seguir la estrategia habitual para 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 devolvió 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 2 horas y media para jugar cincuenta movimientos, de lo contrario se reclamaría un empate bajo la regla de los cincuenta movimientos . Después de cuarenta y cinco movimientos, Browne acordó un empate, no pudiendo forzar 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 del juego 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 la quincuagésima jugada, dándole una posición ganadora ( Levy & Newborn 1991 : 144–48), ( Nunn 2002 : 49).
Otras posiciones, que durante mucho tiempo se creyeron ganadas, resultaron necesitar más movimientos contra el juego perfecto para ganar de lo que permitía la regla de los cincuenta movimientos del ajedrez. Como consecuencia, durante algunos años se cambiaron las reglas oficiales de ajedrez de la FIDE 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 complica 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 . Están disponibles bases de mesa para todas las posiciones con seis piezas. [26] Marc Bourzutschky y Yakov Konoval han analizado algunos finales de siete piezas. [27] 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 contra un solo rey negro ). [28] [29] En todas estas bases de datos de finales se asume que el enroque ya no es posible.
Muchas tablas no consideran la regla de los cincuenta movimientos, según la cual un juego en el que pasan cincuenta movimientos sin una captura o un movimiento de peón puede ser considerado un empate por cualquiera de los jugadores. Esto da como resultado que la base de la tabla devuelva resultados como "Mate forzado en sesenta y seis movimientos" en algunas posiciones que en realidad se dibujarían debido a la regla de los cincuenta movimientos. Una razón para esto es que si las reglas del ajedrez fueran cambiadas una vez más, dando más tiempo para ganar tales posiciones, no será necesario regenerar todas las tablas. También es muy fácil para el programa que usa las tablas de base darse cuenta y tener en cuenta esta 'característica' y, en cualquier caso, si usa una base de tablas de finales, elegirá el movimiento que conduce a la victoria más rápida (incluso si faltaría a los cincuenta puntos). -move la regla con juego perfecto). Si juega contra un oponente que no usa una base de mesa, tal elección le dará buenas posibilidades de ganar dentro de cincuenta movimientos.
Las bases de tabla de 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 necesitan aproximadamente 1,2 TB . Se estima que una base de mesa de siete piezas requiere entre 50 y 200 TB de espacio de almacenamiento. [30]
Las bases de datos de Endgame aparecieron de manera destacada en 1999, cuando Kasparov jugó un partido de exhibición en Internet contra el resto del mundo . Se alcanzó un final de reina y peón de siete piezas con el Equipo Mundial luchando para salvar un empate. Eugene Nalimov ayudó al generar la base de la mesa final de seis piezas donde ambos lados tenían dos reinas que se usó mucho para ayudar en el análisis de ambos lados.
Libro de apertura
Los motores de ajedrez, al igual que los seres humanos, pueden ahorrar tiempo de procesamiento y seleccionar variaciones fuertes como las expuestas por los maestros, haciendo referencia a un libro de aperturas almacenado en una base de datos de disco. Los libros de apertura cubren los movimientos de apertura de un juego con una profundidad variable, dependiendo de la apertura y la variación, pero generalmente hasta los primeros 10-12 movimientos (20-24 capas). Dado que las aperturas han sido estudiadas en profundidad por los maestros durante siglos, y algunas se conocen bien en el medio del juego, las valoraciones de variaciones específicas por parte de los maestros serán generalmente superiores a las heurísticas generales del programa.
Mientras que en algún momento, jugar un movimiento fuera del libro para poner el programa de ajedrez en sus propios recursos podría haber sido una estrategia efectiva porque los libros de apertura 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 bases de datos informáticas son probablemente mucho más extensos que incluso los humanos mejor preparados, y jugar un movimiento temprano fuera del libro puede resultar en que la computadora encuentre el movimiento inusual en su libro y cargue al oponente con un movimiento brusco. desventaja. Incluso si no es así, jugar fuera del libro puede ser mucho mejor para los programas de ajedrez tácticamente agudos que para los humanos que tienen que descubrir movimientos fuertes en una variación desconocida sobre el tablero.
Listas de clasificación de ajedrez por computadora
CEGT , [31] CSS , [32] SSDF , [33] y WBEC [34] mantienen listas de clasificación que permiten a los aficionados comparar la potencia de los motores. Varias versiones de Stockfish, Komodo y Houdini dominan la lista de clasificación IPON a finales de la década de 2010.
CCRL (Computer Chess Rating Lists) es una organización que prueba la fuerza de los motores de ajedrez informático al jugar 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. [35]
La organización ejecuta tres listas diferentes: 40/40 (40 minutos por cada 40 jugadas jugadas), 40/4 (4 minutos por cada 40 jugadas jugadas) y 40/4 FRC (mismo control de tiempo pero Chess960). [Nota 1] 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 apertura 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 hombres . [35] [36] [37]
Historia
La era anterior a la informática
La idea de crear una máquina de jugar al ajedrez se remonta al siglo XVIII. Alrededor de 1769, el autómata ajedrecista llamado El Turco , se hizo famoso antes de ser denunciado como un engaño. Antes del desarrollo de la computación digital , los ensayos serios basados en autómatas como El Ajedrecista de 1912, 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.
Edad temprana del software: búsqueda selectiva
Desde entonces, los entusiastas del ajedrez y los ingenieros informáticos han construido, con grados crecientes de seriedad y éxito, máquinas para jugar al ajedrez y programas informáticos. Uno de los pocos grandes maestros del ajedrez que se dedicó seriamente al ajedrez por computadora fue el ex campeón mundial de ajedrez Mikhail Botvinnik , quien escribió varios trabajos sobre el tema. También tenía un doctorado en ingeniería eléctrica. 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 de software; en ese momento, solo las computadoras más poderosas podían lograr mucho más allá de 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 computadora entre Estados Unidos y la Unión Soviética (ver Kotok-McCarthy ).
La última era del software: búsqueda de ancho completo
Un hito en el desarrollo ocurrió cuando el equipo de la Universidad de Northwestern , que era responsable de la serie de programas de Ajedrez y ganó los primeros tres Campeonatos de Ajedrez por Computadora ACM (1970-72), abandonó la búsqueda de tipo B en 1973. El programa resultante, Ajedrez 4.0, ganó el campeonato de ese año y sus sucesores pasaron a quedar en segundo lugar tanto en el Campeonato ACM 1974 como en el Campeonato Mundial de Ajedrez Informático inaugural de ese año , antes de volver a ganar el Campeonato ACM en 1975, 1976 y 1977. La implementación de tipo A resultó ser tan rápido: en el tiempo que solía tomar para 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.
El auge de las máquinas de ajedrez
En 1978, una versión temprana de la máquina de ajedrez de hardware de Ken Thompson, Belle , participó y ganó el Campeonato de ajedrez informático norteamericano sobre el dominante Northwestern University Chess 4.7.
La revolución de la microcomputadora
Los avances tecnológicos por ó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 con la ayuda de 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ó producir excelentes resultados, al menos en el campo del ajedrez, al permitir que las computadoras hicieran lo que mejor saben hacer (calcular) en lugar de persuadirlos para que imiten 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, marcando la primera vez que una computadora derrota a un actual campeón mundial de ajedrez en control de tiempo estándar.
Ajedrez sobrehumano
En 2016, NPR pidió a los expertos que caracterizaran el estilo de juego de los motores de ajedrez por computadora. Murray Campbell de IBM declaró que "las computadoras no tienen ningún sentido de la estética ... Juegan lo que creen que es la mejor jugada objetivamente en cualquier posición, incluso si parece absurda, y pueden realizar cualquier jugada sin importar lo feo que sea. es." Los grandes maestros Andrés Soltis y Susan Polgar afirmaron que las computadoras tienen más probabilidades de retroceder que los humanos. [22]
La próxima generación: redes neuronales y búsqueda de árboles de montecarlo
El programa AlphaZero utiliza una variante de búsqueda de árbol de Monte Carlo sin implementación. [38] La Royal Society 's Venki Ramakrishnan señala que con Deep Blue ", podríamos decir que los programas vencedoras fueron diseñados con algoritmos (ajedrez) en base a nuestra propia comprensión - utilizando, en este caso, la experiencia y el asesoramiento de la parte superior gran masters ... (Deep Blue) era solo una máquina tonta ... (Pero con AlphaZero), esa forma de programación está cambiando dramáticamente ". [39] AlphaZero ha revolucionado el ajedrez informático, hasta el punto de que todos los participantes de la Primera División de la Temporada 20 del TCEC, excepto los que ocuparon el último lugar, utilizaron una función de evaluación basada en redes neuronales.
Cronología
- 1769 - Wolfgang von Kempelen construye el Turk . Presentado como un autómata que juega al ajedrez, es operado en secreto por un jugador humano escondido dentro de la máquina.
- 1868 - Charles Hooper presenta el autómata Ajeeb , que también tiene un jugador de ajedrez humano escondido en su interior.
- 1912 - Leonardo Torres y Quevedo construye El Ajedrecista , una máquina que podría jugar finales de Rey y Torre contra Rey .
- 1941 - Con anterioridad a un trabajo comparable en al menos una década, Konrad Zuse desarrolla algoritmos de ajedrez informático en su formalismo de programación Plankalkül . Sin embargo, debido a las circunstancias de la Segunda Guerra Mundial, no se publicaron y no salieron a la luz hasta la década de 1970.
- 1948 - El libro Cybernetics de Norbert Wiener describe cómo se podría desarrollar un programa de ajedrez usando una búsqueda minimax de profundidad limitada con una función de evaluación .
- 1950 - Claude Shannon publica "Programación de una computadora para jugar al ajedrez", uno de los primeros artículos sobre los métodos algorítmicos del ajedrez por computadora.
- 1951 - Alan Turing es el primero en publicar un programa, desarrollado en papel, que era capaz de jugar una partida completa de ajedrez (apodado Turochamp ). [40] [41]
- 1952 - Dietrich Prinz desarrolla un programa que resuelve problemas de ajedrez.
a | B | C | D | mi | F | |||
6 | 6 | |||||||
5 | 5 | |||||||
4 | 4 | |||||||
3 | 3 | |||||||
2 | 2 | |||||||
1 | 1 | |||||||
a | B | C | D | mi | F |
- 1956 - El ajedrez de Los Alamos es el primer programa para jugar un juego similar al ajedrez, desarrollado por Paul Stein y Mark Wells para la computadora MANIAC I.
- 1956 - John McCarthy inventa el algoritmo de búsqueda alfa-beta .
- 1957 - Se desarrollan los primeros programas que pueden jugar una partida completa de ajedrez, uno de Alex Bernstein [42] y otro de programadores rusos que utilizan un BESM .
- 1958 - NSS se convierte en el primer programa de ajedrez en utilizar el algoritmo de búsqueda alfa-beta.
- 1962 - Se publica en el MIT el primer programa en jugar de manera creíble, Kotok-McCarthy .
- 1963 - El gran maestro David Bronstein derrota a un M-20 que ejecuta un programa de ajedrez temprano. [43]
- 1966–67 - Se juega la primera partida de ajedrez entre programas de computadora. El Instituto de Física Teórica y Experimental de Moscú (ITEP) derrota a Kotok-McCarthy en la Universidad de Stanford por telégrafo durante nueve meses.
- 1967 - Mac Hack VI , por Richard Greenblatt et al. introduce tablas de transposición y emplea docenas de heurísticas de selección de movimientos cuidadosamente ajustadas; se convierte en el primer programa en derrotar a una persona en un torneo. Mac Hack VI jugó sobre el nivel de clase C.
- 1968 - El campeón de ajedrez escocés David Levy hace una apuesta de 500 libras con los pioneros de la IA, John McCarthy y Donald Michie, a que ningún programa de computadora ganaría una partida de ajedrez contra él en 10 años.
- 1970 - Monty Newborn y la Association for Computing Machinery organizan el primer campeonato norteamericano de ajedrez informático en Nueva York.
- 1971 - Ken Thompson , un informático estadounidense en Bell Labs y creador del sistema operativo Unix, escribe su primer programa de juego de ajedrez llamado "ajedrez" para la primera versión de Unix . [44]
- 1974 - David Levy , Ben Mittman y Monty Newborn organizan el primer Campeonato Mundial de Ajedrez Informático que gana el programa ruso Kaissa .
- 1975 - Después de casi una década de progreso marginal desde la marca máxima del MacHack VI de Greenblatt en 1967, se presenta Northwestern University Chess 4.5 con búsqueda de ancho completo e innovaciones de bitboards y profundización iterativa. También restableció una tabla de transposición como se vio por primera vez en el programa de Greenblatt. Por lo tanto, fue el primer programa con una estructura moderna integrada y se convirtió en el modelo para todo el desarrollo futuro. Chess 4.5 jugó fuerte clase B y ganó el 3er Campeonato Mundial de Ajedrez Informático ese año. El ajedrez de la Universidad Northwestern y sus descendientes dominaron el ajedrez por computadora hasta la era de las máquinas de ajedrez de hardware a principios de los 80.
- 1976 - En diciembre, el programador canadiense Peter R. Jennings lanza Microchess , el primer juego para microcomputadoras que se vende. [45]
- 1977 - En marzo, Fidelity Electronics lanza Chess Challenger , la primera computadora dedicada al ajedrez que se vende. La Asociación Internacional de Ajedrez Informático es fundada por programadores de ajedrez para organizar campeonatos de ajedrez informático e informar sobre la investigación y los avances en el ajedrez informático en su diario. También ese año, Applied Concepts lanzó Boris , una computadora de ajedrez dedicada en una caja de madera con piezas de ajedrez de plástico y un tablero plegable.
- 1978 - David Levy gana la apuesta realizada 10 años antes, derrotando a Chess 4.7 en una partida de seis juegos por una puntuación de 4½ – 1½. La victoria de la computadora en el cuarto juego es la primera derrota de un maestro humano en un torneo. [10]
- 1979 - Frederic Friedel organiza un partido entre el MI David Levy y Chess 4.8 , que se transmite por la televisión alemana. Levy y Chess 4.8, que se ejecutaban en un CDC Cyber 176, la computadora más poderosa del mundo, luchó contra un agotador empate de 89 movimientos.
- 1980 - Las computadoras Fidelity ganan el Campeonato Mundial de Microcomputadoras cada año desde 1980 hasta 1984. En Alemania, Hegener & Glaser lanzan su primera computadora de ajedrez dedicada a Mephisto . La USCF prohíbe que las computadoras compitan en torneos humanos, excepto cuando estén representadas por los creadores de los sistemas de ajedrez. [46] Se establece el Premio Fredkin, que ofrece $ 100,000 al creador de la primera máquina de ajedrez que derrote al campeón mundial de ajedrez.
- 1981 - Cray Blitz gana el Campeonato Estatal de Mississippi con una puntuación perfecta de 5-0 y una calificación de rendimiento de 2258. En la ronda 4 derrota a Joe Sentef (2262) para convertirse en la primera computadora en vencer a un maestro en torneos y la primera computadora en obtener una calificación de maestro.
- 1984 - La línea Mephisto de computadoras dedicadas al ajedrez de la compañía alemana Hegener & Glaser comienza una larga racha de victorias (1984-1990) en el Campeonato Mundial de Microcomputadoras utilizando computadoras dedicadas que ejecutan los programas ChessGenius y Rebel .
- 1986 - Software Country (ver Software Toolworks ) lanzó Chessmaster 2000 basado en un motor de David Kittinger, la primera edición de lo que se convertiría en la línea de programas de ajedrez más vendida del mundo.
- 1987 - Frederic Friedel y el físico Matthias Wüllenweber fundan Chessbase , lanzando el primer programa de base de datos de ajedrez. Stuart Cracraft lanza GNU Chess , uno de los primeros ' motores de ajedrez ' que se incluye con una interfaz gráfica de usuario (GUI) separada, chesstool. [47]
- 1988 - HiTech , desarrollado por Hans Berliner y Carl Ebeling , gana un partido contra el gran maestro Arnold Denker por 3½ – ½. Deep Thought comparte el primer lugar con Tony Miles en el Software Toolworks Championship, por delante del ex campeón mundial Mikhail Tal y varios grandes maestros como Samuel Reshevsky , Walter Browne y Mikhail Gurevich . También derrota al gran maestro Bent Larsen , convirtiéndolo en la primera computadora en vencer a un DJ en un torneo. Su calificación de desempeño en este torneo de 2745 (escala USCF) fue la más alta obtenida por un jugador de computadora. [48] [49]
- 1989 - Deep Thought derriba a David Levy en un partido de 4 juegos 0–4, poniendo fin a su famosa serie de apuestas que comenzó en 1968.
- 1990 - El 25 de abril, el ex campeón mundial Anatoly Karpov perdió en una simultánea contra la computadora de ajedrez Mephisto Portorose M68030 de Hegener & Glaser. [50]
- 1991 - La ChessMachine basada en Rebel de Ed Schröder gana el Campeonato Mundial de Ajedrez de Microcomputadoras
- 1992 - ChessMachine gana el séptimo campeonato mundial de ajedrez informático , la primera vez que un microordenador vence a los mainframes . El GM John Nunn publica Secrets of Rook Endings , el primer libro basado en tablas de finales desarrolladas por Ken Thompson .
- 1993 - Deep Thought-2 pierde un partido de cuatro juegos contra Bent Larsen . Los programas de ajedrez que se ejecutan en computadoras personales superan a las computadoras de ajedrez dedicadas de Mephisto para ganar el Campeonato de Microcomputadoras, marcando un cambio de hardware de ajedrez dedicado a software en computadoras personales multipropósito.
- 1995 - Fritz 3 , que se ejecuta en una PC Pentium de 90Mhz, supera a la máquina de ajedrez dedicada Deep Thought-2 y a los programas que se ejecutan en varias supercomputadoras, para ganar el 8º Campeonato Mundial de Ajedrez Informático en Hong Kong. Esta es la primera vez que un programa de ajedrez que se ejecuta en hardware básico derrota a las máquinas de ajedrez especializadas y supercomputadoras masivas, lo que indica un cambio en el énfasis del poder computacional bruto a las mejoras algorítmicas en la evolución de los motores de ajedrez.
- 1996 - Deep Blue de IBM pierde un partido de seis juegos contra Garry Kasparov , 2-4.
- 1997 - Deep (er) Blue , una versión altamente modificada del original, gana una partida de seis juegos contra Garry Kasparov , 3.5-2.5.
- 2000 - Stefan Meyer-Kahlen y Rudolf Huber redactaron la Interfaz Universal de Ajedrez , un protocolo para que las GUI se comunicaran con los motores que gradualmente se convertiría en la forma principal que adoptarían los nuevos motores.
- 2002 - Vladimir Kramnik empata un partido de ocho juegos contra Deep Fritz .
- 2003 - Kasparov empata una partida de seis juegos contra Deep Junior y empata una partida de cuatro contra X3D Fritz .
- 2004 - un equipo de computadoras ( Hydra , Deep Junior y Fritz ) gana 8½ – 3½ contra un equipo humano fuerte formado por Veselin Topalov , Ruslan Ponomariov y Sergey Karjakin , quienes tenían una calificación Elo promedio de 2681. Fabien Letouzey publica el código fuente de Fruit 2.1, un motor bastante competitivo con los mejores motores de fuente cerrada de la época. Esto lleva a muchos autores a revisar su código, incorporando las nuevas ideas.
- 2005 - Rybka gana el torneo IPCCC y rápidamente se convierte en el motor más potente . [51]
- 2006 - El campeón del mundo, Vladimir Kramnik , es derrotado 4-2 por Deep Fritz .
- 2009 - Pocket Fritz . 4 corriendo en un teléfono inteligente, gana la Copa Mercosur, un torneo internacional de nivel Master, con una puntuación de 9½ / 10 y una calificación de rendimiento de 2900. [19] Un grupo de programadores rusos seudónimos publica el código fuente de Ippolit, un motor aparentemente más fuerte que Rybka. . Esto se convierte en la base de los motores Robbolito e Ivanhoe, y muchos autores de motores adoptan ideas de él.
- 2010 - Antes del Campeonato Mundial de Ajedrez 2010 , Topalov se prepara luchando contra la supercomputadora Blue Gene con 8.192 procesadores capaces de realizar 500 billones (5 × 10 14 ) de operaciones de punto flotante por segundo. [52] El desarrollador de Rybka, Vasik Rajlich , acusa a Ippolit de ser un clon de Rybka.
- 2011 - La ICGA despoja a Rybka de sus títulos WCCC. [53] [54]
- 2017 - AlphaZero , un autómata digital basado en redes neuronales, vence a Stockfish 28-0, con 72 empates, en una partida de 100 juegos.
- 2019 - Leela Chess Zero (LCZero v0.21.1-nT40.T8.610), un motor de ajedrez basado en AlphaZero, derrota a Stockfish 19050918 en una partida de 100 juegos con una puntuación final de 53.5 a 46.5 para ganar la temporada 15 de TCEC . [55]
Categorizaciones
Hardware dedicado
Estos sistemas de juego de ajedrez incluyen hardware personalizado con aprox. fechas de introducción (excluidas las microcomputadoras dedicadas):
- Belle 1976
- Bebe, un potente procesador de trozos de bits 1980
- HiTech 1985
- ChipTest 1985
- Pensamiento profundo 1987
- Deep Thought 2 (prototipo de Deep Blue) ~ 1994
- Azul profundo 1996, 1997
- Hydra , su predecesora se llamaba Brutus 2002
- AlphaZero 2017 (usó las unidades de procesamiento de tensor de Google para redes neuronales, pero el hardware no es específico para ajedrez o juegos)
- MuZero 2019 (hardware similar a su predecesor AlphaZero, no específico de Ajedrez o, por ejemplo, Go), aprende las reglas del Ajedrez
Computadoras dedicadas comerciales
A finales de la década de 1970 y principios de la de 1990, existía un mercado competitivo para las computadoras dedicadas al ajedrez. Este mercado cambió a mediados de los 90 cuando las computadoras con procesadores dedicados ya no podían competir con los procesadores rápidos en las computadoras personales.
- Boris en 1977 y Boris Diplomat en 1979, computadoras de ajedrez que incluyen piezas y tablero, vendidas por Applied Concepts Inc.
- Chess Challenger, una línea de computadoras de ajedrez vendidas por Fidelity Electronics de 1977 a 1992. [56] Estos modelos ganaron los primeros cuatro Campeonatos Mundiales de Ajedrez de Microcomputadoras . [ cita requerida ]
- ChessMachine , una computadora dedicada basada en ARM , que podría ejecutar dos motores:
- "The King", que más tarde se convirtió en el motor Chessmaster , también se usó en la computadora dedicada TASC R30.
- Gideon, una versión de Rebel , en 1992 se convirtió en la primera microcomputadora en ganar el Campeonato Mundial de Ajedrez Informático . [57]
- Excalibur Electronics vende una línea de unidades de fuerza para principiantes.
- Mephisto , una línea de computadoras de ajedrez vendida por Hegener & Glaser. Las unidades ganaron seis Campeonatos Mundiales de Ajedrez de Microcomputadoras consecutivas . [ cita requerida ]
- Novag vendió una línea de computadoras tácticamente fuertes, incluidas las marcas Constellation, Sapphire y Star Diamond.
- Phoenix Chess Systems fabrica unidades de edición limitada basadas en procesadores StrongARM y XScale que ejecutan motores modernos y emulan motores clásicos.
- Saitek vende unidades de rango medio de resistencia intermedia. Compraron Hegener & Glaser y su marca Mephisto en 1994.
Recientemente, algunos aficionados han estado usando Multi Emulator Super System para ejecutar los programas de ajedrez creados para Fidelity o las computadoras Mephisto de Hegener & Glaser en sistemas operativos modernos de 64 bits como Windows 10 . [58] 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. [59]
Programas de DOS
Estos programas se pueden ejecutar en MS-DOS y en Windows 10 de 64 bits mediante emuladores como DOSBox o Qemu : [60]
- Maestro de ajedrez 2000
- Ajedrez Coloso
- Fritz 1–3
- Gambito de Kasparov
- Rebelde
- Sargón
- Sócrates II
Teóricos notables
Entre los teóricos del ajedrez informático conocidos se incluyen:
- Georgy Adelson-Velsky , matemático e informático soviético e israelí
- Hans Berliner , informático estadounidense y campeón mundial de ajedrez por correspondencia, supervisor de diseño de HiTech (1988)
- Mikhail Botvinnik , ingeniero eléctrico soviético y campeón mundial de ajedrez, escribió Pioneer
- Alexander Brudno , científico informático ruso, elaboró por primera vez el algoritmo de poda alfabeta
- Feng-hsiung Hsu , el desarrollador principal de Deep Blue (1986-1997)
- El profesor Robert Hyatt desarrolló Cray Blitz y Crafty [61]
- Danny Kopec , profesor estadounidense de ciencias de la computación y maestro internacional de ajedrez, desarrolló la prueba Kopec-Bratko
- Alexander Kronrod , informático y matemático soviético
- Profesor Monroe Newborn , presidente del comité de ajedrez informático de la Association of Computing Machinery
- Claude E. Shannon , científico informático y matemático estadounidense
- Alan Turing , informático y matemático inglés
Resolviendo ajedrez
Las perspectivas de resolver completamente el ajedrez generalmente se consideran bastante remotas. Se conjetura ampliamente que no existe un método computacionalmente económico para resolver el ajedrez, incluso en el sentido muy débil de determinar con certeza el valor de la posición inicial, y de ahí la idea de resolver el ajedrez en el sentido más fuerte de obtener una descripción prácticamente utilizable de una posición inicial. La estrategia para un 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 la mejor jugada en una posición de ajedrez, ni siquiera que un buscador alfa-beta tradicional que se ejecuta en hardware informático actual no pueda resolver la posición inicial en una cantidad aceptable de hora. La dificultad para probar esto último radica en el hecho de que, si bien el número de posiciones del tablero que podrían ocurrir en el transcurso de una partida de ajedrez es enorme (del orden de al menos 10 43 [62] a 10 47 ), es difícil para 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 arbitrariamente grande de piezas en un tablero de ajedrez arbitrariamente grande) es EXPTIME-completo , [63] lo que significa que determinar el lado ganador en una posición arbitraria del ajedrez generalizado lleva probablemente un tiempo exponencial en el peor caso; sin embargo, este resultado teórico no da un límite inferior a la cantidad de trabajo requerido para resolver el ajedrez ordinario de 8x8.
Se solucionó el Minichess de Martin Gardner , jugado en un tablero de 5 × 5 con aproximadamente 10 18 posiciones posibles en el tablero; su valor de la teoría del juego es 1/2 (es decir, cualquiera de las partes puede forzar un empate), y se ha descrito la estrategia de forzar para lograr ese resultado.
También se ha avanzado desde el otro lado: a partir de 2012, se han resuelto los finales de 7 y menos piezas (2 reyes y hasta 5 piezas más).
Motores de ajedrez
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 siguiendo protocolos estandarizados como la Interfaz de ajedrez universal desarrollada por Stefan Meyer-Kahlen y Franz Huber o el Protocolo de comunicación del motor de ajedrez desarrollado por Tim Mann para GNU Chess y Winboard . Chessbase tiene su propio protocolo propietario, y en un momento Millennium 2000 tuvo otro protocolo utilizado para ChessGenius . Los motores diseñados para un sistema operativo y un protocolo pueden trasladarse a otros sistemas operativos o protocolos.
Aplicaciones web de ajedrez
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. [64] Esta fue probablemente una de las primeras aplicaciones web de ajedrez. Free Internet Chess Server siguió poco después con un cliente similar. [65] En 2004, la Federación Internacional de Ajedrez por Correspondencia abrió un servidor web para reemplazar su sistema basado en correo electrónico. [66] Chess.com comenzó a ofrecer Live Chess en 2007. [67] Chessbase / Playchess ha tenido durante mucho tiempo un cliente descargable y agregó un cliente basado en la web en 2013. [68]
Otra aplicación web popular es el entrenamiento de tácticas. El ahora desaparecido Chess Tactics Server abrió su sitio en 2006, [69] seguido por Chesstempo el año siguiente, [70] y Chess.com agregó su Entrenador de Tácticas en 2008. [71] Chessbase agregó una aplicación web de entrenamiento de tácticas en 2015. [ 72]
Chessbase puso su base de datos de juegos de ajedrez en línea en 1998. [73] Otra base de datos de juegos de ajedrez temprana fue Chess Lab, que comenzó en 1999. [74] 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 cambio, centrarse en su base de datos en línea a partir de 2002. [75]
Uno podría jugar contra el motor Shredder en línea desde 2006. [76] En 2015, Chessbase agregó una aplicación web Play Fritz, [77] así como My Games para almacenar los juegos. [78]
A partir de 2007, Chess.com ofreció el contenido del programa de formación Chess Mentor a sus clientes en línea. [79] Los mejores GM como Sam Shankland y Walter Browne han contribuido con lecciones.
Ver también
- Computadora Go
- Comprobadores informáticos
- Computadora Othello
- Shogi de la computadora
Notas
- ^ El primer número se refiere al número de movimientos que debe realizar cada motor, el segundo número se refiere al número de minutos asignados para realizar todos estos movimientos. El control de tiempo de repetición significa que el tiempo se pone a cero después de que se alcanza cada múltiplo de este número de movimientos. Por ejemplo, en un control de tiempo 40/4, cada motor tendría 4 minutos para hacer 40 movimientos, luego se asignarían 4 minutos nuevos para los siguientes 40 movimientos y así sucesivamente, hasta que se completara el juego.
Referencias
- ^ Sreedhar, Suhas. "¡Damas, resuelto!" . Espectro IEEE . Instituto de Ingenieros Eléctricos y Electrónicos.
- ^ https://pubmed.ncbi.nlm.nih.gov/22530382/
- ^ http://scid.sourceforge.net SCID.
- ^ [1] Archivado el 20 de agosto de 2008 en la Wayback Machine.
- ^ http://www.exachess.com ExaChess para Mac
- ^ http://kalab.com/pgnviewer/
- ^ https://www.facebook.com/chessstudioapp/
- ^ Simon, HA; Newell, A. (1958). "Resolución de problemas heurísticos: el próximo avance en la investigación de operaciones" (PDF) . Investigación operativa . 6 (1): 7. doi : 10.1287 / opre.6.1.1 . Consultado el 10 de febrero de 2018 .
- ^ a b c d e f g Hapgood, Fred (23 a 30 de diciembre de 1982). "Ajedrez informático ajedrez humano malo peor" . Nuevo científico . págs. 827–830 . Consultado el 22 de enero de 2015 .
- ^ a b c Douglas, JR (diciembre de 1978). "Ajedrez 4.7 frente a David Levy" . BYTE . pag. 84 . Consultado el 17 de octubre de 2013 .
- ^ Rebaño, Emil; Silverman, Jonathan (marzo de 1984). "SPOC / The Chess Master" . BYTE . págs. 288-294 . Consultado el 8 de septiembre de 2015 .
- ^ Stinson, Craig (enero de 1982). "Campeonato de ajedrez: juego de máquinas, observación de la gente" . Softline . pag. 6 . Consultado el 13 de julio de 2014 .
- ^ "Rebelde contra Anand" . Rebel.nl . Consultado el 3 de abril de 2010 .
- ^ "Noticias de ajedrez - Adams vs Hydra: Man 0.5 - Machine 5.5" . ChessBase.com . Consultado el 3 de abril de 2010 .
- ^ Una vez más, Machine Beats Human Champion at Chess New York Times, 5 de diciembre de 2006
- ^ "Una vez más, la máquina vence al campeón humano en el ajedrez" . The New York Times . 5 de diciembre de 2006 . Consultado el 30 de abril de 2010 .
- ^ Computer Chess: The Drosophila of AI 30 de octubre de 2002
- ^ El pensamiento profundo gana el premio intermedio Fredkin , Hans Berliner
- ^ a b "Pocket Fritz 4 gana la Copa Mercosur" . Chess.co.uk. Archivado desde el original el 30 de septiembre de 2011 . Consultado el 3 de abril de 2010 .
- ^ Stanislav Tsukrov, autor de Pocket Fritz. Pocket Fritz 4 busca menos de 20.000 posiciones por segundo.
- ^ "El campeón mundial de ajedrez Magnus Carlsen: 'La computadora nunca ha sido un oponente ' " . Deutsche Welle. 16 de abril de 2016 . Consultado el 26 de agosto de 2016 .
- ^ a b "20 años después, los humanos siguen sin rivalizar con las computadoras en el tablero de ajedrez" . NPR.org . 2016 . Consultado el 28 de junio de 2020 .
- ^ Lo que esto significa es que el ajedrez, como la mosca común de la fruta, es un paradigma simple, más accesible y familiar para experimentar con tecnología que puede usarse para producir conocimiento sobre otros sistemas más complejos.
- ^ Wheland, Norman D. (octubre de 1978). "Un tutorial de ajedrez por computadora" . BYTE . pag. 168 . Consultado el 17 de octubre de 2013 .
- ↑ ( Shannon 1950 )
- ^ Kirill Kryukov. "Bases de tablas de Endgame en línea" . Kirill-kryukov.com . Consultado el 3 de abril de 2010 .
- ^ "Diario de ajedrez abierto 301-320" . Xs4all.nl . Consultado el 3 de abril de 2010 .
- ^ http://tb7.chessok.com Sitio web de Lomonosov que permite al usuario registrado acceder a una base de tabla de 7 piezas y un foro con posiciones encontradas.
- ^ "¿Quién gana con esto? (Rompecabezas de ajedrez)" Una posición de ajedrez de ejemplo encontrada en la base de la mesa de ajedrez de Lomonosov.
- ^ Los tamaños de Rybka Lounge / Computer Chess / Tablebase, http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380 , 19 de junio de 2012
- ^ CEGT 40/20 , Chess Engines Grand Tournament , 12 de octubre de 2008, archivado desde el original el 1 de marzo de 2012 , consultado el 21 de octubre de 2008
- ^ Computerschach und Spiele - Eternal Rating , Computerschach und Spiele, 18 de marzo de 2007 , consultado el 21 de mayo de 2008
- ^ The SSDF Rating List , Swedish Chess Computer Association , 26 de septiembre de 2008 , consultado el 20 de octubre de 2008
- ^ BayesianElo Ratinglist de WBEC Ridderkerk , consultado el 20 de julio de 2008
- ↑ a b CCRL, http://www.computerchess.org.uk/ccrl/ , 19 de junio de 2012
- ^ Tablero de discusión CCRL, http://kirill-kryukov.com/chess/discussion-board/viewtopic.php?f=7&t=2808 , 19 de junio de 2012
- ↑ Adam's Computer Chess Pages, http://adamsccpages.blogspot.co.uk/2012/05/ccrl.html , 19 de junio de 2012
- ^ Silver, David; Hubert, Thomas; Schrittwieser, Julian; Antonoglou, Ioannis; Lai, Matthew; Guez, Arthur; Lanctot, Marc; Sifre, Laurent; Kumaran, Dharshan; Graepel, Thore; Lillicrap, Timothy; Simonyan, Karen; Hassabis, Demis (2017). "Dominar el ajedrez y el shogi por auto-juego con un algoritmo de aprendizaje de refuerzo general". arXiv : 1712.01815 [ cs.AI ].
- ^ " Venki Ramakrishnan : ¿Las computadoras se convertirán en nuestros señores?". Mentes posibles: veinticinco formas de ver la inteligencia artificial (Kindle ed.). Penguin Press. 2019. p. 174. ISBN 978-0525557999.
- ^ Ajedrez, una subsección del capítulo 25, Computadoras digitales aplicadas a juegos, de Más rápido que el pensamiento, ed. BV Bowden, Pitman, Londres (1953). En línea .
- ^ Un juego jugado por el algoritmo de ajedrez de Turing
- ^ "Chessville - primeros programas de ajedrez informático - por Bill Wall - Maravilloso mundo del ajedrez de Bill Wall" . Archive.is. Archivado desde el original el 21 de julio de 2012 . Consultado el 1 de diciembre de 2014 .CS1 maint: bot: estado de URL original desconocido ( enlace )
- ^ David Bronstein v M-20, repetición en Chessgames.com
- ^ Dennis Ritchie (junio de 2001). "Ken, Unix y Juegos" . Revista ICGA . 24 (2).
- ^ https://www.computerhistory.org/chess/orl-4334404555680/
- ^ "Nuevas restricciones" . BYTE . Enero de 1981. p. 292 . Consultado el 18 de octubre de 2013 .
- ^ https://web.cecs.pdx.edu/~trent/gnu/bull/02/nb.html#SEC6
- ^ Hsu (2002) p. 292
- ^ Recién nacido (1997) p. 159
- ^ Búsqueda selectiva. Junio de 1990
- ^ [2] Campeonato Internacional de Ajedrez Informático Paderborn 2005
- ^ "Challenger utiliza superordenador en el campeonato mundial de ajedrez" . Chessbase.
- ^ [3] Archivado el 30 de marzo de 2014 en la Wayback Machine.
- ^ Riis, Dr. Søren (2 de enero de 2012). "Un grave error judicial en el ajedrez informático (parte uno)" . Noticias de Chessbase . Consultado el 19 de febrero de 2012 .
- ^ https://cd.tcecbeta.club/archive.html?season=15&div=sf&game=1 TCEC temporada 15
- ^ Sousa, Ismenio. "Fidelity Chess Challenger 1 - Primera computadora de ajedrez del mundo" . Consultado el 25 de septiembre de 2016 .
- ^ https://research.tilburguniversity.edu/en/publications/the-7th-world-computer-chess-championship-report-on-the-tournamen
- ^ http://rebel13.nl/rebel13/rebel%2013.html
- ^ http://rebel13.nl/dedicated/dedicated%20as%20uci.html
- ^ http://rebel13.nl/download/more%20dos%20oldies.html
- ^ "Página de inicio del Dr. Robert Hyatt" . Cis.uab.edu. 2004-02-01 . Consultado el 3 de abril de 2010 .
- ^ El tamaño del espacio estatal y el árbol de juego para el ajedrez se estimaron por primera vez en Claude Shannon (1950), "Programming a Computer for Playing Chess" (PDF) , Philosophical Magazine , 41 (314), archivado desde el original (PDF) el 6 de julio de 2010 , consultado el 30 de diciembre de 2008Shannon dio estimaciones de 10 43 y 10 120 respectivamente, menores que las estimaciones en la tabla de complejidad del Juego , que son de la tesis de Victor Allis . Consulte el número de Shannon para obtener más detalles.
- ^ Aviezri Fraenkel; D. Lichtenstein (1981), "Calcular una estrategia perfecta para el ajedrez n × n requiere tiempo exponencial en n", J. Combin. Teoría Ser. A , 31 (2): 199–214, doi : 10.1016 / 0097-3165 (81) 90016-9
- ^ "Copia archivada" . Archivado desde el original el 20 de junio de 1997 . Consultado el 8 de julio de 2019 .CS1 maint: copia archivada como título ( enlace )
- ^ "Copia archivada" . Archivado desde el original el 12 de diciembre de 1998 . Consultado el 8 de julio de 2019 .CS1 maint: copia archivada como título ( enlace )
- ^ "Copia archivada" . Archivado desde el original el 31 de agosto de 2004 . Consultado el 31 de agosto de 2004 .CS1 maint: copia archivada como título ( enlace )
- ^ https://web.archive.org/web/20071006143047/http://www.chess.com/echess/
- ^ https://web.archive.org/web/20131217045511/http://play.chessbase.com/js/apps/playchess/
- ^ "Copia archivada" . Archivado desde el original el 8 de abril de 2006 . Consultado el 8 de abril de 2006 .CS1 maint: copia archivada como título ( enlace )
- ^ "Copia archivada" . Archivado desde el original el 13 de junio de 2007 . Consultado el 13 de junio de 2007 .CS1 maint: copia archivada como título ( enlace )
- ^ "Copia archivada" . Archivado desde el original el 18 de febrero de 2008 . Consultado el 18 de febrero de 2008 .CS1 maint: copia archivada como título ( enlace )
- ^ https://web.archive.org/web/20150504000924/http://training.chessbase.com/js/apps/Training/
- ^ https://web.archive.org/web/20000511014758/http://www.chessbase-online.com/
- ^ "Copia archivada" . Archivado desde el original el 19 de febrero de 1999 . Consultado el 8 de julio de 2019 .CS1 maint: copia archivada como título ( enlace )
- ^ "Copia archivada" . Archivado desde el original el 8 de octubre de 2002 . Consultado el 8 de octubre de 2002 .CS1 maint: copia archivada como título ( enlace )
- ^ "Copia archivada" . Archivado desde el original el 5 de diciembre de 2006 . Consultado el 5 de diciembre de 2006 .CS1 maint: copia archivada como título ( enlace )
- ^ http://fritz.chessbase.com/
- ^ http://mygames.chessbase.com/
- ^ "Copia archivada" . Archivado desde el original el 14 de diciembre de 2007 . Consultado el 14 de diciembre de 2007 .CS1 maint: copia archivada como título ( enlace )
Fuentes
- Hsu, Feng-hsiung (2002), Detrás de Deep Blue: Construyendo la computadora que derrotó al campeón mundial de ajedrez , Princeton University Press , ISBN 0-691-09065-3
- Levy, David ; Recién nacido, Monty (1991), Cómo las computadoras juegan al ajedrez , Computer Science Press, ISBN 0-7167-8121-2
- Newborn, Monty (1975), Computer Chess , Academic Press, Nueva York
- Newborn, Monty (1997), Kasparov versus Deep Blue: Computer Chess llega a la mayoría de edad , Springer, ISBN 0-387-94820-1 (Este libro en realidad cubre el ajedrez informático desde los primeros días hasta el primer partido entre Deep Blue y Garry Kasparov).
- Nunn, John (2002), Secretos de finales sin empeño , Publicaciones de Gambito , ISBN 1-901983-65-X
- Shannon, Claude E. (1950), "Programación de una computadora para jugar al ajedrez" (PDF) , Revista filosófica , Ser.7, Vol. 41 (314), archivado desde el original (PDF) el 6 de julio de 2010 , consultado el 21 de junio de 2009
- Dominar el juego: una historia del ajedrez informático en el Museo de Historia de la Computación
- Cronología de la historia del ajedrez informático de Bill Wall
Otras lecturas
- Nuevas arquitecturas en ajedrez informático: tesis sobre cómo construir un motor de ajedrez
- Coles, L. Stephen (30 de octubre de 2002), Computer Chess: The Drosophila of AI , Dr. Dobb's Journal
- Huberman (Liskov), Barbara Jane (1968), Un programa para jugar partidas de ajedrez , Departamento de Ciencias de la Computación de la Universidad de Stanford, Informe técnico CS 106, Memorando del proyecto de inteligencia artificial de Stanford AI-65
- Lasar, Matthew (2011). ¿Fuerza bruta o inteligencia? El lento ascenso del ajedrez informático ". Ars Technica .
- Recién nacido, Monty (1996). Outsearching Kasparov , Actas de simposios en matemáticas aplicadas de la American Mathematical Society: Aspectos matemáticos de la inteligencia artificial, v. 55, págs. 175-205, 1998. Basado en un documento presentado en la Reunión de Invierno de 1996 de la AMS, Orlando, Florida, 9 de enero - 11 de 1996.
- Recién nacido, Monty (2000). Contribución de Deep Blue a la IA , Annals of Mathematics and Artificial Intelligence, v. 28, págs. 27-30, 2000.
- Recién nacido, Monty (2006). Theo y Octopus en el Campeonato Mundial de Programas de Razonamiento Automatizado de 2006 , Seattle, Washington, 18 de agosto de 2006
- Stiller, Lewis (1996), Multilinear Algebra and Chess Endgames (PDF) , Berkeley, California: Mathematical Sciences Research Institute , Games of No Chance, MSRI Publications, Volumen 29 , consultado el 21 de junio de 2009
enlaces externos
- Lista de clasificaciones del motor de ajedrez y archivos de juego en formato PGN
- Dominar el juego: una historia del ajedrez informático en el Museo de Historia de la Computación
- Ajedrez informático ACM de Bill Wall
- "Computer Chess" de Edward Winter
- Información y recursos de ajedrez informático : blog sobre la creación de un motor de ajedrez informático
- Defending Humanity's Honor , un artículo de Tim Krabbé sobre el ajedrez "anti-estilo informático"
- Una guía para las bases de tablas de Endgame
- GameDev.net - Programación de ajedrez por François-Dominic Laramée Parte 1 2 3 4 5 6
- Página de teoría del ajedrez informático de Colin Frayn
- " " Cómo REBEL juega al ajedrez "por Ed Schröder" (PDF) . (268 KB)
- "Juega al ajedrez con Dios" : por jugar al ajedrez contra la base de datos de finales de Ken Thompson
- Wiki de programación de ajedrez
- Foros del Computer Chess Club
- Los motores de ajedrez informático más potentes a lo largo del tiempo
Medios de comunicación
- La historia del ajedrez informático: una perspectiva de la IA : una conferencia completa con Murray Campbell (IBM Deep Blue Project), Edward Feigenbaum, David Levy , John McCarthy y Monty Newborn. en el Museo de Historia de la Computación