Algoritmo Alfa-Beta

La poda alfa-beta es una técnica que optimiza el algoritmo Minimax de búsqueda en árboles de juego: reduce el número de posiciones que hay que evaluar sin cambiar la jugada que Minimax elegiría. Se aplica a juegos adversariales de dos jugadores, suma cero e información perfecta, como el ajedrez o las damas.

La idea tomó forma en la década de 1950: John McCarthy recordó haber propuesto la heurística alfa-beta, pero también reconoció que Arthur Samuel y el equipo de Newell y Simon usaron versiones independientes y que no pudo establecerse una autoría única. Una discusión pública temprana apareció en 1958, en el trabajo de Allen Newell, J. C. Shaw y Herbert Simon sobre programas de ajedrez y complejidad.

Cómo funciona

El algoritmo mantiene dos valores mientras recorre el árbol: alfa, la mejor puntuación ya garantizada para el jugador que maximiza, y beta, la mejor para el que minimiza. Cuando en un nodo se descubre que ya no puede mejorar la decisión asegurada —es decir, cuando beta es menor o igual que alfa—, se «poda» esa rama y se deja de explorar, porque ninguno de sus descendientes podrá alterar la elección final. En una frase: se abandona una jugada en cuanto se demuestra que es peor que otra ya examinada.

Cuánto ahorra

La poda no cambia el resultado, solo el coste, y este depende del orden en que se examinen las jugadas. Con una ordenación óptima, el factor de ramificación efectivo se reduce a su raíz cuadrada, lo que permite buscar aproximadamente al doble de profundidad con el mismo cómputo. Con un orden aleatorio la mejora es real pero menor, y por eso los motores invierten en ordenar bien las jugadas.