| < El efecto horizonte | [Cheoss] [índice] | La Función de evaluación > |
Hasta ahora hemos visto 3 principios básicos para la búsqueda: eficiencia en la construcción del árbol, ordenación de la lista de jugadas y búsqueda quiescente.
Pues bien, con un algoritmo que cumpla estos principios y una función de evaluación mínima, que sólo valore el material, ya tenemos un programa de ajedrez que jugará sorprendentemente bien. Realmente llama la atención lo bien que puede jugar un programa sólo con lo que llevamos visto hasta ahora. Pero hay otras técnicas que podemos aplicar para refinar el proceso de búsqueda.
Primero realizamos una búsqueda hasta el nivel 1. Un vez terminada ésta hacemos una segunda que llegue hasta el nivel 2, y así sucesivamente, profundizando un nivel más en cada ciclo hasta que se agota el tiempo disponible para esa jugada.
Resulta paradójico: hacemos todo lo posible por reducir la búsqueda (poda alfa beta, etc) y ahora decidimos que es mejor hacer no una sino varias búsquedas por cada turno de juego. Hay varias razones que explican que hacer esto es una buena idea:
1. Por la propia naturaleza del minimax sucede que cada nivel adicional que profundizamos cuesta tanto o más tiempo de cálculo que la suma de todos los niveles anteriores.
2. Con esta técnica nos aseguramos de que siempre habrá una jugada disponible cualquiera que sea el tiempo que tenemos para realizar la jugada, ya que la búsqueda hasta los primeros niveles es casi instantánea.
3. Lo más importante es que en cada búsqueda que hacemos obtenemos información muy valiosa que utilizaremos en la siguiente búsqueda. Esta realimentación es la base de varias mejoras en el algoritmo de búsqueda. Es decir, para mejorar y hacer más rápida la función de búsqueda primero tenemos que introducir la búsqueda iterativa como paso previo. Es la base para todas las mejoras posteriores.
De esta forma cuando la búsqueda acaba tenemos no sólo la mejor jugada, también toda la línea prevista por el programa como posibles respuestas de uno y otro bando hasta la profundidad hasta donde haya llegado. Llamamos a esta variante “línea principal”.
La línea principal se utiliza para ordenar la lista de jugadas. Tenemos anotada la mejor jugada que el programa calculó para ese nivel, por tanto aprovechamos esta información para ponerla la primera en la lista.
Esto supone una mejora muy importante porque como ya hemos visto el algoritmo alfabeta es extraordinariamente sensible a la ordenación de la lista de jugadas. Teniendo en cuenta la línea principal el orden de evaluación de jugadas en el alfabeta queda así: en primer lugar la jugada recomendada por la línea principal, en segundo lugar las capturas buenas, a continuación capturas neutras y jugadas que no capturan y por último las capturas malas.
De esta forma si se vuelve a presentar esta posición, el programa no debe calcular de nuevo todas las variantes, utiliza la valoración obtenida anteriormente ahorrándose mucho tiempo de cálculo. El uso de estas tablas también es útil para la detección de jaques por repetición.
| < El efecto horizonte | [Cheoss] [índice] | La Función de evaluación > |
