¿Los motores de ajedrez almacenan todas las posiciones analizadas previamente entre movimientos

Estoy empezando a jugar con motores de ajedrez. Noté que los mejores motores de ajedrez pueden demorar varios minutos en moverse. Me pregunto por qué. Antes de cada movimiento, el motor examina todos los movimientos legales futuros a cierta profundidad. Sin embargo, parece repetir este ejercicio para el próximo movimiento. Dado que el movimiento anterior ya estaba incluido en el árbol de movimientos examinado, ¿no es esto ineficiente? ¿O he entendido mal?

[Editar: Supongo que la razón por la cual los análisis de movimiento no se almacenan en caché se debe a algunas limitaciones de memoria de la computadora que solo hacen que sea más rápido reiniciar el análisis]

La programación de motores de ajedrez es un territorio muy complicado, así que desde el principio te dirijo a la Wiki de programación de ajedrez , que tiene mucha información excelente sobre este tema.

Antecedentes

Los cálculos de ajedrez (y muchas cosas similares) generalmente se modelan y se consideran "árboles de juego" o " árboles de decisión ". En términos generales, este árbol es un gráfico dirigido, con un nodo en la parte superior (la posición actual), que conduce a un nodo para cada posible movimiento, cada uno de los cuales conduce a más nodos para cada posible próximo movimiento, y así sucesivamente.

En su forma más simple y de fuerza bruta, los motores de ajedrez generan todas las posiciones en este árbol hasta cierto límite de profundidad ("capa"), evaluando cada posición resultante en función de algunos criterios complejos ¹ . Luego juega el movimiento que parece conducir al mejor resultado. Hoy en día, se han desarrollado muchas técnicas realmente complicadas para limitar el número de posiciones que el motor tiene que mirar, pero voy a ignorarlas a los efectos de esta respuesta, porque no cambian el problema real en mano.

Tangente Matemática

La razón básica por la que los motores generalmente tardan aproximadamente la misma cantidad de tiempo en considerar cada movimiento es que el tamaño del árbol de decisión aumenta exponencialmente con la profundidad ( k).

Considere la posición inicial. La parte superior del árbol ( k=0) es un nodo. Hay veinte primeros movimientos posibles para las blancas, por lo que hay veinte nodos en profundidad k=1. Luego, las negras también tienen veinte movimientos disponibles para cada una de las opciones de las blancas: así que k=2, ¡hay 20 * 20 = 400posibles posiciones! ¡Y solo empeora a medida que los jugadores desarrollan sus piezas!

Por ejemplo, supongamos que siempre hay veinte movimientos posibles para cada jugador en un momento dado ² . Le indica a la computadora que mire hacia adelante cinco movimientos para cada jugador (diez capas). Veamos el tamaño del árbol de fuerza bruta en cada nivel. Por diversión, también veremos el número total de posiciones en el árbol (desde la parte superior hasta el nivel dado).

Ply |    Positions   |  Total Tree Size
----------------------------------------
 0  | 1              | 1
 1  | 20             | 21
 2  | 400            | 421
 3  | 8000           | 8421
 4  | 160000         | 168421
 5  | 3200000        | 3368421
 6  | 64000000       | 67368421
 7  | 1280000000     | 1347368421
 8  | 25600000000    | 26947368421
 9  | 512000000000   | 538947368421
10  | 10240000000000 | 10778947368421

El resultado de que cada nivel sea exponencialmente mayor que el nivel anterior es que el tamaño de todo el árbol está dominado por el nivel inferior . Considere el ejemplo anterior: el último nivel solo contiene diez billones de nodos. Todo el resto del árbol solo contiene quinientos mil millones. La décima capa contiene aproximadamente el 95% de los nodos en todo el árbol (esto es realmente cierto en cada nivel). En la práctica, lo que esto significa es que se pasa todo el tiempo de búsqueda evaluando el "último" movimiento.

Responder

Entonces, ¿cómo se relaciona esto con su pregunta? Bueno, digamos que la computadora está configurada en diez capas, como se indicó anteriormente, y además "recuerda" los resultados de sus evaluaciones. Calcula un movimiento, lo juega y luego haces un movimiento. Ahora se han realizado dos movimientos, por lo que elimina todas las posiciones de la memoria relacionadas con los movimientos que no ocurrieron, y queda con un árbol que baja los ocho movimientos restantes que ya calculó: ¡26,947,368,421 posiciones!

¡Todo bien! ¡Entonces solo tenemos que calcular las dos últimas capas! Usando nuestra estimación de 20 movimientos en cada profundidad, el número total de movimientos que necesitamos calcular aquí todavía supera los diez billones. ¡Las posiciones que ya calculamos solo representan el 2.5% de las posibilidades! Entonces, incluso al almacenar en caché los resultados del último movimiento, ¡lo mejor que podemos esperar es un aumento del 2.5% en la velocidad! En el fondo, esta es la razón por la cual, incluso si su programa almacena en caché resultados anteriores, generalmente no ve una aceleración significativa entre movimientos (¡excepto en los casos en que la computadora encuentra un compañero forzado o algo así, por supuesto!).

Descargo de responsabilidad de simplificación

Hay mucha complejidad involucrada en esta pregunta, por eso me vinculé a la wiki de programación en la parte superior y solo intenté explicar la respuesta en términos matemáticos generales. En realidad, los programas hacen generalmente partes de caché del árbol de movimiento para mover y hay otras razones por las que es insuficiente por sí solo - algunas razones simples (por ejemplo, una determinada línea puede ser bueno a ocho movimientos, pero termina con una parte posterior - ¡Mate compañero en el movimiento nueve!) y muchos muy complicados (generalmente relacionados con varios métodos de poda inteligentes). Por lo tanto, la computadora debe seguir mirando más adelante en un intento de evitar hacer suposiciones erróneas basadas en la profundidad de corte del movimiento anterior.

¹ No voy a entrar en funciones heurísticas aquí, porque esa es su área increíblemente compleja, pero a menudo también se pueden lograr algunas ganancias a través de esquemas de almacenamiento en caché de posición.

² Un factor de ramificación promedio de 20 es probablemente demasiado bajo .

Un motor de ajedrez típico almacenará algunas de las posiciones y sus puntuaciones alfa-beta entre corchetes en una tabla de transposición que se puede consultar durante las búsquedas posteriores. Esta tabla no se consulta directamente para elegir el siguiente movimiento, pero hace que la búsqueda de ese movimiento sea más eficiente de dos maneras.

1. Es probable que se encuentre una posición varias veces en un árbol de búsqueda, alcanzándose mediante una transposición o permutación de una secuencia de movimientos. Debido a que se puede consultar la tabla, tal posición solo necesita ser evaluada pocas veces (para diferentes profundidades de búsqueda fijas) en lugar de docenas de veces a medida que la posición se visita y se vuelve a visitar.

2. Una técnica estándar para las búsquedas alfa-beta es utilizar la profundización iterativa , sondeando repetidamente el árbol a una mayor profundidad de búsqueda hasta alcanzar la profundidad terminal. Las puntuaciones de valoración calculadas en las iteraciones anteriores se utilizan para ordenar los movimientos buscados en las iteraciones posteriores. Se sabe que Alpha-beta funciona mejor (es decir, poda más del árbol de búsqueda) si se buscan buenos movimientos antes de malos movimientos.

Ejemplo que evidencia la memoria del motor:

Considere las posiciones donde se descubren profundas novedades teóricas, en particular el juego que Caruana vs Topalov jugó este año. Cuando deja que el motor analice la posición después del movimiento 12 durante un período de tiempo más o menos corto (digamos 10-15 minutos), puede verificar los movimientos sugeridos y ver que el TN ( 13.Re2!) no aparece entre ellos. Introduzca el movimiento usted mismo, retroceda un movimiento y deje que el motor analice nuevamente la misma posición durante más o menos el mismo tiempo. Sorprendentemente, después de pensarlo un poco, ahora el motor considera al TN entre los mejores movimientos y lo aprueba.

EDITAR: La respuesta original (que se muestra a continuación) es incorrecta, sin embargo, proporciona un ejemplo útil de la memoria del motor, que se ha citado en la parte superior.

Hasta donde yo sé, no lo hacen, es decir, comienzan la búsqueda de árboles casi desde cero en cada movimiento.

Sin embargo, deben tener algún tipo de función que actualice los valores para cada movimiento, y esta función seguramente tiene algo de memoria a corto plazo. Algunos ejemplos son posiciones donde se descubren profundas novedades teóricas, en particular el juego que Caruana vs Topalov jugó este año. Cuando deja que el motor analice la posición después del movimiento 12 durante un período de tiempo más o menos corto (digamos 10-15 minutos), puede verificar los movimientos sugeridos y ver que el TN ( 13.Re2!) no aparece entre ellos. Introduzca el movimiento usted mismo, retroceda un movimiento y deje que el motor analice nuevamente la misma posición durante más o menos el mismo tiempo. Sorprendentemente, después de pensarlo un poco, ahora el motor considera al TN entre los mejores movimientos y lo aprueba.

No soy un experto en software de ajedrez, pero esto sucede. Esto puede explicarse al menos parcialmente si (como se dijo) la función que evalúa los movimientos para la posición tiene algo de memoria.

Henry Keiter ya te dio una respuesta general, yo te daré una respuesta más técnica. Se trata de la tabla de transposición, profundidad de búsqueda y corte. La discusión aquí es MUCHO más técnica que otras respuestas, pero será beneficiosa para quien quiera aprender programación de ajedrez.

Es un malentendido común que si una posición se evaluó antes, el puntaje de evaluación podría reutilizarse siempre que haya suficiente memoria para almacenar los movimientos. La programación de ajedrez es más complicada que eso. Incluso teniendo en cuenta la memoria infinita, todavía tendría que buscar las posiciones nuevamente. Para cada movimiento, se adjunta un puntaje de evaluación con su profundidad y su límite. Por ejemplo, si el motor almacena un movimiento por falla alta, la entrada de la tabla tendría un límite inferior. Esto significa que, si está buscando un puesto, aún tendrá que verificar los límites si puede usar el puntaje de evaluación anterior.

Aparte de eso, cada evaluación tiene una profundidad asociada. En un marco de profundización iterativa, a medida que aumenta la profundidad de cada iteración, aún tendrá que buscar las posiciones que ya ha buscado en la iteración anterior.

La respuesta breve a su pregunta es que un motor almacena todas las posiciones analizadas anteriores (siempre que haya suficiente memoria), pero esos resultados almacenados no pueden reutilizarse tan fácilmente como podría haber pensado . En una fase de apertura donde hay menos repeticiones, los resultados almacenados son más útiles para la ordenación de movimientos y una docena de heurísticas de reducción de movimientos. Por ejemplo, uno supondría que el mejor movimiento desde la última profundidad sería el mejor movimiento en la profundidad actual, por lo que clasificaríamos las listas de movimientos y buscaríamos el mejor movimiento antes que cualquier otro movimiento. Con suerte, obtendríamos un corte temprano de falla alta.

No tenemos memoria infinita para almacenar las posiciones. Necesitaríamos definir un algoritmo de hash. El algoritmo de hash de Zobrist nos proporciona una distribución pseudoaleatoria, pero tarde o temprano aún tendremos que reemplazar algunas entradas existentes.

Cada motor tiene su propio esquema de gestión del tiempo. Algunos motores y GUI le permiten establecer el ritmo al que jugará el motor. Los motores siempre calculan / evalúan / minimax tanto como pueden dadas las restricciones impuestas por las subrutinas de gestión del tiempo o la configuración del usuario. Si un motor piensa durante mucho tiempo, es probable porque el control de tiempo para el juego es lento o porque el usuario lo ha configurado para jugar lentamente.

Las posiciones y evaluaciones que el motor ha calculado se almacenan en una tabla hash. El usuario puede establecer el tamaño del hash disponible en la configuración de la mayoría de los motores UCI. El motor en sí usa una cierta cantidad de RAM, y si configura el tamaño de la tabla hash demasiado alto, la computadora comenzará a almacenar hash en su disco duro en forma de RAM virtual. Se accede a la memoria del disco duro más lentamente que la RAM, y generalmente podrá escuchar el disco duro agitándose. Muchos usuarios establecen el tamaño de la tabla hash para que se ajuste a la RAM disponible.

Una gran proporción de cualquier tabla de hash se vuelve inútil después de que el motor y su oponente hayan hecho sus movimientos ya que las otras posiciones consideradas ya no son relevantes. El motor reutilizará las evaluaciones almacenadas en hash, pero algunas de las evaluaciones resultan incorrectas debido a los efectos del horizonte una vez que el motor se adentra en la misma línea, por lo que a menudo tiene que reordenar sus movimientos candidatos.

Dado que la cantidad de hash es finita, un motor también tiene que tomar decisiones sobre qué información eliminar de su hash a medida que agrega nueva información. El motor no sabe de antemano qué movimientos se jugarán, por lo que puede eliminar inadvertidamente información que podría haber sido útil al agregar nuevos datos.

Los motores en general no examinan todos los movimientos legales hasta una cierta profundidad. Eliminan ciertas ramas del árbol de la consideración basada en la poda hacia adelante y hacia atrás. Además, si una posición de nodo de hoja tiene capturas o comprobaciones aún por realizar, el motor continuará por esa línea hasta que llegue a una posición tranquila (inactiva). El árbol real es probablemente bastante profundo en algunos lugares, mientras que otras líneas pueden haberse truncado después de un pequeño número de movimientos.