¿Qué algoritmos y heurísticas son populares en el ajedrez informático?

18

El ajedrez informático ha explotado en los últimos veinte años, con el establecimiento de un campeonato mundial de informática y muchos diseñadores de computadoras de ajedrez se han vuelto bastante rentables a partir de sus esfuerzos. Algunos de los programas ocultan su código fuente, pero muchos son de código abierto, especialmente Fruit, que sirvió de base para una familia de motores de ajedrez.

¿Cuáles son algunos ejemplos de heurística o algoritmos utilizados por las computadoras de ajedrez, y cuáles han tenido más éxito o son más populares?

Andrew Latham
fuente
2
Este no es el lugar adecuado para esta pregunta y ya se le preguntó en la definición del proyecto: debate.area51.stackexchange.com/questions/5056/…
Charles Menguy

Respuestas:

7

Los algoritmos utilizados principalmente se basan en la búsqueda del espacio de estados. El problema es que las posibles posiciones que puede hacer una pieza en el próximo movimiento son muy grandes. Pero es finito. Básicamente es un problema de búsqueda. Hay una posición válida que una pieza puede tomar. Es decir, hay un estado inicial conocido y un estado final conocido. No hay probabilidad involucrada como el problema de lanzar una moneda.
Un algoritmo típico es usar la fuerza bruta y calcular movimientos para un número fijo de movimientos. MiniMax se puede utilizar en tales casos. La poda alfa-beta también es un algoritmo bien conocido utilizado. La mayoría de los espacios de búsqueda se representan mediante una estructura de datos basada en árbol.
El programa de computadora también utiliza en gran medida bases de datos que contienen movimientos, aperturas, posiciones finales del juego, etc.


fuente
1
La pregunta se refiere a la heurística . El objetivo de la heurística es evitar el gasto del cálculo de la fuerza bruta de todos los movimientos legales. Entonces, desafortunadamente, una respuesta que involucra un enfoque de fuerza bruta no está en el tema.
jaxter