Potatura alfa-beta con ordinamento
La potatura alfa-beta con ordinamento è una tecnica utilizzata per ridurre la complessità dell'algoritmo minimax L'efficacia della potatura alfa-beta è tanto maggiore quanto prima sono trovate le mosse ( nodi ) migliori. Ad esempio, nel seguente esempio le mosse migliori di MINI sono situate all'ultimo posto. Quando la potatura alfa-beta entra in azione ( cerchio rosso ) l'esplorazione dell'albero è comunque completa.
Viceversa, quando le mosse migliori sono ordinate in ordine decrescente per MAX e in ordine crescente per MINI, la potatura alfa-beta dell'albero è più frequente. Nel seguente albero i nodi sono ordinati seguendo questa logica.
L'ordinamento dei nodi successori a partire dalla mossa corrente ha pro e contro. Da un lato, l'ordinamento appesantisce la complessità dell'algoritmo in quanto implica l'elaborazione di un apposita subroutine di sort a partire dal nodo corrente. Dall'altro, l'ordinamento consente di far scattare più rapidamente la potatura alfa-beta. L'efficienza della tecnica dipende dal consumo complessivo di risorse necessario per l'esecuzione dell'algoritmo di sort e dal risparmio di risorse ottenibile dalla potatura alfa.beta.
