| < Un buen algoritmo ... | [Cheoss] [índice] | Mejoras en la búsqueda > |
El efecto horizonte es un problema inherente al minimax y que es imposible eliminar por completo. Se presenta cuando se envía a evaluar una posición intermedia en una secuencia táctica.
Consideremos un par de ejemplos:
En una secuencia de cambios tácticos
el programa captura una torre. El motor evalúa esta posición con
un valor de +5 porque tiene una torre más que su adversario. A la siguiente jugada
el rival corona un peón que estaba en la séptima fila. Se ha producido el temido efecto
horizonte. El programa evaluó una posición intermedia en una secuencia táctica y obtuvo una
valoración errónea.
Otro ejemplo más: supongamos que es el turno de juego del programa con blancas.
La función de búsqueda empieza a construir su árbol de variantes y en uno de los nodos
terminales asigna un valor de +10 a la posición.
La valoración tan alta se explica porque el programa acaba de comerse la dama de su
rival. Si contamos el material que hay en el tablero vemos que las blancas tienen una
dama de más y por tanto la función de evaluación valora esta posición con una ventaja
de 10 puntos.
Pero si seguimos mirando una jugada más allá vemos que las negras restablecen la igualdad
material porque capturan la dama blanca en el siguiente movimiento. Es decir, lo que al
programa le parece una captura de dama en realidad es un simple cambio. El desastre puede ser
total si para llegar a ese cambio de damas el programa ha sacrificado material confiando en
que al comerse la dama enemiga saldría ganando finalmente.
El efecto horizonte continúa apareciendo sea cual sea la profundidad de búsqueda. No importa si el programa puede ver hasta una profundidad de 4, 5 o 16 jugadas: si las posiciones de los nodos terminales son posiciones intermedias en una secuencia de cambios el efecto horizonte impedirá al programa jugar bien.
Esta ceguera suicida es parte del algoritmo de búsqueda empleado por los programas de ajedrez y si bien no se puede eliminar completamente sí se puede mitigar en gran parte.
Si tratamos de poner esto en práctica de forma directa extendiendo la búsqueda hasta llegar a posiciones estables pronto se descubre que no vamos a llegar muy lejos: la búsqueda de las posiciones estables extiende demasiado el árbol, es peor el remedio que la enfermedad.
Esta nueva función es igual que la normal, con poda alfa beta incluida. La diferencia es el generador de movimientos que utiliza. Se trata de un generador distinto del principal. Esta vez sólo calculamos jugadas "peligrosas", básicamente capturas, jaques y promociones de peón. Antes, cuando describíamos el problema del efecto horizonte vimos que se trata de vuelcos repentinos que ocurren en la valoración de la posición. Estos vuelcos suceden casi siempre cuando están involucradas jugadas del mismo tipo que calcula nuestro generador especial: capturas, jaques y coronaciones.
Al terminar la búsqueda quiescente hemos conseguido obtener una valoración más realista porque hemos profundizado hasta una posición estable. Además hemos podido encontrar esta estabilidad en un tiempo razonable gracias a que hemos podido reducir drásticamente el factor de ramificación. Recordemos que antes definimos el factor de ramificación como el número medio de jugadas que un bando tiene a su disposición. Si descartamos todas las jugadas normales y nos quedamos sólo con las peligrosas en vez de 30-35 jugadas posibles de media tendremos muchas menos, a menudo sólo 1 ó 2. Esta búsqueda con un factor de ramificación tan bajo produce un árbol de variantes muy profundo y estrecho.La búsqueda quiescente no es una técnica perfecta, pero permite minimizar el efecto horizonte y es fundamental para que un programa pueda jugar bien al ajedrez.
| < Un buen algoritmo ... | [Cheoss] [índice] | Mejoras en la búsqueda > |
