Prerequisiti: Algoritmo Minimax nella teoria dei giochi , Funzione di valutazione nella teoria dei giochi
La potatura Alpha-Beta non è in realtà un nuovo algoritmo, ma piuttosto una tecnica di ottimizzazione per l'algoritmo minimax. Riduce il tempo di calcolo di un fattore enorme. Ciò ci consente di effettuare ricerche molto più velocemente e persino di accedere a livelli più profondi nell'albero di gioco. Taglia i rami nell'albero del gioco che non necessitano di essere cercati perché esiste già una mossa migliore disponibile. Si chiama potatura Alpha-Beta perché passa 2 parametri aggiuntivi nella funzione minimax, vale a dire alfa e beta.

Definiamo i parametri alfa e beta.

Alfa è il miglior valore che il massimizzatore attualmente può garantire a quel livello o superiore.
Beta è il miglior valore che il minimizzatore attualmente può garantire a quel livello o al di sotto.

logo java

Pseudocodice:

 function minimax(node, depth, isMaximizingPlayer, alpha, beta): if node is a leaf node : return value of the node if isMaximizingPlayer : bestVal = -INFINITY for each child node : value = minimax(node, depth+1, false, alpha, beta) bestVal = max( bestVal, value) alpha = max( alpha, bestVal) if beta <= alpha: break return bestVal else : bestVal = +INFINITY for each child node : value = minimax(node, depth+1, true, alpha, beta) bestVal = min( bestVal, value) beta = min( beta, bestVal) if beta <= alpha: break return bestVal>

 // Calling the function for the first time. minimax(0, 0, true, -INFINITY, +INFINITY)>

Chiariamo l'algoritmo di cui sopra con un esempio.

• La chiamata iniziale inizia da UN . Il valore di alfa qui è -INFINITO e il valore di beta è +INFINITO . Questi valori vengono passati ai nodi successivi nell'albero. A UN il massimizzatore deve scegliere il massimo di B E C , COSÌ UN chiamate B Primo
• A B il minimizzatore deve scegliere min of D E E e quindi chiama D Primo.
• A D , guarda il suo figlio sinistro che è un nodo foglia. Questo nodo restituisce un valore di 3. Ora il valore di alpha at D è max( -INF, 3) che è 3.
• Per decidere se vale la pena guardare o meno il suo nodo destro, controlla la condizione beta<=alpha. Questo è falso poiché beta = +INF e alpha = 3. Quindi continua la ricerca.
D ora guarda il suo figlio destro che restituisce un valore di 5.At D , alpha = max(3, 5) che è 5. Ora il valore di node D è 5 D restituisce un valore da 5 a B . A B , beta = min( +INF, 5) che è 5. Al minimizzatore è ora garantito un valore pari o inferiore a 5. B ora chiama E per vedere se riesce a ottenere un valore inferiore a 5.
• A E i valori di alfa e beta non sono -INF e +INF ma invece -INF e 5 rispettivamente, perché il valore di beta è stato modificato in B e questo è ciò che B tramandato a E
• Ora E guarda il suo figlio sinistro che ha 6 anni E , alpha = max(-INF, 6) che è 6. Qui la condizione diventa vera. beta è 5 e alfa è 6. Quindi beta<=alpha è vero. Quindi si rompe e E restituisce 6 a B
• Nota come non importa quale sia il valore di E il figlio giusto lo è. Avrebbe potuto essere +INF o -INF, comunque non avrebbe avuto importanza, non abbiamo nemmeno dovuto guardarlo perché al minimizzatore era garantito un valore pari a 5 o inferiore. Quindi non appena il massimizzatore ha visto il 6 sapeva che il minimizzatore non sarebbe mai arrivato da questa parte perché può ottenere un 5 sul lato sinistro di B . In questo modo non abbiamo dovuto guardare quel 9 e quindi abbiamo risparmiato tempo di calcolo.
E restituisce un valore da 6 a B . A B , beta = min( 5, 6) che è 5.Il valore di node B è anche 5

Finora ecco come appare il nostro albero di gioco. Il 9 è cancellato perché non è mai stato calcolato.

B restituisce 5 a UN . A UN , alpha = max( -INF, 5) che è 5. Ora al massimizzatore è garantito un valore pari o superiore a 5. UN ora chiama C per vedere se può ottenere un valore superiore a 5.
• A C , alfa = 5 e beta = +INF. C chiamate F
• A F , alfa = 5 e beta = +INF. F guarda il figlio sinistro che è 1. alpha = max( 5, 1) che è ancora 5.
F guarda il suo figlio destro che è un 2. Quindi il miglior valore di questo nodo è 2. Alpha rimane comunque 5 F restituisce un valore di 2 a C . A C , beta = min( +INF, 2). La condizione beta <= alpha diventa vera poiché beta = 2 e alpha = 5. Quindi non funziona e non deve nemmeno calcolare l'intero sottoalbero di G .
• L'intuizione alla base di questa rottura è che, a C al minimo è stato garantito un valore pari o inferiore a 2. Ma al massimizzatore era già garantito un valore di 5 se lo avesse scelto B . Allora perché mai il massimizzatore dovrebbe scegliere? C e ottenere un valore inferiore a 2? Ancora una volta puoi vedere che non importa quali fossero gli ultimi 2 valori. Abbiamo anche risparmiato molti calcoli saltando un intero sottoalbero.
C ora restituisce un valore da 2 a UN . Pertanto il miglior rapporto qualità-prezzo UN è max( 5, 2) che è 5.
• Quindi il valore ottimale che il massimizzatore può ottenere è 5

Ecco come appare il nostro albero di gioco finale. Come potete vedere G è stato cancellato perché non è mai stato calcolato.

CPP

>

>

Giava

>

interfaccia comparabile in Java

>

Python3

>

>

C#

>

>

Javascript

preg_match

>

>

The optimal value is : 5>