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 programas informáticos de juegos para estimar el valor o la bondad de una posición (generalmente 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 enésimas partes del valor de una pieza de juego, como una piedra en el go o un peón en el 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 victorias, empates y pérdidas de la posición.
No existen modelos analíticos o teóricos para funciones de evaluación de juegos sin resolver, ni dichas funciones son enteramente 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 importante conjunto de pruebas para varios juegos como el ajedrez, el shogi y el go en cuanto a la composición general de las funciones de evaluación para ellos.
Los juegos en los que los programas informáticos emplean funciones de evaluación incluyen ajedrez , [2] go , [2] shogi (ajedrez japonés), [2] othello , hex , backgammon , [3] y damas . [4] [5] Además, con la llegada de programas como MuZero , los programas informáticos también utilizan funciones de evaluación para jugar a videojuegos , como los del Atari 2600 . [6] Algunos juegos como el tres en raya se resuelven fuertemente y no requieren búsqueda ni evaluación porque hay disponible un árbol de soluciones discretas.
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 del juego se expandiera desde ese nodo hasta el final del juego. La función mira sólo la posición actual (es decir, en qué espacios se encuentran 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 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 quiescentes ; requieren al menos un tipo limitado de extensión de búsqueda llamada búsqueda de inactividad 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 se produce una victoria, una pérdida o un empate en el nodo.
Existe una relación intrincada entre búsqueda y conocimiento en la función de evaluación. Una búsqueda más profunda favorece factores tácticos menos a corto plazo y motivos posicionales de largo plazo más sutiles en la evaluación. También existe un equilibrio 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 entrenada sustancialmente para que funcione eficazmente en otra aplicación.
En el ajedrez informático , la salida de una función de evaluación suele ser un número entero y las unidades de la función de evaluación suelen denominarse 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 las piezas de ajedrez . El número entero 1 generalmente representa alguna fracción de un peón, y en el ajedrez por computadora se usan comúnmente los centipeones , que son una centésima parte de un peón. Las evaluaciones más amplias indican un desequilibrio material o una ventaja posicional o que una ganancia de material suele ser inminente. Evaluaciones muy grandes pueden indicar que el jaque mate es inminente. Una función de evaluación también codifica implícitamente el valor del derecho a mover, que puede variar desde una pequeña fracción de un peón hasta ganar o perder.
Históricamente, en el ajedrez por computadora, los términos de una función de evaluación los construye (es decir, los elabora a mano) el desarrollador del motor, en lugar de descubrirlos mediante el entrenamiento de redes neuronales . El enfoque general para construir funciones de evaluación artesanales 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 artesanal son lineales; algunos, como la seguridad del rey y la estructura de peones, no son lineales. Se puede considerar que cada término está compuesto por factores de primer orden (aquellos que dependen sólo del espacio y de cualquier pieza en él), factores de segundo orden (el espacio en relación con otros espacios) y factores de enésimo orden (dependencias de la historia de la posición).
Una función de evaluación artesanal generalmente tiene un término de balance de materiales que generalmente domina la evaluación. Los valores convencionales utilizados para el material son Reina=9, Torre=5; Caballo u Obispo=3; Peón=1; al rey se le asigna un valor arbitrariamente grande, generalmente mayor que el valor total de todas las demás piezas. [1] Además, normalmente tiene un conjunto de términos posicionales que generalmente no suman más que el valor de un peón, aunque en algunas posiciones los términos posicionales pueden volverse mucho más grandes, como cuando el jaque mate es inminente. Las funciones de evaluación artesanales suelen contener entre decenas y cientos de términos individuales.
En la práctica, las funciones de evaluación artesanales efectivas no se crean expandiendo la lista de parámetros evaluados, sino ajustando o entrenando cuidadosamente los pesos entre sí, de un conjunto modesto de parámetros como los descritos anteriormente. Para ello se utilizan posiciones de diversas bases de datos, como por ejemplo de juegos maestros, juegos de motor, juegos Lichess o incluso de autojuego, como en el aprendizaje por refuerzo .
Un ejemplo de función de evaluación artesanal para ajedrez podría verse así:
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.
Si bien las redes neuronales se han utilizado en las funciones de evaluación de los motores de ajedrez desde finales de la década de 1980, [7] [8] no se hicieron populares en el ajedrez informático hasta finales de la década de 2010, ya que el hardware necesario para entrenar las redes neuronales no era lo suficientemente potente en tiempo, y aún no se han desarrollado algoritmos de entrenamiento rápido ni topología y arquitectura 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 número entero , normalizado a la escala centipeón de modo que un valor de 100 es aproximadamente equivalente a un material. ventaja de un peón. Los parámetros de las redes neuronales normalmente se entrenan mediante aprendizaje por refuerzo o aprendizaje supervisado . Más recientemente, las funciones de evaluación en el 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 en los que una función de evaluación consta tanto de redes neuronales como de términos elaborados a mano.
Las redes neuronales profundas se han utilizado, aunque con poca frecuencia, en el ajedrez informático 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. Además 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 evaluación (la cabeza de valor ) y otra para ordenar movimientos (la cabeza de política ). ), en lugar de un solo resultado para la evaluación. [10] Además, si bien es posible establecer la salida del valor principal de la red neuronal de Leela en un número real para aproximarse a la escala de centipones utilizada en los motores de ajedrez tradicionales, de forma predeterminada la salida son los porcentajes de victorias, empates y pérdidas. 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 cuadradas (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 cuadradas consiste en tablas separadas para cada tipo de pieza por jugador, lo que en ajedrez da como resultado 12 tablas de piezas cuadradas en total. En el ajedrez informático se utilizan variantes más complejas de tablas de piezas cuadradas, siendo una de las más destacadas la tabla de piezas cuadradas de rey, 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 por sí sola. Los valores de las tablas son bonificaciones/penalizaciones por la ubicación de cada pieza en cada espacio, y codifican una combinación de muchos factores sutiles difíciles de cuantificar analíticamente. En las funciones de evaluación artesanales, a veces hay dos conjuntos de tablas: una para la apertura/medio juego y otra para el final; Las posiciones del medio juego se interpolan entre los dos. [13]
Desarrollada originalmente en shogi informático en 2018 por Yu Nasu, [14] [15] la función de evaluación más común utilizada en el ajedrez informático hoy en día [ cita necesaria ] es la red neuronal eficientemente actualizable , o NNUE para abreviar, una red neuronal escasa y poco profunda que solo tiene tablas de piezas cuadradas como entradas a la red neuronal. [16] De hecho, la arquitectura NNUE más básica son simplemente las tablas de 12 piezas cuadradas descritas anteriormente, una red neuronal con una sola capa y sin funciones de activación . Una arquitectura de red neuronal actualizable de manera eficiente, que utiliza tablas de pieza-rey como entradas, se transfirió 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 adoptada por muchos otros motores antes. finalmente se incorporará al motor oficial Stockfish el 6 de agosto de 2020. [18] [19]
Los motores de ajedrez utilizan con frecuencia tablas de finales en su función de evaluación, ya que permiten que el motor juegue 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, el número de prisioneros y la vida o muerte de los grupos en el tablero. Sin embargo, los programas informáticos modernos para jugar 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 ganancias/empates/pérdidas en lugar de un valor en número de piedras.