¿Cómo mejoraron los motores desde Deep Blue?

17

Los motores de ajedrez informáticos han mejorado desde que Deep Blue venció a Kasparov en 1997.

¿Los algoritmos mejoraron o las mejoras se debieron principalmente a que los mismos algoritmos se ejecutaron más rápido gracias a un hardware más rápido, etc.?

Si es lo primero, ¿son públicas estas mejoras algorítmicas?

Y si es así, ¿cuáles fueron las mejoras? ¿Dónde puedo leer sobre ellos?

MaxB
fuente
Cómo ? Dramáticamente.
Evargalo

Respuestas:

8

Tal vez puedas echar un vistazo a TalkChess , un foro dedicado al ajedrez informático. Encontré un hilo reciente que podría ser interesante para usted: progreso en 30 años por cuatro intervalos de 7-8 años

Un par de partidos entre los mejores motores (anteriores) se juegan en el mismo hardware . La prueba sugiere que en los últimos años (2002-2017), la ganancia se debe principalmente a las mejoras de software. En la prueba, Stockfish (2017) obtuvo un impresionante 94/100 contra RobboLito (2009), mientras que RobboLito, por su parte, aplastó a Shredder (2002) con 92/100.

Una observación importante: como la computación paralela no se implementa en los motores más antiguos, la prueba se realizó en un solo núcleo. Como resultado, no se mide la ganancia de hardware de las máquinas paralelas. Por otro lado, podría argumentar que la computación paralela también es una ganancia de software: no es fácil diseñar e implementar una paralelización eficiente y bien escalable para el algoritmo de búsqueda.

El motor Stockfish es de código abierto, por lo que las mejoras algorítmicas son públicas. Se puede encontrar mucha documentación en https://chessprogramming.wikispaces.com

Maxwell86
fuente
Esto responde a su afirmación. Intenta responder la pregunta la próxima vez.
Fred Knight
1
Bueno, creo que respondí la pregunta: la ganancia se debe principalmente a las mejoras del algoritmo. Además, mostré datos que respaldan esta afirmación (ver enlace) y señalé una posible deficiencia (no se midió la paralelización).
Maxwell86
3

No puedo hablar por el algoritmo utilizado para Deep Blue, pero voy a tratar de explicar las mejoras en la programación de ajedrez. La velocidad es la mayor mejora. Deep Blue usó computadoras dedicadas multiprocesador, por lo que una comparación no es realmente posible.

https://chessprogramming.wikispaces.com/ es una gran fuente, pero es difícil de navegar.

Hay 3 funciones principales que se modifican para mejorar un motor de ajedrez: las funciones de evaluación, generación de movimientos y búsqueda.

La evaluación es la más difícil de programar, ya que hay muchas excepciones a las reglas. Con el espacio del disco duro cada vez más barato, la función eval permite evaluar más excepciones.

La generación de movimientos, junto con hacer y deshacer un movimiento, consume mucha memoria porque tiene que formarse tantas veces. Las funciones de generación más comunes son buzón, bitboard, 0x88, 8x8, tableros extendidos (10x10, 10x12) y una matriz / tabla de movimientos predeterminada (* utilizo una tabla de movimientos indexados). La opinión actual es que los bitboards son los más rápidos, y el uso de bitboards mágicos acelera esto hasta en un 30%. El Dr. Robert Hyatt, profesor y creador del ingenioso motor de ajedrez, afirma que no hay un aumento significativo de la velocidad.

La función de búsqueda temprana eran las funciones primitivas min-max. Básicamente, ¿intentaste maximizar la puntuación del lado para moverte y minimizar la puntuación del oponente? Alpha-Beta fue la primera mejora. Redujeron el número de movimientos que se buscan por tabla de transposición, valores de corte, ventanas de aspiración y heurística del historial. Estas son búsquedas de profundidad primero. También existe la búsqueda interna de profundización iterativa que trata de buscar el "mejor" movimiento (s) con la más profunda esperanza de que la búsqueda de otros movimientos resulte infructuosa.

NOTA: Mi tabla de índice. GNUChess y Jester usan una matriz de índice para generar sus movimientos. Inicializan el motor llenando la matriz con posibles movimientos. Luego toman las seis piezas y calculan los movimientos legales que están disponibles en cada casilla. Entonces cada pieza tenía una matriz [64] [8]. Tomé esta idea y la comprimí en dos índices y una tabla. La tabla contiene un valor que indica si los 16 movimientos son posibles, un índice contiene el desplazamiento del movimiento y el otro contiene la máscara.

desplazamiento [] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};

máscara [] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};

Entonces, la generación de un movimiento deslizante es tan fácil como buscar la validez de su máscara en sus desplazamientos permitidos contra la tabla de movimientos.

Fred Knight
fuente
77
Intento no responder a las respuestas, pero esto es solo ... Alpha-beta y bitboards fueron inventados MUCHO antes de Deep Blue. También estoy bastante seguro de que la evaluación de la placa no accede a HD en ningún motor cuerdo (la latencia es ENORME). En cuarto lugar, soy muy escéptico de que el tamaño de la RAM haga una diferencia real en su implementación de búsqueda alfa-beta normal.
MaxB
¿Podría quizás agregar algunos hipervínculos a algunos de los conceptos que está discutiendo? Como alguien que está interesado en el concepto, pero no está familiarizado con la terminología, es difícil de seguir porque no sé qué es un bitboard o el motor Crafty Chess.
Thunderforge
Pensé que estaba claro en que no me estaba comparando con Deep Blue, pero estaba dando una breve historia. El disco duro al que me refería es el programa en sí. Cada vez que se incluye un nuevo concepto de evaluación en un motor de ajedrez, se requiere más código y, por lo tanto, más espacio en HD.
Fred Knight
@Thunderforge, el único enlace que proporcioné explica todos los aspectos que podrías desear en relación con la programación de ajedrez, sin embargo, admito que es difícil de navegar. Aprendí leyendo los códigos fuente de otros, pero el que está más comentado es el motor Crafty del Dr. Hyatt. Elijo no ser demasiado completo debido a las limitaciones de espacio y las diferencias entre plataformas y compiladores. Si, después de leer la página de ajedrez wiki, todavía está confundido, haga la pregunta y estoy seguro de que muchos le darán una mejor respuesta.
Fred Knight
1
Every time that a new eval concept in included into a chess engine, more code, and therefore more HD space is required.Las funciones de evaluación de la placa generalmente están diseñadas para caber en el caché de la CPU. Caché de la CPU << RAM << HD. El tamaño de HD no hace ninguna diferencia.
MaxB
2

¿Los algoritmos mejoraron?

Obviamente, sí un poco.

¿O las mejoras se debieron principalmente a que los mismos algoritmos se ejecutaron más rápido gracias a un hardware y software más rápidos?

Minor nit: si los algoritmos mejoraron, entonces ese es el software que mejora, así que no hay "o".

La Ley de Moore nos dice que la velocidad del procesador se duplicará aproximadamente cada 18 meses. Eso significa que se ha duplicado aproximadamente 13 veces en 20 años. Eso hace que los procesadores modernos en algún lugar de la región sean 8,000 veces más rápidos. Entonces, de lejos, la mayor mejora en el rendimiento del motor se debe a un hardware más rápido.

Si es lo primero, ¿son públicas estas mejoras algorítmicas?

Y si es así, ¿cuáles fueron las mejoras? ¿Dónde puedo leer sobre ellos?

Bueno, no fue lo primero, fue lo último. Sin embargo, las mejoras son en su mayoría de código abierto y libremente visibles al descargar las fuentes para motores como Stockfish . Quizás también valga la pena dar el enlace de descarga general de Stockfish ya que el enlace del código fuente específico probablemente caduque cuando salga la versión 9.

Brian Towers
fuente
2
That means it has doubled roughly 13 times in 20 years.Creo que estás citando mal la Ley de Moore. No dice nada sobre la velocidad del procesador. De hecho, no se ha duplicado en mucho tiempo.
MaxB
hardware and softwareMe refería al software como en la implementación del algoritmo (ASM vs C ++), pero puedo ver cómo es confuso. Fijo.
MaxB
1
La ley de Moore es correcta, excepto que incluye la frase "en la próxima década". Esto habría sido en 1975, y tenía razón.
Fred Knight
-1 porque la respuesta es incorrecta: en el mismo hardware, los motores actuales todavía aplastan a los motores que antes eran los mejores.
Allure
0

Se trata de algoritmos.

Enfrentarse a un jugador de ajedrez humano tomó una de las computadoras más poderosas del mundo en ese momento. Este enfoque de cálculo de fuerza bruta permitió a Deep Blue mirar alrededor de seis a ocho movimientos por delante. En una competencia muy reñida, la máquina finalmente derrotó a Kasparov por 3 1/2 juegos a 2 1/2.

Seis años después, Kasparov estuvo involucrado en otra competencia de hombre contra máquina. Esta vez jugó contra el sucesor de Deep Blue, Deep Junior. El resultado fue una serie dibujada en tres juegos todos. La mayor diferencia fue que Deep Junior funcionaba en una máquina con aproximadamente el uno por ciento de la potencia informática de Deep Blue. Los algoritmos de juego de ajedrez habían mejorado hasta el punto de lograr prácticamente el mismo resultado con un poder de cómputo cien veces menor.

David Hambling
fuente
44
¡Bienvenido a ajedrez! Escribiste la parte principal de tu respuesta como si fuera una cita; ¿podría por favor proporcionar una fuente?
Glorfindel
0

Descargo de responsabilidad: no es un experto.

Los algoritmos mejoraron, y los mejores motores de hoy en funcionamiento en 1995 (recuerden que Deep Blue era 1999) el hardware derrotará fácilmente a Kasparov. Según tengo entendido, hay dos aspectos de los algoritmos:

Buscar . Si, por ejemplo, llevo a tu reina con mi reina, un oponente humano automáticamente buscará primero la recaptura. Sin embargo, para una computadora, evaluará todas las respuestas posibles a QxQ. Casi todo el tiempo, esta es una energía de procesamiento desperdiciada. Un buen algoritmo de búsqueda reduce todas estas "ramas" ya que de todos modos son irrelevantes.

El algoritmo de búsqueda estándar es la poda alfa-beta , y se usó en las primeras computadoras de ajedrez. No sé si Deep Blue usó la poda alfa-beta, pero los motores modernos no. Como resultado, sus búsquedas son "inseguras": pueden perderse, por ejemplo, que algunos movimientos que no sean recuperar la reina habrían ganado el juego. Sin embargo, es raro que esto suceda, y a cambio empujan sus profundidades muy alto. ("Profundidad" es un término técnico para determinar qué tan profundo busca el motor, por ejemplo, un motor que busca hasta la profundidad 30 es probable que supere a uno que solo busca hasta la profundidad 20, todas las demás cosas son iguales).

Evaluación . Esta es la otra punta del código del motor. Dada una posición particular, ¿es mejor para blanco, negro o igual? Esto puede involucrar todo tipo de funciones, p. Ej.

  • Si un lado tiene material / espacio extra, dele un bono para evaluar.
  • Si las blancas tienen un caballero avanzado apoyado por un peón, dale a las blancas una bonificación para evaluar.
  • Si el rey negro está estancado, dale al blanco una bonificación para evaluar.
  • Si las blancas tienen una torre en el séptimo rango, dale a las blancas una bonificación para evaluar.
  • Si es un juego final (y hay algoritmos para decidir si la posición es un juego final) y ambos lados tienen obispos de colores opuestos, imponga una penalización para evaluar (es decir, empujarlo hacia 0.00).

Los motores de hoy evalúan las posiciones mucho mejor que Deep Blue.

En cuanto a si los algoritmos son públicos, Stockfish es actualmente el motor más fuerte del mundo y es de código abierto. Puede descargar el código usted mismo desde Github .

Seducir
fuente