Función de evaluación

Este artículo es parte de la serie sobre
Programación de ajedrez
Representaciones de la junta 0x88 Tableros de bits
Funciones de evaluación Redes neuronales profundas ( Transformers ) Atención Redes neuronales actualizables de manera eficiente Funciones de evaluación hechas a mano Mesas de piezas cuadradas Aprendizaje por refuerzo Descenso de gradiente estocástico Aprendizaje supervisado Ajuste de Texel Aprendizaje no supervisado
Algoritmos de búsqueda de gráficos y árboles Minimáximo Poda alfa-beta Búsqueda de variación principal Búsqueda de quietud Búsqueda de árboles en Montecarlo
Computadoras de ajedrez Beldad Maquina de ajedrez Prueba de chip Blitz de lombrices Azul profundo Pensamiento profundo De alta tecnología Hidra Mefisto Saitek
Motores de ajedrez Alfa Cero Tigre de ajedrez Astuto Ajedrez cuco Fritz profundo Dragón de Komodo Chess Hada-Max Fritz Fruta Ajedrez GNU HIARCS Houdini Ícaro Júnior Gorra de caballero Komodo Leela Ajedrez Cero MChess Pro Guantes de boxeo MuZero Naum REBELDE Río Desfibradora Sjeng Pensamiento inteligente Pescado de seco Antorcha Turochamp Zappa
en a mi

Una función de evaluación , también conocida como función de evaluación heurística o función de evaluación estática , es una función utilizada por los programas informáticos de juegos para estimar el valor o la bondad de una posición (normalmente en una hoja o nodo terminal) en un árbol de juego. ^[1] La mayoría de las veces, el valor es un número real o un entero cuantificado , a menudo en n del valor de una pieza de juego, como una piedra en go o un peón en ajedrez, donde n puede ser décimas, centésimas u otra fracción conveniente, pero a veces, el valor es una matriz de tres valores en el intervalo unitario , que representa los porcentajes de victoria, empate y derrota de la posición.

No existen modelos analíticos o teóricos para las funciones de evaluación de juegos no resueltos, ni tampoco son funciones totalmente ad hoc. La composición de las funciones de evaluación se determina empíricamente insertando una función candidata en un autómata y evaluando su desempeño posterior. Actualmente existe un conjunto significativo de evidencias para varios juegos como ajedrez, shogi y go en cuanto a la composición general de las funciones de evaluación para ellos.

Los juegos en los que los programas de computadora para jugar emplean funciones de evaluación incluyen ajedrez , ^[2] go , ^[2] shogi (ajedrez japonés), ^[2] otelo , hex , backgammon , ^[3] y damas . ^{[4] [5]} Además, con la llegada de programas como MuZero , los programas de computadora también usan funciones de evaluación para jugar videojuegos , como los del Atari 2600. [ ^6] Algunos juegos como el tres en raya se resuelven fuertemente y no requieren búsqueda o evaluación porque hay disponible un árbol de soluciones discreto.

Un árbol de tales evaluaciones suele ser parte de un algoritmo de búsqueda, como la búsqueda de árbol de Monte Carlo o un algoritmo minimax como la búsqueda alfa-beta . Se supone que el valor representa la probabilidad relativa de ganar si el árbol de juego se expandiera desde ese nodo hasta el final del juego. La función solo mira la posición actual (es decir, en qué espacios están las piezas y su relación entre sí) y no tiene en cuenta el historial de la posición ni explora posibles movimientos hacia adelante del nodo (por lo tanto, estático). Esto implica que para las posiciones dinámicas donde existen amenazas tácticas, la función de evaluación no será una evaluación precisa de la posición. Estas posiciones se denominan no quietas ; requieren al menos un tipo limitado de extensión de búsqueda llamada búsqueda de quiescencia para resolver las amenazas antes de la evaluación. Algunos valores devueltos por las funciones de evaluación son absolutos en lugar de heurísticos, si ocurre una victoria, una derrota o un empate en el nodo.

Existe una relación intrincada entre la búsqueda y el conocimiento en la función de evaluación. Una búsqueda más profunda favorece menos factores tácticos de corto plazo y motivos posicionales de largo plazo más sutiles en la evaluación. También existe una disyuntiva entre la eficacia del conocimiento codificado y la complejidad computacional: calcular el conocimiento detallado puede llevar tanto tiempo que el rendimiento disminuye, por lo que las aproximaciones al conocimiento exacto suelen ser mejores. Debido a que la función de evaluación depende de la profundidad nominal de la búsqueda, así como de las extensiones y reducciones empleadas en la búsqueda, no existe una formulación genérica o independiente para una función de evaluación. Una función de evaluación que funciona bien en una aplicación normalmente necesitará ser reajustada o reentrenada sustancialmente para funcionar de manera efectiva en otra aplicación.

En ajedrez por computadora , la salida de una función de evaluación es típicamente un entero , y las unidades de la función de evaluación son típicamente llamadas peones . El término 'peón' se refiere al valor cuando el jugador tiene un peón más que el oponente en una posición, como se explica en Valor relativo de la pieza de ajedrez . El entero 1 usualmente representa una fracción de un peón, y comúnmente usado en ajedrez por computadora son centipeones , que son una centésima parte de un peón. Las evaluaciones más grandes indican un desequilibrio material o ventaja posicional o que una ganancia de material es usualmente inminente. Evaluaciones muy grandes pueden indicar que un jaque mate es inminente. Una función de evaluación también codifica implícitamente el valor del derecho a mover, el cual puede variar desde una pequeña fracción de un peón hasta victoria o pérdida.

Históricamente, en el ajedrez por computadora, los términos de una función de evaluación son construidos (es decir, hechos a mano) por el desarrollador del motor, en lugar de descubrirse mediante el entrenamiento de redes neuronales . El enfoque general para construir funciones de evaluación hechas a mano es como una combinación lineal de varios términos ponderados determinados para influir en el valor de una posición. Sin embargo, no todos los términos en una función de evaluación hecha a mano son lineales, algunos, como la seguridad del rey y la estructura del peón, son no lineales. Cada término puede considerarse compuesto de factores de primer orden (aquellos que dependen solo del espacio y cualquier pieza en él), factores de segundo orden (el espacio en relación con otros espacios) y factores de orden n (dependencias en el historial de la posición).

Una función de evaluación hecha a mano normalmente tiene un término de balance de material que suele dominar la evaluación. Los valores convencionales utilizados para el material son Reina = 9, Torre = 5; Caballo o Alfil = 3; Peón = 1; al rey se le asigna un valor arbitrario grande, normalmente mayor que el valor total de todas las demás piezas. ^[1] Además, normalmente tiene un conjunto de términos posicionales que normalmente no suman más que el valor de un peón, aunque en algunas posiciones los términos posicionales pueden ser mucho más grandes, como cuando el jaque mate es inminente. Las funciones de evaluación hechas a mano normalmente contienen de docenas a cientos de términos individuales.

En la práctica, las funciones de evaluación artesanales eficaces no se crean ampliando la lista de parámetros evaluados, sino ajustando o entrenando cuidadosamente los pesos relativos entre sí de un conjunto modesto de parámetros como los descritos anteriormente. Con este fin, se emplean posiciones de varias bases de datos, como partidas maestras, partidas de motor, partidas de Lichess o incluso de partidas propias, como en el aprendizaje por refuerzo .

Un ejemplo de función de evaluación hecha a mano para ajedrez podría verse como el siguiente:

• c ₁ * material + c ₂ * movilidad + c ₃ * seguridad del rey + c ₄ * control central + c ₅ * estructura de peones + c ₆ * tropismo del rey + ...

Cada uno de los términos es un peso multiplicado por un factor de diferencia: el valor de los términos materiales o posicionales de las blancas menos los de las negras.

• El término material se obtiene asignando un valor en unidades peón a cada una de las piezas.
• La movilidad es el número de movimientos legales disponibles para un jugador o, alternativamente, la suma del número de espacios atacados o defendidos por cada pieza, incluidos los espacios ocupados por piezas amigas u opuestas. También se puede tener en cuenta la movilidad efectiva o el número de espacios "seguros" a los que puede moverse una pieza.
• La seguridad del rey es un conjunto de bonificaciones y penalizaciones evaluadas según la ubicación del rey y la configuración de los peones y piezas adyacentes o frente al rey, y las piezas opuestas que se encuentran en espacios alrededor del rey.
• El control central se deriva de cuántos peones y piezas ocupan o se ubican en los cuatro espacios centrales y, a veces, en los 12 espacios del centro extendido.
• La estructura de peones es un conjunto de penalizaciones y bonificaciones para diversas fortalezas y debilidades en la estructura de peones, como por ejemplo penalizaciones por peones duplicados y aislados.
• El tropismo del rey es una bonificación por la cercanía (o penalización por la distancia) de ciertas piezas, especialmente reinas y caballos, al rey oponente.

Si bien las redes neuronales se han utilizado en las funciones de evaluación de los motores de ajedrez desde fines de la década de 1980, ^{[7] [8]} no se volvieron populares en el ajedrez por computadora hasta fines de la década de 2010, ya que el hardware necesario para entrenar redes neuronales no era lo suficientemente fuerte en ese momento, y aún no se habían desarrollado algoritmos de entrenamiento rápido ni topologías y arquitecturas de red. Inicialmente, las funciones de evaluación basadas en redes neuronales generalmente consistían en una red neuronal para toda la función de evaluación, con características de entrada seleccionadas del tablero y cuya salida es un entero , normalizado a la escala de centipeones de modo que un valor de 100 es aproximadamente equivalente a una ventaja material de un peón. Los parámetros en las redes neuronales generalmente se entrenan utilizando aprendizaje de refuerzo o aprendizaje supervisado . Más recientemente, las funciones de evaluación en ajedrez por computadora han comenzado a utilizar múltiples redes neuronales, con cada red neuronal entrenada para una parte específica de la evaluación, como la estructura de peones o los finales. Esto permite enfoques híbridos donde una función de evaluación consta tanto de redes neuronales como de términos hechos a mano.

Las redes neuronales profundas se han utilizado, aunque con poca frecuencia, en ajedrez por computadora después de que Giraffe ^[9] de Matthew Lai en 2015 y AlphaZero de Deepmind en 2017 demostraran la viabilidad de las redes neuronales profundas en funciones de evaluación. El proyecto de computación distribuida Leela Chess Zero se inició poco después para intentar replicar los resultados del artículo AlphaZero de Deepmind. Aparte del tamaño de las redes, las redes neuronales utilizadas en AlphaZero y Leela Chess Zero también difieren de las utilizadas en los motores de ajedrez tradicionales, ya que tienen dos salidas, una para la evaluación (el valor cabeza ) y otra para el orden de movimientos (la política cabeza ), en lugar de solo una salida para la evaluación. ^[10] Además, si bien es posible establecer la salida del valor cabeza de la red neuronal de Leela en un número real para aproximarse a la escala de centipeones utilizada en los motores de ajedrez tradicionales, por defecto la salida son los porcentajes de victoria-empate-derrota, un vector de tres valores cada uno del intervalo unitario . ^[10] Dado que las redes neuronales profundas son muy grandes, los motores que utilizan redes neuronales profundas en su función de evaluación generalmente requieren una unidad de procesamiento de gráficos para calcular de manera eficiente la función de evaluación.

Una técnica importante en la evaluación desde al menos principios de la década de 1990 es el uso de tablas de piezas-casillas (también llamadas tablas de valores de piezas) para la evaluación. ^{[11] [12]} Cada tabla es un conjunto de 64 valores correspondientes a las casillas del tablero de ajedrez. La implementación más básica de la tabla de piezas-casillas consiste en tablas separadas para cada tipo de pieza por jugador, lo que en ajedrez da como resultado 12 tablas de piezas-casillas en total. En el ajedrez por computadora se utilizan variantes más complejas de tablas de piezas-casillas, una de las más destacadas es la tabla de rey-pieza-casilla, utilizada en Stockfish , Komodo Dragon , Ethereal y muchos otros motores, donde cada tabla considera la posición de cada tipo de pieza en relación con el rey del jugador, en lugar de la posición de cada tipo de pieza solo. Los valores en las tablas son bonificaciones/penalizaciones por la ubicación de cada pieza en cada espacio y codifican un compuesto de muchos factores sutiles difíciles de cuantificar analíticamente. En las funciones de evaluación hechas a mano, a veces hay dos conjuntos de tablas: uno para la apertura/medio juego y otro para el final; las posiciones del medio juego se interpolan entre los dos. ^[13]

Originalmente desarrollada en shogi por computadora en 2018 por Yu Nasu, ^{[14] [15]} la función de evaluación más común utilizada en ajedrez por computadora hoy ^{[ cita requerida ]} es la red neuronal actualizable de manera eficiente , o NNUE para abreviar, una red neuronal dispersa y superficial que solo tiene tablas de cuadrados de piezas como entradas en la red neuronal. ^[16] De hecho, la arquitectura NNUE más básica es simplemente las tablas de 12 cuadrados de piezas descritas anteriormente, una red neuronal con solo una capa y sin funciones de activación . Una arquitectura de red neuronal actualizable de manera eficiente, que utiliza tablas de cuadrados de piezas de rey como entradas, se trasladó por primera vez al ajedrez en un derivado de Stockfish llamado Stockfish NNUE, lanzado públicamente el 30 de mayo de 2020, ^[17] y fue adoptado por muchos otros motores antes de ser finalmente incorporado al motor oficial de Stockfish el 6 de agosto de 2020. ^{[18] [19]}

Los motores de ajedrez utilizan frecuentemente tablas de finales en su función de evaluación, ya que les permite jugar perfectamente en el final.

Históricamente, las funciones de evaluación en Computer Go tenían en cuenta tanto el territorio controlado, la influencia de las piedras, la cantidad de prisioneros y la vida o muerte de los grupos en el tablero. Sin embargo, los programas informáticos modernos para jugar al Go utilizan en gran medida redes neuronales profundas en sus funciones de evaluación, como AlphaGo , Leela Zero , Fine Art y KataGo , y generan un porcentaje de victorias/empates/derrotas en lugar de un valor en cantidad de piedras.

• Slate, D y Atkin, L., 1983, "Chess 4.5, the Northwestern University Chess Program" en Habilidad en ajedrez en el hombre y la máquina, 2.ª edición, págs. 93-100. Springer-Verlag, Nueva York, NY.
• Ebeling, Carl, 1987, All the Right Moves: A VLSI Architecture for Chess (Tesis doctoral de la ACM), págs. 56-86. MIT Press, Cambridge, MA

• Claves para evaluar posiciones
• GameDev.net - Programación de ajedrez Parte VI: Funciones de evaluación