Desde hace un tiempo estoy interesando en el mundo de los engines de ajedrez, y aunque en gran parte me sirva para aclararme, creo que puede ser un tema interesante.
Básicamente un engine de ajedrez
necesita tres componentes esenciales:
Un generador de movimientos
Una función de evaluación
Una función de búsqueda
El generador de movimientos se encarga
de crear una lista de los movimientos posibles en un posición
determinada, así como de chequear la legalidad de los mismos. Esta
es una de las partes más difíciles, ya que es muy “bug prone”.
El generador de movimientos debe ser capaz también de deshacer
movimientos, por razones que veremos más adelante.
La función de evaluación (que se
suele denominar “estática”, ya que evalúa factores puramente
estáticos tales como el material, la estructura de peones, la
seguridad del rey, etc. pero no se para a mirar si, por ejemplo, en
el siguiente movimiento vamos a perder la dama: de eso se encarga la
función de búsqueda, como se explica más adelante) tiene la
finalidad de asignar una valoración a una posición dada. La
implementación más sencilla sería la puramente material: contar el
material que hay por cada bando en el tablero. La evaluación se
suele dar tomando el valor de un peón como 100, y el resto de las
piezas en función de esta. Así, valores típicos para las piezas
serían de 100 para los peones, 300 para caballos y alfiles, 500 para
las torres y 900 para las damas.
Sin embargo, una evaluación basada
solamente en el material daría lugar a un engine muy débil. Por
ejemplo, valoraría como igualada una posición con equilibro
material, aunque uno de los bandos tuviera todas sus piezas
desarrolladas y el otro las mantuviera en sus casillas iniciales.
Además mientras no viera una ganancia de material, todos los
movimientos le parecerían equivalentes, dando lugar a un juego
cuasialeatorio.
Una mejora realmente sencilla y muy
eficiente son las piece square tables (pst). Se trata de
asignar una puntuación extra a cada pieza dependiendo del tipo de
pieza en cuestión y de su posición en el tablero. Por ejemplo, una
pst para los caballos blancos podría ser la siguiente;
int
knight_pst[64] = {
-10,
-10, -10, -10, -10, -10, -10, -10,
-10,
0, 0, 0, 0, 0, 0, -10,
-10,
0, 5, 5, 5, 5, 0, -10,
-10,
0, 5, 10, 10, 5, 0, -10,
-10,
0, 5, 10, 10, 5, 0, -10,
-10,
0, 5, 5, 5, 5, 0, -10,
-10,
0, 0, 0, 0, 0, 0, -10,
-10,
-30, -10, -10, -10, -10, -30, -10
};
El primer elemento del array es la
casilla a8, y el último la h1. Cuando la función de evaluación
escanee el tablero en una posición determinada, al encontrarse con
un caballo blanco en la casilla n-sima, le dará un bonus (o malus)
que será el valor n-simo (en puridad “n-simo menos uno”) del
array knight_pcsq. Podemos ver que con esta pst para los caballos,
como norma general se penaliza que se sitúen en los bordes del
tablero y se incentiva que estén en el centro del mismo. Con algunas
pst más para el resto de piezas (añadido a la evaluación material)
el juego del engine pasa a ser con mucho más sentido a un coste muy
bajo.
Por convenio se suele tener que la
función de evaluación da valores positivos cuando la ventaja es de
las blancas y negativos cuando la ventaja es de las negras.
La verdad es que por lo dicho hasta
ahora nada diferencia cómo juega un programa de ajedrez de cómo lo
hace un humano. Básicamente hemos dicho que debe saber las reglas
(generador de movimientos) y que tenga ciertos conocimientos para
evaluar si una posición es mejor que otra (función de evaluación).
Pero a partir de aquí, ¿cómo usa estas herramientas un engine de
ajedrez? Una vez que sabemos mover las piezas y evaluar la posición,
el paso siguiente es buscar el mejor movimiento de todos los
posibles.
Para seguir con esto debemos introducir
al menos un término para no inducir a errores, el ply de
profundidad. Cuando se habla de ajedrez, se suele entender que “un
movimiento” equivale a que el bando blanco y el negro han movido.
Sin embargo, en el mundo de los engines de ajedrez, la unidad
fundamental de movimientos es el “ply”, que es simplemente un
movimiento hecho por cualquiera de los bandos. Así, para calcular
nuestro movimiento y la respuesta del rival, estamos analizando con
una profundidad de 2 plies. O si un engine dice que ha analizado con
una profundidad de 14 plies, se puede “traducir” como que ha
profundizado a 7 movimientos.
Una vez dicho esto, supongamos que un
engine quiere decidir cuál es el mejor movimiento disponible a una
profundidad de 3 plies (es decir, movemos nosotros, mueve el
contrario, y respondemos). El árbol de variantes (el esquema de
todos los posibles movimientos hasta una determinada profundidad)
tendría un aspecto similar a este:
Por supuesto, un árbol de variantes de
una posición cualquiera es mucho más profuso, pero por razones
prácticas se ha reducido drásticamente. El número “23”, abajo
a la izquierda, debajo de la celda en la que pone “e4”,
significa:
“Si en la posición actual yo muevo
d4 y el contrario mueve d6 y yo respondo e4, entonces la valoración
de la posición es de 23 (centésimas de peón, es decir, ligeramente
favorable al blanco)”. Y así con el resto. Un dato importante: la
función de evaluación sólo se aplica a las posiciones últimas,
las que se encuentran en la última fila (llamados leaf nodes).
Vale, supongamos entonces que hemos
creado el árbol de variantes hasta la profundidad deseada y que
tenemos las puntuaciones de todas (to das) las posiciones
resultantes. Lo primero que se nos puede ocurrir es algo como “bueno,
cojamos el movimiento que mayor puntuación da a nuestro bando y ya
está, es decir, 35, tras jugar d5 en el ply 3”. Para que se dé
esa posición, nosotros debemos mover primero d4, entonces el negro
debe mover Cc6, y vualá, hacemos d5 y a seguir jugando. Pero estamos
obviando algo: el negro no tiene ninguna obligación de responder Cc6
a nuestro d4. De hecho, lo que tratará de hacer el negro tras cada
movimiento nuestro, es precisamente elegir el movimiento que menos le
perjudique (o más le beneficie). Es decir, si nosotros movemos d4,
precisamente el negro evitará mover Cc6, porque él es tan buen
jugador como nosotros, y verá que tras d4, Cc6, d5 da ventaja al
blanco.
De modo que si el blanco mueve d4, ¿qué
movimiento elegirá el negro? Pues el que deje la peor mejor opción
al blanco, teniendo en cuenta que el blanco moverá maximizando sus
posibilidades. Si hemos llegado hasta aquí, veremos enseguida que la
respuesta del negro a d4 del blanco será 0-0, que deja como mejor opción del blanco Tb1, con -12 (ligera ventaja negra). Es decir, a
la posición que se da tras d4 y 0-0 se le asigna una valoración de
-12, y esta valoración no la hemos sacado de aplicar la función de
evaluación a dicha posición sino de las valoraciones de las
posiciones derivadas.
La misma técnica se aplica sobre cada
serie de movimientos que tienen un padre común, y llegaríamos a
tener un diagrama como el siguiente:
Las valoraciones de las posiciones tras
el ply 2, en marrón (sí, soy un petardo eligiendo colores), se
obtienen maximizando los valores que ha devuelto la función de
evaluación en el ply 3 a las posiciones hijas, en azul. Sin embargo,
los valores de las posiciones tras el ply 1 se obtienen minimizando
las puntuaciones del ply 2 (por eso a esta técnica se la llama
mini-max). Ocurre que cada vez que subimos o bajamos un ply, cambia
el bando que mueve. Así, cuando mueve el blanco, trata de maximizar
la puntuación, mientras que el negro trata de minimizarla.
Finalmente, aplicando el mismo sistema, llegamos a la conclusión de
que la valoración de la posición a tres plies de profundidad es de
11 centésimas de peón (ligera ventaja blanca).
Nótese que tal y como comentaba, la
función de evaluación sólo se usa en las posiciones finales [por
cierto, en todo este proceso estamos suponiendo que nuestra función
de evaluación es “la verdad”. Evidentemente, ninguna función de
evaluación es perfecta (aunque algunas se acercan bastante), pero es
que sencillamente es lo que tenemos], y es a partir de estos valores
como se toma la decisión del mejor movimiento.
También aquí vemos por qué el
generador de movimientos debe ser capaz también de deshacerlos. Al
comenzar a analizar, lo primero que se hace es generar los
movimientos disponibles. Si entonces no nos encontramos en el ply de
profundidad deseado, volvemos a generarlos hasta que se cumpla la
condición. De modo que la función de búsqueda (que es como se
suele llamar, ya que se encarga de buscar el mejor movimiento en el
árbol de variantes) es recursiva, llamándose a sí misma y
generando los movimientos posibles hasta llegar a la profundidad
deseada. Entonces se aplica la función de evaluación a las
posiciones, y se deben deshacer los movimientos para seguir
moviéndonos por el árbol de variantes.
Bueno, para una introducción puede
valer. Evidentemente tanto sobre la generación de los movimientos
como sobre la evaluación y la búsqueda hay muchísimo más que
contar, pero creo que con esto puede ser suficiente para hacernos una
primera idea de cómo funcionan estos programitas. En próximas
entradas trataré de explicar algunos de estos asuntos con más
detalle.
PS: si alguien tiene curiosidad por ver el código de alguno de estos programas, hay bastantes, y algunos muy fuertes, que están bajo licencia GPL o open source. En particular servidor tiene debilidad por secondchess, un engine que se basa en un código en C escrito por Pham Nguyen llamado firstchess, con fines puramente didácticos. El código de secondchess se puede encontrar aquí (muy comentado y con un nivel de juego medianamente interesante, en especial teniendo en cuenta lo sencillo que es).
