Función de evaluación - Evaluation function

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. Un árbol de tales evaluaciones suele ser parte de un minimax o paradigma de búsqueda relacionado que devuelve un nodo en particular y su evaluación como resultado de seleccionar alternativamente el movimiento más favorable para el bando en movimiento en cada capa del árbol del juego. El valor es un escalar cuantificado, a menudo en n THS del valor de una pieza de juego, como una piedra en el camino o un peón en el ajedrez. n puede ser décimas, centésimas u otra fracción conveniente.

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 solo 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 valoració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 inactiva 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.

No existen modelos analíticos o teóricos para funciones de evaluación para juegos no resueltos, ni tales funciones son completamente 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 evidencia para varios juegos como el ajedrez, el shogi y la composición general de las funciones de evaluación para ellos.

El enfoque general para construir funciones de evaluación es como una combinación lineal de varios términos ponderados determinados para influir en el valor de una posición. Se puede considerar que cada término está compuesto por factores de primer orden (aquellos que dependen solo del espacio y cualquier pieza del mismo), 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).

Existe una intrincada relación entre la búsqueda y el 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 horizonte largo 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. 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, por lo general, tendrá que reajustarse sustancialmente para que funcione de manera eficaz en otra aplicación.

Los juegos computarizados que emplean funciones de evaluación incluyen ajedrez , go , shogi (ajedrez japonés), othello , hex y damas . Algunos juegos como tic-tac-toe están fuertemente resueltos y no requieren búsqueda o evaluación porque hay disponible un árbol de solución discreto.

En ajedrez

Las funciones de evaluación en el ajedrez consisten en un término de balance de materiales que domina la evaluación, más 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. . Una función de evaluación también codifica implícitamente el valor del derecho a moverse, que puede variar desde una pequeña fracción de un peón hasta ganar o perder. En el final del juego, es posible construir posiciones en las que gane quien se mueva, aunque por lo demás la posición está en equilibrio; también es posible construir posiciones donde quien deba moverse pierde ( Zugzwang ).

Una función de evaluación para el ajedrez podría tomar la forma

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 del material de los blancos o la puntuación posicional menos el de los negros. La puntuación de material se obtiene asignando un valor en unidades de peón a cada una de las piezas. Los valores convencionales son: Reina = 9, Torre = 5; Caballero 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. No solo importa el valor absoluto del material, sino también la relación entre el material blanco y negro: sacrificar un peón en la apertura puede conferir una ventaja posicional (la relación material apenas se ve afectada), pero el plus de un peón en un rey y El juego de final de peón suele ser suficiente para ganar (la proporción de material es grande). Esta proporción generalmente se implementa como un bono de cambio de acuerdo con la regla empírica: 'intercambia piezas pero no peones cuando estás adelante, y viceversa cuando estás atrás'. La puntuación de 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 o contrarias. 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 movilidad efectiva de las reinas suele ser muy baja, aunque el número de movimientos legales puede ser bastante alto. La puntuación de seguridad del rey es un conjunto de bonificaciones y penalizaciones que se evalúan según la ubicación del rey y la configuración de los peones y piezas adyacentes o delante del rey, y las piezas opuestas que se encuentran en los espacios alrededor del rey. El control del centro se deriva de cuántos peones y piezas ocupan o se apoyan 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 por varias fortalezas y debilidades en la estructura de peones, como penalizaciones por peones doblados 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 caballeros, al rey contrario.

Los pesos c1, etc., no son necesariamente constantes; son coeficientes de aplicación que pueden variar con la etapa del juego (apertura, medio juego, final), piezas en el tablero (por ejemplo, presencia o ausencia de reinas), otras características del juego. posición, o estrategia o planes de alto nivel (por ejemplo, asigne un mayor peso a las piezas que se colocan en los cuadrados alrededor del rey contrario si el plan es un ataque en el flanco de rey).

El enfoque, y por lo tanto los términos y pesos relevantes de la función de evaluación, difieren según la etapa del juego. En la apertura, las consideraciones dominantes son el desarrollo de las piezas menores, el enroque y seguridad del rey y el control del centro. Las penalizaciones se suelen imponer por piezas no desarrolladas y enroque retrasado. En los finales, la promoción de peones o el apareamiento con las piezas son las consideraciones dominantes. En situaciones de apareamiento, los factores relevantes son la distancia del rey objetivo desde el borde o esquina del tablero, y la proximidad del rey y las piezas de apareamiento al rey contrario. Para los finales de rey y peón, los factores relevantes son la proximidad de los reyes a los peones, el avance de los peones y el control de las casillas de reina.

La ecuación es un modelo conceptual. En una implementación particular, cada pseudo-término compuesto puede estar representado por un puñado o posiblemente cientos de términos individuales, cada uno con su propio peso o valor calculado. Por ejemplo, la estructura de peones puede tener términos para aislados, doblados, atrasados, avanzados, pasados, pases protegidos, pases conectados, huecos, filas semiabiertas y abiertas, mayorías de peones, falanges y muchas otras formaciones. Otros factores especiales que a menudo se consideran son: desarrollo de las piezas menores, torres en filas abiertas o séptima fila, torres dobladas, caballeros de avanzada (caballeros en ubicaciones centrales protegidos por un peón y no sujetos al ataque de un peón contrario), posesión de la pareja de alfiles, alfiles en las diagonales largas, piezas que ocupan espacios alrededor del rey oponente o que se relacionan con ellos, y movilidad de los reyes (los reyes no deben estar "apiñados", por lo tanto sujetos a mate en movimiento). Algunos términos, como la seguridad del rey en un final con pocas piezas, pueden y deben ignorarse según el contexto.

Los términos que componen algunos factores, como la seguridad del rey, se combinan de forma no lineal: una debilidad en la seguridad del rey, como una fila abierta adyacente al rey, puede ser penalizada, por ejemplo, con 1/4 de peón, pero puede ser necesario penalizar dos debilidades. uno o incluso dos peones completos, y tres debilidades por pieza, torre o incluso más porque el jaque mate se está convirtiendo en una posibilidad probable. Los factores relacionados con el avance y la promoción de peones también se combinan de forma no lineal.

Los valores típicos de peones múltiples asignados a las piezas tampoco son constantes, sino que dependen del contexto: las piezas sin desarrollar valen mucho menos al igual que las piezas con movilidad reducida por cualquier motivo: alfiles confinados por sus propios peones ("el alfil malo") ; los caballos pierden valor a medida que la posición se despeja de piezas, y los alfiles y las torres ganan valor; las reinas valen mucho más si el rey contrario no está protegido contra jaques.

Las funciones de evaluación suelen contener decenas a cientos de términos individuales, y la evaluación de una posición suele oscilar entre más o menos una pequeña fracción de un peón. Las evaluaciones más amplias indican un desequilibrio material o que una ganancia de material suele ser inminente. Evaluaciones muy amplias pueden indicar que el jaque mate es inminente.

En la práctica, las funciones de evaluación eficaces se crean no ampliando nunca la lista de parámetros evaluados, sino ajustando cuidadosamente los pesos entre sí, de un conjunto modesto de parámetros como los descritos anteriormente. Con este fin, se emplean posiciones ejemplares de los juegos de maestros y la eficacia de la función de evaluación se mide por el porcentaje de movimientos seleccionados que concuerdan con las elecciones de los maestros.

Mesas cuadradas

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 valor de piezas) para la evaluación. Cada tabla es un conjunto de 64 valores correspondientes a los cuadrados del tablero de ajedrez. Hay una mesa separada para cada tipo de pieza: rey, reina, caballo, alfil, torre, peón. Hay un juego de mesas separado (volteado) para las piezas opuestas. Los valores en las tablas son bonificaciones / penalizaciones por la ubicación de cada pieza en cada espacio. Los valores codifican una combinación de muchos factores sutiles difíciles de cuantificar analíticamente. Las tablas básicas se pueden construir a partir de principios de desarrollo, control del centro, seguridad del rey, etc. En los programas de nivel maestro y más allá, las mesas se construyen a partir de una combinación de posiciones ocupadas por las piezas en los juegos maestros, ajustadas para la aplicación. Por ejemplo, los caballos rara vez se encuentran en los bordes izquierdo y derecho del tablero en los juegos maestros, por lo que se puede asignar un valor de penalización a esos espacios de la tabla de piezas cuadradas de caballos proporcional a la poca frecuencia con que se encuentra un caballo en los juegos maestros. A menudo hay dos juegos de tablas: una para la apertura y otra para el final; las posiciones del juego intermedio se interpolan entre los dos. Los autores de programas de ajedrez tienden a mantener en secreto la composición de sus tablas de piezas cuadradas, así como los métodos utilizados para crearlos, porque se dedica una gran cantidad de tiempo, esfuerzo, pruebas y experiencia de juego para construirlos, y un ajuste cuidadoso aquí. ofrece una ventaja competitiva.

Evaluación en la búsqueda de árboles de montecarlo

Las máquinas de ajedrez como Leela Chess Zero tienen un paradigma de búsqueda y evaluación sustancialmente diferente al esquema convencional de alfabeta / minimax con evaluación de nodo hoja. En la búsqueda del árbol de montecarlo, el espacio de búsqueda de todas las variaciones de un nodo se muestrea desplegando o jugando el juego hasta el final eligiendo alternativamente un movimiento aleatorio para cada lado. El resultado, ganar, perder o empatar, se respalda en el nodo inicial. La jugada seleccionada es la que conduce a una posición con el mayor número de victorias, o la puntuación promedio más alta, aunque no se asocia una línea de juego específica con la jugada. Una situación análoga es el porcentaje de victorias / empates / pérdidas acumuladas para varias aperturas empleadas en juegos maestros. Si uno elige una apertura, tenderá a elegir entre las que tienen el mayor porcentaje de victorias o el mayor porcentaje de victorias + empates. Y de manera similar para cada variación dentro de la apertura, si hay estadísticas disponibles. La debilidad de tal esquema es que las líneas de juego más fuertes para cada lado pueden no ser parte de esa apertura; pueden ser oportunidades estrechas en una apertura que por lo demás es débil.

Entonces, la 'evaluación' en las implementaciones de montecarlo es una probabilidad de ganar en lugar de una valoración numérica de una posición.

En ir

Las funciones de evaluación en Go tienen en cuenta tanto el territorio controlado, la influencia de piedras, el número de presos y la vida y muerte de los grupos en el tablero.

Ver también

Referencias

Shannon, Claude, 1950, "Programación de una computadora para jugar al ajedrez", Revista filosófica, Ser.7, vol. 41, núm. 314.
Slate, D y Atkin, L., 1983, "Chess 4.5, the Northwestern University Chess Program" en Chess Skill in Man and Machine 2nd Ed., Págs. 93-100. Springer-Verlag, Nueva York, NY.
Ebeling, Carl, 1987, Todos los movimientos correctos: Una arquitectura VLSI para el ajedrez (Disertación distinguida de ACM), págs. 56–86. Prensa del MIT, Cambridge, MA
Guía de evaluación de stockfish, [1]

Languages

In other projects