Heurística de movimiento nulo

En los programas de ajedrez de computadora , la heurística de movimiento nulo es una técnica heurística utilizada para mejorar la velocidad del algoritmo de poda alfa-beta .

La poda alfa-beta acelera el algoritmo minimax al identificar puntos de corte , puntos en el árbol de juego donde la posición actual es tan buena para que el bando se mueva que la mejor jugada del otro bando la hubiera evitado. Dado que dichas posiciones no podrían haber resultado de la mejor jugada, ellas y todas las ramas del árbol de juego derivadas de ellas pueden ignorarse. Cuanto más rápido el programa produce puntos de corte, más rápido se ejecuta la búsqueda. La heurística de movimiento nulo está diseñada para adivinar puntos de corte con menos esfuerzo del que se requeriría de otra manera, mientras se mantiene un nivel razonable de precisión.

La heurística del movimiento nulo se basa en el hecho de que la mayoría de los movimientos de ajedrez razonables mejoran la posición del bando que los realizó. Por lo tanto, si el jugador al que le toca mover puede renunciar al derecho a mover (o hacer un movimiento nulo , una acción ilegal en ajedrez ) y aún así tener una posición lo suficientemente fuerte como para producir un corte, entonces la posición actual produciría casi con certeza un corte si el jugador actual realmente moviera.

Al emplear la heurística de movimiento nulo, el programa de computadora primero pierde el turno del bando al que le toca mover y luego realiza una búsqueda alfa-beta en la posición resultante a una profundidad menor que la que hubiera buscado en la posición actual si no hubiera usado la heurística de movimiento nulo. Si esta búsqueda superficial produce un punto de corte, supone que la búsqueda a profundidad completa en ausencia de un turno perdido también habría producido un punto de corte. Debido a que una búsqueda superficial es más rápida que una búsqueda a profundidad completa, el punto de corte se encuentra más rápido, acelerando el programa de ajedrez de computadora. Si la búsqueda superficial no produce un punto de corte, entonces el programa debe realizar la búsqueda a profundidad completa.

Este enfoque parte de dos supuestos. En primer lugar, supone que la desventaja de perder el turno es mayor que la desventaja de realizar una búsqueda más superficial. Siempre que la búsqueda más superficial no sea demasiado superficial (en la práctica, la búsqueda de movimiento nulo suele ser 2 o 3 veces más superficial de lo que hubiera sido la búsqueda completa), esto suele ser cierto. En segundo lugar, supone que la búsqueda de movimiento nulo producirá un corte con la frecuencia suficiente para justificar el tiempo empleado en realizar búsquedas de movimiento nulo en lugar de búsquedas completas. En la práctica, esto también suele ser cierto.

Hay una clase de posiciones de ajedrez en las que emplear la heurística de movimiento nulo puede dar lugar a graves errores tácticos. En estas posiciones de zugzwang (que en alemán significa "obligado a mover"), el jugador al que le toca mover solo tiene como opciones legales movimientos malos, por lo que en realidad estaría en mejor situación si se le permitiera perder el derecho a mover. En estas posiciones, la heurística de movimiento nulo puede producir un punto de corte en el que una búsqueda completa no habría encontrado ninguno, lo que hace que el programa suponga que la posición es muy buena para un bando cuando, de hecho, puede ser muy mala para él.

Para evitar el uso de la heurística de movimiento nulo en posiciones de zugzwang, la mayoría de los programas de ajedrez que utilizan la heurística de movimiento nulo imponen restricciones a su uso. Dichas restricciones a menudo incluyen no utilizar la heurística de movimiento nulo si

• El lado a mover está en jaque
• El bando a mover solo tiene su rey y sus peones restantes
• El lado a mover tiene una pequeña cantidad de piezas restantes
• El movimiento anterior en la búsqueda también fue un movimiento nulo.

Otra heurística para tratar el problema de zugzwang es la poda de movimiento nulo verificada de Omid David y Nathan Netanyahu . ^[1] En la poda de movimiento nulo verificada, siempre que la búsqueda de movimiento nulo superficial indica un error alto, en lugar de cortar la búsqueda desde el nodo actual, la búsqueda continúa con una profundidad reducida.

• Goetsch, G.; Campbell, MS (1990). "Experimentos con la heurística de movimiento nulo". En Marsland, T. Anthony; Schaeffer, Jonathan (eds.). Computadoras, ajedrez y cognición . Springer-Verlag. págs. 159–168. ISBN 3-540-97415-6.