En los programas informáticos de ajedrez , la heurística de movimiento nulo es una técnica heurística utilizada para mejorar la velocidad del algoritmo de poda alfa-beta .
Razón fundamental
La poda alfa-beta acelera el algoritmo minimax al identificar los puntos de corte , puntos en el árbol del juego donde la posición actual es tan buena para que el lado se mueva y la mejor jugada del otro lado lo habría evitado. Dado que tales posiciones no podrían haber resultado de un mejor juego, se pueden ignorar ellas y todas las ramas del árbol de juego que se derivan de ellas. Cuanto más rápido produzca el programa cortes, más rápido se ejecutará la búsqueda. La heurística de movimiento nulo está diseñada para adivinar los puntos de corte con menos esfuerzo del que se requeriría de otro modo, al tiempo que conserva un nivel razonable de precisión.
La heurística de 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 jugó. Entonces, si el jugador al que le toca mover puede perder el derecho a mover (o hacer un movimiento nulo - una acción ilegal en el ajedrez ) y aún tener una posición lo suficientemente fuerte como para producir un corte, entonces la posición actual produciría casi con certeza un límite si el jugador actual realmente se movió.
Implementación
Al emplear la heurística de movimiento nulo, el programa de computadora primero pierde el turno del lado al que le toca moverse, y luego realiza una búsqueda alfa-beta en la posición resultante a una profundidad menor de 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 de profundidad completa en ausencia de un giro perdido también habría producido un límite. Debido a que 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 de la computadora. Si la búsqueda superficial no produce un corte, entonces el programa debe realizar la búsqueda completa.
Este enfoque hace dos suposiciones. Primero, asume que la desventaja de perder el turno es mayor que la desventaja de realizar una búsqueda menos profunda. Siempre que la búsqueda menos profunda no sea mucho más superficial (en la implementación práctica, la búsqueda de movimiento nulo suele ser 2 o 3 capas menos profunda de lo que habría sido la búsqueda completa), esto suele ser cierto. En segundo lugar, asume que la búsqueda de movimiento nulo producirá un límite con la frecuencia suficiente para justificar el tiempo dedicado a realizar búsquedas de movimiento nulo en lugar de búsquedas completas. En la práctica, esto también suele ser cierto.
Problemas con la heurística de movimiento nulo
Hay una clase de posiciones de ajedrez donde emplear la heurística de movimiento nulo puede resultar en graves errores tácticos. En estas posiciones de zugzwang (alemán para "obligado a moverse"), el jugador al que le toca mover sólo tiene malas jugadas como sus opciones legales, 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 corte donde una búsqueda completa no hubiera encontrado uno, haciendo que el programa asuma que la posición es muy buena para un bando cuando de hecho puede ser muy mala para ellos.
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 usar la heurística de movimiento nulo si
- el lado para moverse está bajo control
- el lado que se mueve solo tiene su rey y 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.
Poda de movimiento nulo verificada
Otro heurístico para tratar el problema Zugzwang es Omid David y Nathan Netanyahu 's verificada nulo movimiento de poda . [1] En la poda de movimiento nulo verificada, siempre que la búsqueda de movimiento nulo superficial indica una falla alta, en lugar de cortar la búsqueda del nodo actual, la búsqueda continúa con profundidad reducida.
Referencias
- ↑ David-Tabibi, Omid; Netanyahu, Nathan S. (septiembre de 2002). "Poda de movimiento nulo verificado". Revista ICGA . 25 (3): 153-161. arXiv : 0808.1125 . Código bibliográfico : 2008arXiv0808.1125D . doi : 10.3233 / ICG-2002-25305 . S2CID 1041 .
- 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.