klondike

Si este blog siguiera algún orden lógico esta entrada debería ser la primera, pero bueno, más vale tarde que nunca, y si alguien me lo echa en cara le diré que el caos es parte del encanto de esta bitácora (una excusa como otra cualquiera).
Voy a tratar de dar una visión muy general y muy básica de qué partes tiene un programa de ajedrez y cómo encajan estos componentes para que el resultado final sea algo que "parece que piensa".

A primera vista puede dar la impresión de que un programa de juego debe ser algo muy complejo, pero no es así. De hecho, el esquema principal es simple y consta de pocas piezas. Básicamente si queremos montar un programa de ajedrez necesitamos:

1) Un generador de movimientos

2) Una parte que se encargue de buscar el mejor movimiento en cada turno

3) Una función de evaluación

Y nada más. Vamos a ver muy rápidamente cada uno de estos puntos.

La misón del generador es calcular todos los movimientos legales que se pueden realizar en una posición determinada. Para implementarlo nos va a hacer falta una forma de representar la posición de las piezas en el tablero, como ya contaba en la entrada anterior. Calcular los movimientos posibles no es una tarea especialmente difícil, cualquiera que sepa programar mínimamente y conozca las reglas del ajedrez puede hacerlo. Pero conviene ser cuidadoso con este código: es el motor de nuestro programa, el que tiene que alimentar con posiciones al siguiente componente y cuanto más rápido sea mejor para el resultado final.

A continuación necesitamos escribir código que procese las posiciones resultantes del generador. Es decir, necesitamos un algoritmo de búsqueda. En esto los programas no suelen ser muy originales, todos los que conozco (y el mío también) usan un algoritmo llamado minimax, que debemos a Von Newman (1928). Otro día si tengo ganas ya cuento algo sobre el minimax y sus sucesivas refinaciones (poda alfa-beta, negamax). De todas formas si te interesa el tema hay muchísima información sobre este algoritmo, creo que es de lo primero que se enseña en inteligencia artificial, y no te será difícil encontrar explicaciones y ejemplos.

Sólo para hacerse una idea de como trabaja el minimax, supongamos que es el turno de juego del programa. Lo primero que hacemos es llamar al generador para obtener las posiciones resultantes de cada uno de los movimientos legales. A continuación necesitamos obtener todas las posibles réplicas del contrario para cada uno de los movimientos, para lo que volvemos a llamar al generador.
Este proceso se repite cierto número de veces (dependiendo, por ejemplo, del tiempo del que dispone el programa para pensar). Una vez hemos llegado a este límite le pedimos a la función de evaluación que valore cada posición, asignando a cada una un valor numérico. Finalmente el algoritmo emprende el camino de vuelta por el árbol de posiciones, quedándose en cada nodo con el movimiento que lleva asociado una posición final más ventajosa, teniendo en cuenta que en cada nivel se invierte el turno de juego.

La función de evaluación es la última pieza de este esquema, y es bastante más fácil de explicar: se trata de una parte del programa que valora posiciones. Esta valoración puede ser tan simple como contar el material de uno y otro bando. Incluso una evaluación tan sencilla como esta ya permite a un programa jugar con cierto sentido al ajedrez, pero la podemos complicar mucho más, con un ojo puesto siempre en la velocidad y en el rendimiento, claro está: cuanto más sofisticada sea nuestra función de evaluación mejor jugará el programa pero más tiempo consumirá evaluando.

Dicen que esta es la parte más personal de un programa de ajedrez, casi todo depende del gusto del programador. Para empezar debe encontrar un buen equilibrio entre sofisticación en las valoraciones y velocidad del programa. Luego otorgará más o menos peso a los factores ajedrecísticos (peones pasados, actividad de las piezas, seguridad del rey, etc) dependiendo de su experiencia, conocimientos o personalidad ajedrecística. En resumen, la función de evaluación determina el carácter de cada programa de ajedrez, su estilo de juego, más que niguna otra cosa.

Parafraseando a Philidor: La función de evaluación es el alma de un programa de ajedrez.