En la teoría de juegos , un movimiento nulo o un pase es una decisión de un jugador de no hacer un movimiento cuando es el turno de ese jugador para moverse. Aunque los movimientos nulos van en contra de las reglas de muchos juegos, a menudo es útil considerarlos al analizar estos juegos. Ejemplos de esto incluyen el análisis de zugzwang (una situación en el ajedrez u otras partidas en las que una jugada nula, si estuviera permitida, sería mejor que cualquier otra jugada), [1] y la heurística de jugadas nulas en el análisis del árbol de juego ( un método para podar árboles de caza que implica hacer un movimiento nulo y luego buscar a una profundidad menor). [2]
La razón por la que un movimiento nulo de profundidad reducida es efectivo en la reducción de búsqueda alfa-beta del árbol del juego es que las amenazas tácticas tienden a aparecer muy rápidamente, en solo uno o dos movimientos. Si el oponente no tiene amenazas tácticas reveladas por la búsqueda de movimiento nulo, la posición puede ser lo suficientemente buena como para exceder el mejor resultado obtenible en otra rama del árbol (es decir, "beta"), por lo que no es necesario realizar más búsquedas desde el nodo actual. , y el resultado del movimiento nulo se puede devolver como valor de búsqueda. Incluso si el valor de búsqueda de movimiento nulo no excede beta, el valor devuelto puede establecer un piso más alto en la valoración de la posición que el alfa actual, por lo que se producirán más cortes en los nodos hermanos descendientes de la posición.
La suposición subyacente es que al menos algún movimiento legal disponible para el jugador en movimiento en el nodo es mejor que ningún movimiento. En el caso de que el jugador en movimiento esté en zugswang, esa suposición es falsa y el resultado del movimiento nulo no es válido (en ese caso, en realidad establece un límite al valor de la posición). Por lo tanto, es necesario tener lógica para excluir movimientos nulos en los nodos del árbol donde es posible zugswang. En el ajedrez, las posiciones de zugawang pueden ocurrir en finales de rey y peón y, a veces, en juegos finales que también incluyen otras piezas.
Referencias
- ^ Beal, Don F. (1990), "Un algoritmo de búsqueda de quiescencia generalizada", Inteligencia artificial , 43 (1): 85-98, doi : 10.1016 / 0004-3702 (90) 90072-8.
- ^ 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.