Poda alfa-beta

La poda alfa-beta acelera la búsqueda de un motor de ajedrez, un programa que compara jugadas y respuestas. La búsqueda puede imaginarse como un árbol: cada nodo es una posición y cada rama es una jugada legal. Sin poda, el programa tendría que recorrer muchas continuaciones que terminarán siendo irrelevantes.

El método mantiene dos límites mientras analiza. Alfa representa el mejor resultado que un bando ya puede garantizar en la línea considerada. Beta representa un límite impuesto por una alternativa que el rival ya tiene disponible. Cuando una continuación resulta tan mala que el jugador racional nunca la elegiría, seguir profundizando en ella no puede cambiar la decisión del nodo superior.

La rama se abandona por una demostración lógica dentro del árbol, no porque una jugada parezca fea a simple vista. Con la misma profundidad y las mismas evaluaciones en el límite, alfa-beta produce la misma elección que una búsqueda completa que supone que ambos bandos responden de la mejor manera.

El ahorro depende mucho del orden de análisis. Si las jugadas fuertes se prueban primero, los límites se vuelven útiles antes y más ramas pueden detenerse sin seguir profundizando. Una función de evaluación, que asigna una estimación numérica a una posición, aporta los valores en los puntos donde termina la búsqueda.