sábado, 24 de marzo de 2012

¿Cómo funciona un programa (engine) de ajedrez?

   
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:
  1. Un generador de movimientos
  2. Una función de evaluación
  3. 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).

7 comentarios:

  1. Como ya sabes, me gusta mucho el artículo. Los nuevos gráficos y cambios que has hecho también están muy bien.

    Me parece curioso lo sencillo que es un engine de ajedrez. Digo sencillo, aunque pillar la idea por encima me costó un par de relecturas de tu artículo, que a su vez requirió que tu lo pensaras y estructuraras de forma comprensible. Pero ya me entiendes, una vez que tienes la idea resulta más sencilla de lo que podría pensarse.

    De todas formas, ya sé que el "demonio está en los detalles" y que además solo has expuesto la idea general (espero próximos artículos sobre el podado alfa-beta ;-) ).

    Como no soy un buen jugador de ajedrez, me llama la atención la forma de las funciones de evaluación. Por ejemplo, el hecho de que los caballos tengan la menor puntuación es la posición inicial supongo que no es más que un "acicate" para que el programa decida moverlos, y puedo entender que cerca de los bordes tienen menos puntos por el simple hecho de que amenazan menos casillas; pero no veo con claridad por qué es mejor que estén en el centro. Supongo que está relacionado con esas cosas de "tomar el centro" que a veces se oyen a los ajedrecistas, aunque nunca las he entendido muy bien.

    ResponderEliminar
    Respuestas
    1. Sí, la verdad es que una vez visto, la idea general es relativamente sencilla, pero esto es (todos juntos) tan sólo la punta del iceberg. Sobre el tema de la búsqueda hay muchísimo más que escribir (sí, sí, empezando por la poda alfa-beta :) ). Ni que decir tiene que pasa parecido con las funciones de evaluación.
      Lo que comento sobre las piece-square-tables es una técnica muy sencilla que permite con poco esfuerzo que un engine pase de jugar de manera casi aleatoria a que parezca que sabe lo que hace. Sobre el psq del caballo en particular, el caballo es una pieza especialmente sensible a su situación en el tablero, en gran parte porque no es de largo alance y porque puede saltar sobre el resto. Por esa razón los caballos están especialmente mal en el borde del tablero (de hecho hay un dicho, "con los caballos por los rincones se gana por los co*ones"), y mucho más en las esquinas. Un caballo en una esquina sólo puede mover a dos casillas, y la movilidad es uno de los factores más importantes en la evaluación de una posición(de hecho hay engines que no aplican las psq y, entre muchas otras cosas, se fían en la movilidad de las piezas). Un caballo en el centro del tablero, además de dominar tantas casillas como es posible, suele ser bastante incómodo para el contrario.

      Eliminar
  2. Respuestas
    1. Si te refieres al lenguaje de programación, elige el que más te guste. En realidad los lenguajes más elegidos suelen ser C/C++ por aquello de la optimización/popularidad, pero en mi opinión, a no ser que pretendas hacer un engine que se encuentre entre los top ten (para lo cual haría falta mucho tiempo y talento), simplemente usa el lenguaje en el que te sientas más cómodo.

      Eliminar
    2. Interesante articulo.

      Hace pocos dias, sin haber investigado nada, estaba tratando de pensar en el bus, como se podria llevar un sistema de valoracion matematica al ajedrez. Siempre habia tratado de buscarlo mediante ecuaciones para intentar lograr enseñar matematicas con el ajedrez: al ir avanzando en el nivel del juego, intuitivamente luego de ver geometrias en el juego -triangulaciones, etc- , uno luego puede "ver" ecuaciones (si hay geometrias, estas son formadas por lineas, las cuales son rectas donde y=mx+n) : de hecho el alfil se mueve por una recta y el tablero es un sistema cartesiano (x,y), por lo cual pensaba que es muy posible que los sistemas matriciales de ecuaciones puedan estar presentes como modo de decision en el juego; pero es necesario abstraerlos, ya que el cerebro intenta valorar mas las piezas que esta otra informacion abstracta pero implicita.

      Al leer un articulo del juego de 'go' y como un jugador (no recuerdo si Tahl o Lasker o alguien asi se vio extremadamente influenciado por la forma de resolverse en ese juego y extrapolarlo al ajedrez), llegue a entender que finalmente se trata de valorar la casilla, donde la pieza le entrega un valor añadido a la casilla. De ahi asigne a cada casilla del tablero un valor, acorde a su centralidad y he llegado a ver que existe un sistema de "capas superpuestas" de valoracion de cada casilla, segun cada jugada que se haga. Asi, llegue a un sistema similar al 'pst', pero he visto que existen muchas capas de formas de valorar las casillas del tablero. Por ejemplo: se puede valorar la posicion, la capacidad combinativa de piezas, casillas debiles, fuertes, piezas debiles, fuertes, pasillos de casillas vacias, el jaque, la falta de enroque, el enroque, la coronacion del peon y sus distintas posibilidades, etc... .sin olvidar que hay valoraciones relativas (un caballo vale mas que una torre en posiciones cerradas, lo que suele transformar la decision en cada jugada acorde a un criterio de valoracion). Si vemos mas alla, el ajedrez tendria que ser siempre tablas, ya que por cada jugada que se haga siempre habra una respuesta "solida" del rival. Por ello es que los GM y campeones mundiales casi solo entablan, ya que se anulan las fuerzas, frente a mayor capacidad de valoracion del juego. Pero vemos que en el hecho practico los partidos ganados son los que deciden y existen mas partidos ganados o perdidos que tablas en la vida de un ajedrecista y la menor cantidad de resultados son tablas: esto genera un detalle exquisito: la capacidad interpretativa del cerebro humano. ¿como es posible asignar un valor a la interpretacion valorica que hace el cerebro? (incluyendo la capacidad de desgaste o cansancio, luego de un partido, o la motivacion de querer atacar, o el temor a perder posicion, etc.)

      PD: ¿sabes de algun programa que pueda generar niveles (capas de informacion de pst)?
      (me interesarìa poder entender el ajedrez matematicamente en forma sencilla (ojala tambien ecuaciones), para poder enseñarlo en un colegio a niños, de manera que poder incentivar el estudio de matematicas pero a manera de juego. No soy profesor, pero serìa formidable trabajar en algo que nos apasiona (ajedrez) dandole un incentivo a alguien que podria cambiar su futuro. Quizas existan muchos bobby fischer que no sepan que su futuro son las matematicas o el ajedrez...

      Eliminar
    3. Hola Alberto

      La verdad es que el tema de las funciones de evaluación en los motores de ajedrez, a la vez que puede dar para docenas de páginas, en lo relacionado a la programación es relativamente sencillo; prácticamente está ya todo escrito, desde qué características de una posición valorar a cómo hacerlo. Es decir, para cada característica de la posición (por ejemplo, valoración de un peón doblado), es sencillo hacer una función que sea eficiente detectándolos y luego simplemente añadir una cierta penalización (digamos de una décima de peón) por cada uno que se encuentre.
      Sobre relacionar las matemáticas y el ajedrez en las escuelas, quizás te pueda servir el acecamiento a la evaluación que hace Hans Berliner en su libro "The system" (si conoces el "Mi sistema" de Nimzowitsch enseguida caerás en la cuenta de que el amigo Hans no se anda por las ramas):
      http://www.euroschach.de/Hans-Berliner--The-System.html

      Por otro lado, si te manejas bien en inglés, puedes intentar a plantear cuestiones sobre motores de ajedrez en este foro:
      http://talkchess.com

      La dirección para acceder al código de Secondchess:
      https://github.com/emdio/secondchess

      Finalmente, por si te quieres hacer una idea de lo compleja que puede llegar a ser una función de evaluación de un motor "de verdad" puedes echar un ojo al código de Stockfish, que ahora mismo se encuentra entre los mejores:
      https://github.com/mcostalba/Stockfish

      Un saludo

      Emilio

      Eliminar
  3. al hacer clik en el enlace de secondchess:

    'Certificado de servidor no válido

    Intentaste llegar a github.com, pero el servidor ha enviado un certificado no válido.'

    ResponderEliminar