klondike

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.