¿Cómo mejoraron los motores desde Deep Blue?

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?

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

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.

¿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.

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.

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 .