Belle (máquina de ajedrez) - Belle (chess machine)
| Este artículo es parte de la serie sobre |
| Programación de ajedrez |
|---|
 |
| Representaciones de la junta |
| Computadoras de ajedrez |
| Motores de ajedrez |
Belle era una computadora de ajedrez desarrollada por Joe Condon (hardware) y Ken Thompson (software) en Bell Labs . En 1983, fue la primera máquina en lograr un juego de nivel maestro , con una calificación de USCF de 2250. Ganó el Campeonato de ajedrez informático norteamericano ACM cinco veces y el Campeonato mundial de ajedrez informático de 1980 . Fue el primer sistema en ganar usando hardware de ajedrez especializado.
En su encarnación final, Belle usó una computadora de propósito general LSI-11 para coordinar su hardware de ajedrez. Había tres tableros personalizados para la generación de movimientos, cuatro tableros personalizados para la evaluación de la posición y una implementación de microcódigo de poda alfa-beta . La computadora también tenía un megabyte de memoria comercial para almacenar tablas de transposición .
Al final de su carrera, Belle fue donada a la Institución Smithsonian . La arquitectura general de Belle se utilizó para los diseños iniciales de ChipTest , el progenitor de IBM Deep Blue .
Orígenes
Tras su trabajo en el sistema operativo Unix , Ken Thompson centró su atención en el ajedrez informático. En el verano de 1972, comenzó a trabajar en un programa para el PDP-11 , que eventualmente se convertiría en Belle. En competición, esta primera versión animó a Thompson a seguir un enfoque de fuerza bruta al diseñar el hardware de Belle.
Diseño
El diseño de Belle sufrió muchos cambios a lo largo de su vida. El programa de ajedrez inicial se reescribió para utilizar la búsqueda de quiescencia movimiento vs evaluación y evaluar posiciones priorizando la ventaja material . Belle también usó una tabla de transposición para evitar exámenes redundantes de posiciones.
Generador de movimiento de hardware
| un | segundo | C | re | mi | F | gramo | h | ||
| 8 |      |
8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| un | segundo | C | re | mi | F | gramo | h | ||
Belle representa un movimiento definiendo un cuadrado "desde" y un cuadrado "hasta", usando un contador de desplazamiento ∆xy. El movimiento de torre de arriba tiene un desplazamiento (2,0), mientras que el alfil es (2,2).
En 1976, Joe Condon implementó un generador de movimiento de hardware para ser utilizado con la versión de software de Belle en el PDP-11. Su diseño tuvo varios pasos:
- Una de 6 bits "de" registro busca en la tabla de piezas de amistosos.
- Una vez que se encuentra una pieza agradable, un Δxy movimiento-offset contador proporciona un código de bits para el movimiento de desplazamiento, por ejemplo, (2,2) para un obispo o (2,0) para una torre .
- Este desplazamiento se combina con el contenido del registro "desde" y se mueve a un registro "a" de 6 bits. Estos dos registros describen completamente un movimiento potencial .
- Un circuito de prueba compara el movimiento con el tablero existente para determinar si el movimiento es pseudolegal . Si es así, los registros "desde" y "hasta" se envían al software.
Una serie similar de pasos usa el generador de movimientos para probar si el movimiento pseudolegal es de hecho legal. Esto asegura que el movimiento no ponga el lado móvil bajo control .
Segunda generación
La segunda generación de Belle se completó en 1978. Implementó varias mejoras sobre su predecesor.
- El generador de movimientos tenía su propia pila , que utilizaba para almacenar movimientos, en lugar de enviarlos al software.
- Se agregó una implementación de hardware del evaluador de puestos.
- Una implementación de hardware de la memoria de transposición.
Estos cambios redujeron la función del software PDP-11. Ahora, el software controlaba estos tres dispositivos y ejecutaba el algoritmo de poda alfa-beta. La segunda generación de Belle podría buscar 5.000 posiciones por segundo.
Tercera generación
La encarnación final de Belle se completó en 1980. Consistió en mejoras adicionales en la velocidad de generación y evaluación de movimientos.
- El generador de movimiento ahora incluía 64 circuitos transmisores y receptores. Cada transmisor recordaba la pieza en su cuadrado y los movimientos potenciales que esa pieza podía hacer. Cada receptor detectó movimientos entrantes, o amenazas, de otras piezas. El circuito adicional detectó enroque y al paso.
- El evaluador ahora podría examinar el control de cuadrados, utilizando 64 circuitos especializados, así como la estructura de peones.
- La memoria de transposición se incrementó a 1 Mb.
- El algoritmo Alpha-beta de Belle ahora se implementó en microcódigo, controlando el generador de movimientos, el evaluador y la tabla de transposición.
La tercera generación de Belle estaba controlada por una computadora LSI-11. Dependiendo de la etapa del juego, examinó de 100.000 a 200.000 movimientos por segundo.
Carrera
Competiciones tempranas
La versión de software de Belle de Ken Thompson compitió en el Campeonato Abierto de Ajedrez de los Estados Unidos de 1972 y el Campeonato de Ajedrez por Computadora ACM de 1973. Durante el año siguiente, Belle jugó varios juegos de UCSF y terminó 3-1 en el Campeonato de Ajedrez de Computadora ACM de 1974.
En 1978, la segunda generación de Belle compitió en el ACM Computer Chess Championships, ganando con un perfecto 4/0. En una partida fundamental contra Chess 4.7 , la subcampeona, Belle examinó 5.000 posiciones por segundo, mientras que Chess 4.7 examinó 3.500.
Campeonato mundial
En 1980, la tercera generación de Belle ganó el tercer Campeonato Mundial de Ajedrez Informático en Linz, Austria. Después de cuatro rondas, tenía una puntuación de 3.5 / 4, empatado con la máquina de ajedrez Chaos . En un desempate por el título de campeón mundial, Belle rompió la Defensa Alekhine de Chaos y pasó a declarar jaque mate en el 8, ganando el juego en el turno 41. Durante el juego, Belle buscó 160.000 posiciones por segundo.
Calificación Master
En 1983, Belle compitió en el US Open, donde terminó 8.5 / 3.5 con una calificación de rendimiento de 2363. Más tarde ese año, la USCF otorgó a Belle el rango de maestra. Debido a que alcanzó este nivel antes que cualquier otra computadora de ajedrez, Belle recibió el premio Fredkin de $ 5,000. El reinado de Belle terminó cuando quedó sexta en el Cuarto Campeonato Mundial de Ajedrez Informático, a pesar de ser la favorita para ganar. Logró una victoria más en los Campeonatos de ACM en 1986 antes de retirarse.
Análisis de rendimiento
Debido a su capacidad para generar y analizar muchas posiciones de ajedrez, Belle representó el enfoque de fuerza bruta para la computación del ajedrez. A fines de la década de 1970, Thompson se interesó por los límites de este método, enfrentando diferentes versiones de Belle entre sí. El uso de máquinas idénticas le permitió minimizar los efectos del estilo de juego de la máquina individual al tiempo que aislaba los efectos de la profundidad de búsqueda . Por ejemplo, si una computadora Belle busca tres niveles de profundidad, la otra podría buscar hasta 4. Thompson concluyó que por cada nivel adicional de búsqueda, Belle mejoró aproximadamente 250 puntos. Este efecto se ha replicado en experimentos de auto-juego con diferentes máquinas. Sin embargo, más allá de los 2,000 puntos, Thompson descubrió que las mejoras se estabilizaron.
Ver también
- Ajedrez de computadora
- Glosario de términos de ajedrez informático
- Ken Thompson (programador de computadoras)
- Joseph Henry Condon
- Base de la mesa final
- Laboratorios Bell
- Fin de juego de ajedrez sin peones # Browne versus BELLE
Notas
Referencias
- Dennis Ritchie (junio de 2001). "Ken, Unix y Juegos" . Revista ICGA . 24 (2).
- Condon, JH y K. Thompson, "Belle Chess Hardware", In Advances in Computer Chess 3 (ed. MRBClarke), Pergamon Press, 1982.
- Museo de Historia de la Computación
- Levy, D .; Mittman, B .; Recién nacido, M. (1980). "3er Campeonato Mundial de Ajedrez Informático". Comunicaciones de la ACM . 23 (11): 661–664. ISSN 0001-0782 .
- Heinz, EA (2001). "Auto-juego, búsqueda profunda y rendimientos decrecientes - Ken Thompson". Revista ICGA . 24 (2): 75–79. doi : 10.3233 / ICG-2001-24205 . ISSN 1389-6911 .
- Condon, Joseph H .; Thompson, Ken (1983). "Capítulo 9: Bella". En Frey, Peter W. (ed.). Habilidad ajedrecística en hombre y máquina . Nueva York: Springer-Verlag. págs. 201–210. ISBN 978-0-387-90815-1.
- Recién nacido, Monroe. (1997). Kasparov contra Deep Blue: el ajedrez informático alcanza la mayoría de edad . Nueva York: Springer. ISBN 978-0-387-94820-1.