Función de evaluación

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 (generalmente en una hoja o nodo terminal) en un árbol de juego. La mayoría de las veces, el valor es un número real o un número entero cuantificado, a menudo en né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 de la unidad, que representa los porcentajes de ganancias, empates y pérdidas de la posición.

No existen modelos analíticos o teóricos para funciones de evaluación de juegos no resueltos, ni 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. Ahora existe un cuerpo significativo de evidencia 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 de computadora emplean funciones de evaluación incluyen ajedrez, go, shogi (ajedrez japonés), othello, hex, backgammon y damas. 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. Algunos juegos como el tres en raya están fuertemente resueltos y no requieren búsqueda ni evaluación. porque un árbol de solución discreto está disponible.

Relación con la búsqueda

Un árbol de dichas evaluaciones suele formar 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 solo observa 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 reposo 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 ganancia, una pérdida o un empate en el nodo.

Existe una relación compleja 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 a corto plazo y motivos posicionales de largo plazo más sutiles en la evaluación. También existe una compensación 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. Dado 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 capacitada sustancialmente para que funcione de manera efectiva en otra aplicación.

En ajedrez

En ajedrez, 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 la pieza de ajedrez. El número entero 1 suele representar una fracción de un peón, y los centipawns, que se utilizan comúnmente en el ajedrez informático, son una centésima parte de un peón. Las evaluaciones más grandes indican un desequilibrio material o una ventaja posicional o que una ganancia 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.

Funciones de evaluación artesanales

Históricamente, en el ajedrez computarizado, 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 descubrirlos a través de redes neuronales de entrenamiento. 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 únicamente del espacio y cualquier parte de él), factores de segundo orden (el espacio en relación con otros espacios) y factores de n-é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 usados para el material son Reina=9, Torre=5; Caballo o Alfil=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. Además, por lo general 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 ser mucho más grandes, como cuando el jaque mate es inminente. Las funciones de evaluación hechas a mano suelen contener de docenas a cientos de términos individuales.

En la práctica, las funciones de evaluación artesanales efectivas no se crean expandiendo nunca 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 juegos maestros, juegos de motor, juegos de Lichess o incluso de auto-juego, como en el aprendizaje por refuerzo.

Ejemplo

Un ejemplo de una función de evaluación artesanal para el ajedrez podría tener el siguiente aspecto:

• c₁ * material + c₂ * movilidad + c₃ * seguridad real + c₄ * control central + c₅ * estructura de peón + c₆ * rey tropismo +...

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 de 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, incluyendo espacios ocupados por piezas amistosas o contrarias. También se puede tener en cuenta la movilidad efectiva, o el número de espacios "seguros".
• La seguridad del rey es un conjunto de bonificaciones y sanciones evaluadas para la ubicación del rey y la configuración de peones y piezas adyacentes o frente al rey, y piezas opuestas que llevan en espacios alrededor del rey.
• El control del centro se deriva de cuántos peones y piezas ocupan o llevan en los cuatro espacios centrales y a veces los 12 espacios del centro extendido.
• La estructura de los peones es un conjunto de sanciones y bonificaciones para varias fortalezas y debilidades en la estructura de los peones, tales como multas por peones dobles y aislados.
• El tropismo rey es un bono para la cercanía (o penalización por distancia) de ciertas piezas, especialmente reinas y caballeros, al rey opuesto.

Redes neuronales

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, 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 ese momento. y aún no se han desarrollado algoritmos de entrenamiento rápido y topología 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 de la placa y cuya salida es un número entero, normalizado a la escala centipawn, de modo que un valor de 100 es aproximadamente equivalente a un material. ventaja de un peón. Los parámetros en las redes neuronales generalmente se entrenan mediante el aprendizaje por refuerzo o el aprendizaje supervisado. Más recientemente, las funciones de evaluación en el ajedrez informático han comenzado a utilizar múltiples redes neuronales, cada una de las cuales está 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 de redes neuronales y términos hechos a mano.

Las redes neuronales profundas se han utilizado, aunque con poca frecuencia, en el ajedrez informático después de que Matthew Lai's Giraffe en 2015 y Deepmind's AlphaZero en 2017 demostraran la viabilidad de las redes neuronales profundas en las 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 la ordenación de movimientos (el encabezado de la política), en lugar de solo una salida para la evaluación. 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 centipawn utilizada en los motores de ajedrez tradicionales, por defecto la salida son los porcentajes de ganar-empatar-perder., un vector de tres valores cada uno del intervalo unitario. 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.

Mesas pieza-cuadrado

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. 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 el ajedrez da como resultado 12 tablas de piezas cuadradas en total. En el ajedrez informático se utilizan variantes más complejas de mesas de piezas cuadradas, una de las más destacadas es la mesa de piezas cuadradas del rey, utilizada en Stockfish, Komodo Dragon, Ethereal y muchos otros motores, donde cada mesa considera la posición de cada uno. tipo de pieza en relación con el rey del jugador, en lugar de la posición de cada tipo de pieza por separado. Los valores en 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.

Una función de evaluación artesanal común utilizada en el ajedrez informático es la Solo tabla de piezas cuadradas, o PeSTO para abreviar, que es una función de evaluación muy simple que consta de términos materiales. y sólo dos juegos de mesas cuadradas de piezas, una para la apertura y otra para el final, para los términos posicionales. Sin embargo, PeSTO es capaz de desempeñarse tan bien como muchas otras funciones de evaluación artesanales que se utilizan en el ajedrez informático. PeSTO fue creado por primera vez por Tomasz Michniewski en 2003 con el nombre de "Función de evaluación simplificada", y Ronald Friederich introdujo el nombre actual cuando implementó PeSTO en su motor rofChade.

Desarrollada originalmente en el shogi informático en 2018 por Yu Nasu, la función de evaluación más común utilizada en el ajedrez informático hoy en día es la red neuronal actualizable eficientemente, o NNUE para abreviar, una red neuronal escasa y poco profunda que solo tiene tablas de piezas cuadradas como entradas en la red neuronal. De hecho, la arquitectura NNUE más básica es 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 cuadradas de reyes como sus 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, y fue adoptado por muchos otros motores antes de ser finalmente incorporado en el motor oficial de Stockfish el 6 de agosto de 2020.

Bases de tablas de finales

Los motores de ajedrez suelen utilizar tablas de finales en su función de evaluación, ya que permiten que el motor juegue perfectamente en el final.

En marcha

Históricamente, las funciones de evaluación en Go tenían en cuenta tanto el territorio controlado, la influencia de las piedras, el número de prisioneros y la vida y 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.