¿Cuál es una forma precisa de evaluar las posiciones de ajedrez?

Durante un tiempo, me interesaron los algoritmos de IA de ajedrez de la computadora (y tuve la oportunidad de trabajar en uno en algún momento) como Minimax , y como el componente central de estos algoritmos es la llamada función de evaluación para determinar qué es un buena configuración de placa, y lo que es malo .

En otros términos, dada una configuración de su tablero de ajedrez, ¿cómo determina que es una ventaja para usted y con qué grado de confianza?

Por ejemplo:

• Si es dueño del centro, esto es bastante favorable.
• Si tienes más piezas que tu oponente, esto es bastante favorable.
• Si perdiste a tu Reina, esto no es favorable.
• Si tienes un peón que está cerca de ser promovido, esto es favorable.
• ...

Por lo tanto, me gustaría pedir algunos consejos sobre cómo crear una buena función de evaluación, basada en un conocimiento experto sobre el juego de ajedrez en general. Y si es posible, un grado de favorabilidad (digamos que entre 1 es muy poco favorable y 100 es extremadamente favorable).

La idea al final es poder crear un algoritmo que busque en el árbol de posibilidades hasta una cierta profundidad y evaluar cuál es la configuración más favorable para el próximo movimiento (teniendo en cuenta varios movimientos en el futuro) en función de qué es favorable al jugador y no favorable al oponente. Pero sin una buena función de evaluación, el algoritmo no es nada.

Aquí hay un buen punto de partida. La comparación de materiales es clave (y fácil), luego puede ajustar eso para considerar aspectos posicionales como rangos / archivos / diagonales abiertos, estructura de peones, etc.

https://www.chessprogramming.org/Evaluation

Sumando a la respuesta de @Eve Freeman, sugeriría buscar cómo el mejor motor de computadora del mundo, Stockfish, evalúa una posición determinada. Como el código fuente está abierto, puede hacerlo de forma gratuita. Creo que el archivo con la función de evaluación que está buscando es este .

Tengo la sensación de que estoy un poco tarde en esta respuesta, pero también estoy en el proceso de hacer un motor. El código fuente está en Python (que es bastante fácil de leer, incluso si no lo sabe) y está disponible aquí si desea leerlo. La lista de 'heurísticas' actualmente activas (en el momento de la publicación):

• Las piezas más desarrolladas (más cerca del lado opuesto) son mejores
• Los peones más cercanos a la promoción son buenos.
• Los reyes se puntúan por separado en función de la fase en la que se encuentra el juego (apertura, medio juego, final del juego)
• Si el jugador tiene ambos obispos, eso recibe una bonificación
• Si el jugador ha enrocado, recibe una bonificación
• Los peones aislados (peones sin nada a su alrededor) no son buenos
• Los peones doblados (dos peones en el mismo archivo sin espacio entre ellos) no son buenos
• Tener los 8 peones no es necesariamente algo bueno y es penalizado (desordenan el tablero y se interponen)
• Eche un vistazo a esta gran función de evaluación que también se utiliza
• Los obispos con más peones en el mismo cuadrado de color que el obispo son penalizados (no son tan buenos en situaciones de hacinamiento)
• Aún no implementado, pero planeado: los Caballeros obtienen una bonificación en situaciones más concurridas

En uno de esos puntos, mencioné la 'fase' del juego (por ejemplo, apertura, medio juego, final del juego), y si desea incluir eso en su motor, probablemente se encontrará con el mismo problema que yo: no hay línea clara que los separa. Mi función que decide en qué fase se encuentra el juego utiliza algunas cosas:

• Cantidad de material en el tablero (tan pronto como se mata cualquier pieza, marca el juego como no en la apertura)
• Número de movimientos (menos de 6 movimientos completos es la apertura, pase lo que pase)
• movimiento de las reinas (si ambas se han movido, marca el juego como medio juego)

Esta respuesta puede haber sido larga, tardía y fuera de tema, pero espero que haya sido útil de todos modos.

Sorprendentemente, resulta que un motor Minimax funcionará razonablemente bien cuando la función de evaluación es aleatoria ; Esto se conoce como el efecto Beale, y resulta del principio de que las posiciones que te dan más opciones y tu oponente menos opciones son generalmente favorables. Una forma razonable de generar evaluaciones aleatorias de manera consistente y eficiente es generar un hash de Zobrist para la posición (usando coeficientes elegidos aleatoriamente al comienzo del juego) y derivar la evaluación aleatoria directamente del hash.

En el extremo opuesto de la escala, AlphaZero y Leela realizan una evaluación extremadamente sofisticada de cada posición buscada, utilizando una gran red neuronal . No es práctico describir en términos humanos qué funciones implementa efectivamente esta red, pero es indudablemente más eficaz que la función de evaluación de Stockfish. El trabajo de investigación de AlphaZero indica que este enfoque funciona mejor con Monte-Carlo Tree Search en lugar de Minimax.

Si, por otro lado, desea desarrollar un motor de análisis para ayudar a los jugadores o comentaristas humanos a comprender los matices de una posición, puede valer la pena implementar una función de evaluación convencional utilizando valores materiales establecidos y teoría posicional . Inside Rebel , de Ed Schröder, da un buen ejemplo y documenta las principales características de diseño de un motor bien considerado utilizado en varias de las computadoras de ajedrez de Mephisto. Es posible que desee utilizar un cierto grado de aprendizaje automático para determinar la importancia relativa de cada elemento de su función de evaluación, y también desglosar estos elementos individualmente para su presentación en una GUI.

Creo que los programadores de ajedrez tienden a no confiar en el conocimiento de los jugadores de ajedrez fuertes cuando diseñan sus funciones de evaluación, sino que prueban diferentes elementos y luego los prueban en juegos contra otros motores, y deciden qué guardar. Larry Kaufman habla un poco sobre sus puntos de vista sobre la comprensión humana, pero parece que tanto Rajlich como Dailey estaban muy orientados a los resultados y no adoptaron las ideas de Kaufman al por mayor.

Un artículo que encontré interesante fue Zach Wegner comparando las funciones de evaluación de Rybka y Fruit. Una de las áreas donde Rybka pudo haber representado un paso adelante fue la incorporación de tablas de desequilibrio de materiales basadas en combinaciones específicas de piezas. Kaufman escribió un artículo sobre esto también.

http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm

Este enlace es el mejor punto de partida en mi humilde opinión. Estoy usando esto como mi punto de partida para mi propio programa de ajedrez y también encuentro que es fácil de entender y útil.

https://chessprogramming.wikispaces.com/Simplified+evaluation+function

En pocas palabras, el enfoque estándar para ajustar los parámetros de un motor de ajedrez es:

1. Definir los parámetros.
2. Dar a los parámetros valores nominales (iniciales)
3. Ejecute el motor para ver cómo funciona
4. Ajuste los valores de los parámetros para intentar mejorar su rendimiento.

Luego repita los pasos 3 y 4 hasta que haya alcanzado su objetivo de rendimiento.

El enfoque habitual para hacer esto es establecer un laboratorio donde los motores se enfrenten en torneos de motores. Se utilizan múltiples juegos en los que el motor juega ambos colores. Los principales torneos de interés implican ejecutar un motor con el valor de parámetro establecido A contra el mismo motor con el valor de parámetro establecido B.

Como probablemente pueda adivinar, los resultados de este enfoque dependen en gran medida de:

• Los parámetros elegidos
• Cómo se especifican los parámetros
• Cómo se varían los valores de los parámetros durante las pruebas
• Cómo funcionan los motores (profundidad de capa limitada, tiempo limitado, sensibilidad, etc.)

Este enfoque también consume mucho tiempo.

En 2010, los investigadores desarrollaron un enfoque más reciente (e innovador) utilizando técnicas de algoritmo genético para a) especificar los parámetros yb) ajustar los valores de los parámetros. Los investigadores primero pusieron en marcha un motor con un conjunto inicial de valores de parámetros nominales contra un conjunto de juegos de grandes maestros para ver si podía elegir efectivamente el "mejor movimiento". El "mejor movimiento" se definió como el movimiento que hizo el gran maestro *. Dondequiera que no lo hizo, se registró. Luego, se probó otro conjunto de valores de parámetros y se determinó el rendimiento relativo frente a la ejecución anterior.

Luego, se probó un enfoque programático para combinar los valores de los parámetros , utilizando el principio del algoritmo genético de supervivencia del "más apto". Aquí, "más apto" significa el que genera la salida que más se acerca al ideal. (También resulta ser un juego de palabras con la técnica estadística de regresión de "ajuste de mínimos cuadrados", una técnica utilizada para juzgar la calidad de la aproximación).

Solo después de que se hayan encontrado los parámetros del motor que pueden imitar a un GM razonablemente bien, comienza la fase del torneo del motor. En esta fase, diferentes conjuntos de valores de parámetros se enfrentan una vez más, esta vez directamente . Las técnicas de mejora del algoritmo genético se aplican para generar sucesivamente mejores generaciones del motor.

En este proyecto de investigación, se utilizaron 36 parámetros, incluidos todos los valores materiales de las piezas y muchos de los criterios de evaluación estratégica más comunes, como los peones hacia atrás, los cuadrados débiles, el par de alfil, etc. Sin embargo, los investigadores agregaron algunos parámetros nuevos, tales como "presión del rey", valores de "movilidad" para cada tipo de pieza, torre en un archivo adyacente al rey, torre en un archivo semiabierto, torre atacando al rey en el - / b- / g- / h-file, separación entre un peón pasado y el rey defensor, y más.

Desafortunadamente, los investigadores no explican cómo se les ocurrió este conjunto de parámetros y qué parámetros alternativos pueden haber probado y rechazado. Sería razonable suponer que comenzaron con un conjunto mucho más grande y determinaron (mediante prueba y error) cuáles tuvieron el mayor efecto en el rendimiento y cuáles fueron insignificantes o derivados, por lo que podrían descartarse.

Si esto le parece útil, puede encontrar la investigación aquí .

* Una advertencia sobre una fase del enfoque que utilizaron los investigadores está en orden. En su Introducción a la comprensión del movimiento de ajedrez por movimiento , John Nunn eligió "... juegos muy reñidos entre grandes maestros fuertes ..." para ilustrar sus temas. Luego agrega:

Los lectores pueden sorprenderse al ver la cantidad de signos de interrogación que adornan los juegos en este libro. Seguramente, podría pensar, con solo treinta juegos para seleccionar, debería haber sido fácil encontrar algunos juegos de sonido. Sin embargo, puedo asegurarle que no fue así. ... es posible encontrar fallas en prácticamente cualquier juego complejo y reñido ... Nunca sentí que mi juego fuera tan preciso, por lo que personalmente no encuentro estas revelaciones angustiantes. Sin embargo, a algunos les puede resultar difícil admitir que el ajedrez tal como lo juegan los seres humanos es menos preciso de lo que se pensaba anteriormente.

El punto que plantea el Dr. Nunn sugiere que el enfoque inicial de los investigadores para establecer los parámetros del motor al exigirles que imiten los movimientos del gran maestro puede ser defectuoso porque el juego humano es defectuoso . De hecho, está bien establecido que los motores ya juegan mejor que los humanos .

Por lo tanto, quizás un mejor enfoque para establecer los parámetros iniciales sería hacer coincidir un motor nuevo con un motor existente superior .

Hay un buen sitio web en:

https://hxim.github.io/Stockfish-Evaluation-Guide/

Le ofrece una introducción sobre cómo funcionan las funciones de Stockfish.