3.3 Alpha-Beta

A McCarthy (56) se le considera el responsable de ver la utilidad de alpha-beta.

Parecido a dynamic-programming en el sentido de que elimina caminos que no van a producir mejores resultados.

Es el más usado en juegos.

Es como un minimax haciendo backtracking, pero $\ldots$

si al actualizar el valor minimax de un nodo, éste cruza cierto límite, entonces no hace falta hacer más exploración abajo de ese nodo; su valor (VA) se puede transmitir a su padre como si todos sus hijos hubieran sido evaluados.

Los límites o cortes son ajustados dinámicamente.

Límite-alpha: el límite para un nodo $J$ MIN es un límite inferior llamado alpha, igual al valor más alto de todos los ancestros MAX de $J$. La exploración de $J$ termina en cuanto el valor actual VA es igual o menor a alpha.

Límite-beta: el límite para un nodo $J$ MAX es un límite superior llamado beta, igual al valor más pequeño de todos los ancestros MIN de $J$. La exploración de $J$ termina en cuanto el valor actual VA es igual o mayor a beta.

$\alpha$ representa el mejor valor que hemos encontrado hasta ahora para MAX y $\beta$ el mejor valor (más bajo) para MIN.

Idea (ver tabla 3.4): 2 parámetros: $\alpha$ y $\beta$:

• Regresa el valor $V(J)$ si está entre $\alpha$ y $\beta$.
• Regresa $\alpha$ si $V(J) \leq \alpha$.
• Regresa $\beta$ si $V(J) \geq \beta$.