En los programas de ajedrez por computadora , la heurística de movimiento nulo es una técnica heurística que se utiliza 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 del juego donde la posición actual es tan buena para que el lado se mueva que la mejor jugada del otro lado lo habría evitado. Dado que tales posiciones no podrían haber resultado del mejor juego, ellas y todas las ramas del árbol de juego que se derivan de ellas pueden ignorarse. Cuanto más rápido el programa produzca cortes, más rápida se ejecutará la búsqueda. La heurística de movimiento nulo está diseñada para adivinar los límites con menos esfuerzo del que se requeriría de otro modo, manteniendo al mismo tiempo un nivel razonable de precisión.
La heurística del movimiento nulo se basa en el hecho de que los movimientos de ajedrez más razonables mejoran la posición del bando que los realizó. Entonces, si el jugador a quien le toca moverse puede perder el derecho de mover (o hacer un movimiento nulo , una acción ilegal en el ajedrez ) y todavía tiene una posición lo suficientemente fuerte como para producir un corte, entonces la posición actual casi con certeza produciría un límite si el jugador actual realmente se movió.
Al emplear la heurística de movimiento nulo, el programa de computadora primero pierde el turno del lado cuyo turno le corresponde moverse, y luego realiza una búsqueda alfa-beta en la posición resultante a una profundidad menor que la que habría buscado en la posición actual. no utilizó la heurística de movimiento nulo. Si esta búsqueda superficial produce un límite, se supone que la búsqueda profunda en ausencia de un turno perdido también habría producido un límite. Como una búsqueda superficial es más rápida que una búsqueda más profunda, el límite se encuentra más rápido, lo que acelera el programa de ajedrez informático. Si la búsqueda superficial no logra producir un límite, entonces el programa debe realizar una búsqueda profunda.
Este enfoque parte de dos suposiciones. En primer lugar, se 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 superficial no sea demasiado superficial (en la implementación práctica, la búsqueda de movimiento nulo suele ser 2 o 3 capas más superficial de lo que habría sido la búsqueda completa), esto suele ser cierto. En segundo lugar, se supone que la búsqueda de movimientos nulos producirá un límite con suficiente frecuencia como para justificar el tiempo dedicado a realizar búsquedas de movimientos nulos 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 zugzwang (en alemán, "forzado a moverse"), el jugador al que le toca moverse sólo tiene como opciones legales malos movimientos, por lo que en realidad estaría mejor si se le permitiera perder el derecho a moverse. En estas posiciones, la heurística de movimiento nulo puede producir un límite en el que una búsqueda completa no habría encontrado uno, haciendo que el programa asuma que la posición es muy buena para un bando cuando en realidad 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. Tales restricciones a menudo incluyen no utilizar la heurística de movimiento nulo si
Otra heurística para abordar el problema del zugzwang es la poda de movimientos nulos verificada por Omid David y Nathan Netanyahu . [1] En la poda de movimiento nulo verificada, siempre que la búsqueda de movimiento nulo superficial indica un fallo alto, en lugar de cortar la búsqueda desde el nodo actual, la búsqueda continúa con una profundidad reducida.