klondike

En el contexto de los programas de ajedrez, cuando hablamos de representación del tablero nos referimos a la manera en que vamos a guardar la información sobre la situación concreta de la partida, básicamente la posición de las piezas en el tablero.

La forma en que almacenemos esta información será determinante para las funciones más básicas del programa (generación de posiciones). La elección del modelo de representación presumiblemente debe afectar mucho a aspectos como la rapidez de cálculo o el reconocimiento de patrones en una posición.

Conozco dos modelos de representación: guardar la información en una matriz de enteros o usar un modelo basado en tableros de bits (bitboards).
El primer método es el más simple, directo y evidente. Consiste en guardar la posición en una matriz de enteros, por ejemplo en una matriz de 8x8 y usar un código de valores para guardar la información, por ejemplo 0 para casillas no ocupadas por ninguna pieza, 1,2,3,4,5,6 para las piezas blancas y -1,-2,-3,-4,-5,-6 para las piezas negras.
Una variante de este método es usar una matriz mayor de 8x8, por ejemplo de 10x10, de esta forma es más fácil calcular movimientos (el control de los movimientos que caen fuera de los límites del tablero es más simple con estas dimensiones adicionales).
En este momento tengo dos versiones de mi programa, una que usa una matriz de 64 enteros y otra con una representación basada en una matriz de 144 elementos (12x12). Las diferencias en cuanto a rapidez de cálculo no son apreciables, pero el código de la segunda versión, la de la matriz con dimensiones adicionales, es más simple y claro.


Como alternativa a esta forma de guardar las posiciones tenemos el modelo de los tableros de bits. Aquí apenas voy a describir la idea general de esta forma de representación, puedes encontrar algo más en http://en.wikipedia.org/wiki/Bitboard
La información se guarda en matrices de bits de 8x8 y tenemos varios tableros de bits en lugar de uno solo. Cada uno guarda información de un aspecto concreto del tablero. Por ejemplo tenemos el tablero de los peones blancos en el que estarán activados los bits que correspondan a casillas ocupadas por un peón blanco, los demás bits estarán a 0.
La gran ventaja de este método es que permite hacer operaciones booleanas entre dos tableros que como resultado dan la solución a un problema concreto. Por ejemplo, para saber qué piezas captura un caballo blanco en e4 hacemos un AND del "tablero de saltos de caballo desde la casilla e4" con el "tablero de piezas negras". El resultado es otro tablero que tiene los bits de las capturas de caballo a 1.

Este modelo es muy atractivo, y además parece que se adapta muy bien al reconocimiento de patrones posicionales: algo ideal para un programa que pretende basar su fuerza en algo más que el cálculo de posiciones. Sin embargo no he escogido esta forma de representación para mi programa porque es más difícil de implementar que la matriz de enteros, y muchos fuertes programas actuales usan el método de la matriz única para guardar la información. Es decir, que el método simple tampoco parece malo de por sí.

Un problema fundamental al que se tienen que enfrentar cualquier programa de ajedrez es la inmensidad del árbol de posiciones.
En la posición inicial las blancas tienen 20 jugadas posibles. A cada una de estas jugadas las negras pueden responder con otras 20 jugadas distintas: tenemos ya un árbol con 400 nodos terminales y hemos buscado hasta una profundidad de 2 plys. El crecimiento de esta estructura es exponencial, de forma que a profundidad 5 ya tenemos un árbol con aproximadamente 20 elevado a 10 nodos terminales, y esto tirando por lo bajo. (¡10.240.000 millones de posiciones para evaluar!)

Calcular a una profundidad de 5 plys significa que evaluamos las posiciones resultantes tras efectuar 5 medias jugadas, no llegamos ni a 3 jugadas completas. Es decir, más bien poco, y para esto hemos tenido que examinar más de 10.000 millones de jugadas.
La rapidez de crecimiento del árbol de jugadas en cualquier juego está relacionada con el "factor de ramificación" que podemos definir como el número medio de jugadas legales que tiene un jugador a su disposición.
Según esta definición un juego como el tres en raya tiene un factor de ramificación de 3. El ajedrez tiene un factor mucho más alto: 35. Existen otros juegos, como el go, para los cuales el factor de ramificación es todavía más alto: un jugador de este juego puede elegir entre 100 jugadas legales por término medio en una posición determinada. Sin duda esto explica por qué todavía no se ha conseguido hacer un programa que juegue bien al go.

Con este panorama resulta obvio que hay que conseguir recortar el árbol de posiciones, conseguir que sea más pequeño de alguna manera. Una estrategia clásica, usada por el 99% de los programas de juego actuales es utilizar métodos de poda basándose en dos límites, uno para las blancas y otro para las negras. Así estas técnicas de poda se unen al clásico algoritmo de búsqueda minimax y consiguen reducir mucho el espacio de búsqueda. Esta estrategia se conoce con el nombre de poda alfa-beta.

Teniendo en cuenta lo anterior, incluír en el árbol de jugadas posibles además de las legales las ilegales parece una estrategia condenada al fracaso: no sólo tendremos más posiciones para evaluar, sino que además estaremos malgastando un tiempo precioso examinando posiciones ilegales.
Pues bien, aunque parezca mentira, existen motivos por los que puede ser más ventajoso examinar movimientos ilegales también. Concretamente se trata de aquellas jugadas que dejan al rey propio en jaque.
¿Cómo se explica esto? Pues por otro principio que debe cumplir cualquier programa de ajedrez que es el de la rápidez en la generación de movimientos. Para descartar los movimientos ilegales porque dejan a nuestro rey en jaque podemos hacer lo siguiente:
1) Calcular todos los movimientos posibles (pseudolegales)
2) Examinar cada uno de estos movimientos y determinar si el rey del bando que hace la jugada queda en jaque después de esta.
3) Eliminar de la lista de movimientos las jugadas que no superen el filtro anterior.
De esta forma nos aseguramos que el generador de movimientos sólo arroja jugadas legales, las únicas que pasan a formar parte del árbol de búsqueda. El problema es que implementar el paso 2) puede ser desesperantemente lento, aunque sospecho que esto puede variar según el método de representación del tablero que se haya elegido.
El caso es que para mi programita este proceso de filtrar los movimientos legales se tomaba mucho tiempo.
Pero existe una solución: No filtrar los jaques en la generación de movimientos. Entonces, ¿No nos arriesgamos a que el programa finalmente haga movimientos ilegales?
En realidad nunca lo hará. El generador nos devuelve una lista de movimientos legales e ilegales, y es el propio algoritmo de búsqueda el que descarta las variantes en las que el rey propio queda en jaque, simplemente porque recibirán una puntuación extremedamente baja (en mi programa al rey se le asigna un valor de 9999, mucho mayor que el de cualquier otra pieza: la dama por ejemplo, sólo tiene un valor de 920). Es decir, cualquier otra posición en la que no se haya capturado el rey tendrá mayor puntuación, con lo cual las posiciones que nacen de estas jugadas ilegales nunca serán elegidas por el programa.
Dos detalles más apoyan el éxito de esta estrategia:
En primer lugar las jugadas que dejan al rey propio en jaque son raras, la mayoría no lo hacen, por lo que supone un desperdicio de tiempo comprobar para todas y cada una de las jugadas posibles si el rey se puede capturar a la siguiente.
Y en segundo lugar, la técnica de poda alfa-beta y otras estructuras de control implementadas en el propio algoritmo de búsqueda se encargan de que estas posiciones "sin rey" no se expandan hasta la profundidad terminal: en cuanto se detecta una posición sin rey no se sigue profundizando y se pasa un valor en torno a -9999 al nodo padre.
Todo esto quiere decir que en realidad el número de jugadas a evaluar crece, sí, pero son sólo unas pocas jugadas más que si sólo pasaramos las jugadas legales al algoritmo de búsqueda.
¿Qué beneficio reporta esto en la práctica? Mi programita ha pasado de calcular menos de 10.000 posiciones por segundo a más de 50.000 sólo con este cambio.