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
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 MIN es un
límite inferior llamado alpha, igual al valor
más alto de todos los ancestros MAX de
. La
exploración de
termina en cuanto el valor actual VA es igual o
menor a alpha.
Límite-beta: el límite para un nodo MAX es un
límite superior llamado beta, igual al valor más
pequeño de todos los ancestros MIN de
. La
exploración de
termina en cuanto el valor actual VA es igual o
mayor a beta.
representa el mejor valor que hemos encontrado hasta ahora
para MAX y
el mejor valor (más bajo) para MIN.
Idea (ver tabla 3.4):
2 parámetros: y
: