3.3.2 Análisis

$\alpha-\beta$ poda el árbol al darse cuenta que los nodos podados (independientemente de sus valores) no pueden influenciar en el valor del nodo raíz.

Si definimos $F_J(x)$ como una función de influencia del nodo raíz con respecto a un nodo $J$, la influencia debe de transmitirse a través del camino que los conecta.

La función de influencia se puede calcular como varias funciones de influencia consecutivas.

Lo importante es que las funciones son cerradas bajo composición por lo que se pueden escribir en términos de dos funciones nuevas:

$A(J) = max[\alpha(K), \alpha(M), \ldots]$ y $B(J) = min[\beta(L), \beta(N), \ldots]$

Estas funciones las podemos usar para evaluar los nodos explorados por $\alpha-\beta$:

Para cualquier nodo $J$, forma el camino desde la raíz hasta $J$ y define la siguientes cantidades:

• A(J) = el valor minimax más alto entre todos los descendientes izquierdos de los ancestros MAX de J.
• B(J) = el valor minimax más pequeño de todos los descendientes izquierdos de los ancestros de J.

$J$ es generado por $\alpha-\beta$ sii: $A(J) < B(J)$