Un buen algoritmo de búsqueda

< Alfabeta: el árbol podado [Cheoss]   [índice] El efecto horizonte >

Un buen algoritmo de búsqueda:

  • Debe mantener listas ordenadas de jugadas
  • Debe ser eficiente en la construcción del árbol
  • Debe minimizar el efecto horizonte


    • Importancia del orden en la búsqueda


    Se puede observar que con la lista ordenada es posible ahorrarse muchos más nodos que con el otro caso.

    La ordenación de la lista de jugadas es una de las características que debe cumplir una función de búsqueda eficiente, porque mejora enormemente la eficacia de la poda: permite al algoritmo de búsqueda descubrir antes cual es el verdadero límite en cada rama.


    MVV/LVA

    Un método sencillo de ordenación de jugadas pero de buenos resultados prácticos es el conocido por las siglas MVV/LVA (Most Valuable Victim/Least Valuable Atacker). La idea es que la mejor jugada posible será la que captura la pieza más valiosa del adversario. Imaginemos una posición en la que uno de los bandos puede capturar la dama enemiga. Es muy posible que ésta sea la mejor jugada disponible. Y si podemos tomar la dama enemiga con un peón mejor que hacerlo con una torre.

    Este algoritmo de ordenación se basa en este sencillo principio para asignar un valor a cada captura según el resultado de la comparación de los valores del atacante y el atacado.

    Los valores se ajustan para que la lista de jugadas quede ordenada de esta forma:

    1.- Capturas buenas (El atacante vale menos que el atacado, ej. PxD )
    2.- Capturas normales (Valores equivalentes de atacante y atacado, ej PxP) y jugadas que no capturan
    3.- Capturas malas (El atacante vale más que el atacado, ej. TxP)

    Esta forma de ordenar tiene limitaciones evidentes, pero es fácil de implementar, es rápido y permite una poda razonable del árbol de variantes.


    Jugadas legales y pseudo legales

    Un aspecto decisivo es la velocidad en el cálculo de jugadas y en la manipulación de las posiciones en el tablero. Si el programa no es capaz de hacer esto ágilmente nunca llegaremos muy lejos en nuestra búsqueda.

    Muchos factores intervienen en la rapidez a la hora de construir el árbol de variantes, no sólo la rapidez del generador de movimientos. Sobre esto hay un punto muy interesante donde se puede ganar o perder mucho tiempo. Se trata de la detección de jugadas ilegales.

    Cuando hablamos del problema de la legalidad de las jugadas en un motor de ajedrez nos referimos sobre todo a la detección de jaques. Comprobar si en una posición determinada el rey se encuentra en jaque es algo que lleva mucho tiempo de cálculo.

    Este proceso es tan costoso que frecuentemente los generadores de movimientos calculan todos los movimientos legales pero sin tener en cuenta los jaques. Posteriormente hay que filtrar esta lista de movimientos pseudo legales de alguna manera.

    Tenemos dos estrategias que se enfrentan de forma distinta al problema de la detección de jaques:

    1.- Tener un generador de movimientos que sólo incluya las jugadas que no dejen al rey del bando al que le toca mover en jaque.

    2.- Tener un generador de movimientos que incluya todas las jugadas posibles sin hacer ninguna comprobación de jaques. La lista se filtrará en la función de búsqueda, antes de realizar la jugada en el tablero se comprobará si el rey del bando que mueve está en jaque y se rechazarán las ilegales.

    La ventaja aparente del método 2 es que no habría que hacer el costoso test de jaques para toda la lista de jugadas, sólo para las que sobrevivieran a la poda alfa beta.


    < Alfabeta: el árbol podado [Cheoss]   [índice] El efecto horizonte >


    Miguel Ángel Embuena Molina                                  chessprogram.cheoss@gmail.com