Predpogoji: Minimax algoritem v teoriji iger , Funkcija vrednotenja v teoriji iger
Obrezovanje alfa-beta pravzaprav ni nov algoritem, temveč tehnika optimizacije za algoritem minimax. Zmanjša čas izračuna za velik faktor. To nam omogoča veliko hitrejše iskanje in gremo celo na globlje ravni v drevesu igre. V drevesu igre odreže veje, ki jih ni treba iskati, ker že obstaja boljša poteza. Imenuje se obrezovanje alfa-beta, ker posreduje 2 dodatna parametra v funkciji minimax, in sicer alfa in beta.

Določimo parametra alfa in beta.

Alfa je najboljša vrednost, ki jo maksimizator trenutno lahko jamči na tej ali višji ravni.
Beta je najboljša vrednost, ki jo minimizator trenutno lahko jamči na tej ali nižji ravni.

Psevdokoda:

 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)>

Pojasnimo zgornji algoritem s primerom.

• Začetni klic se začne od A . Vrednost alfe tukaj je -NESKONČNOST in vrednost beta je +NESKONČNO . Te vrednosti se prenesejo na naslednja vozlišča v drevesu. pri A maksimizator mora izbrati največ B in C , torej A klice B prvi
• pri B minimizator mora izbrati min D in IN in s tem klice D prvi.
• pri D , gleda svojega levega otroka, ki je listno vozlišče. To vozlišče vrne vrednost 3. Zdaj je vrednost alfa pri D je max(-INF, 3), kar je 3.
• Za odločitev, ali je vredno pogledati desno vozlišče ali ne, preveri pogoj beta<=alpha. To je napačno, ker je beta = +INF in alfa = 3. Zato nadaljuje iskanje.
D zdaj pogleda svojega desnega otroka, ki vrne vrednost 5.At D , alfa = max(3, 5), kar je 5. Zdaj vrednost vozlišča D je 5 D vrne vrednost 5 do B . pri B , beta = min( +INF, 5), kar je 5. Minimizatorju je zdaj zagotovljena vrednost 5 ali manj. B zdaj kliče IN da vidim, ali lahko dobi nižjo vrednost od 5.
• pri IN vrednosti alfa in beta nista -INF in +INF, temveč -INF oziroma 5, ker je bila vrednost beta spremenjena pri B in to je tisto B preneseno na IN
• zdaj IN gleda svojega levega otroka, ki je 6. At IN , alfa = max(-INF, 6), kar je 6. Tu pogoj postane resničen. beta je 5 in alfa je 6. Torej je beta<=alfa res. Zato se zlomi in IN vrne 6 na B
• Upoštevajte, kako ni bilo pomembno, kakšna je vrednost IN ima otrok prav. Lahko bi bil +INF ali -INF, še vedno ne bi bilo pomembno. Nikoli nam ga ni bilo treba niti pogledati, ker je minimalizator imel zagotovljeno vrednost 5 ali manj. Takoj ko je maksimizator videl 6, je vedel, da minimizator ne bo nikoli prišel sem, ker lahko dobi 5 na levi strani B . Na ta način nam ni bilo treba gledati teh 9 in smo tako prihranili čas računanja.
E vrne vrednost od 6 do B . pri B , beta = min( 5, 6), kar je 5. Vrednost vozlišča B je tudi 5

Zaenkrat je naše drevo iger videti tako. 9 je prečrtano, ker ni bilo nikoli izračunano.

B vrne 5 do A . pri A , alpha = max( -INF, 5), kar je 5. Zdaj ima maksimizator zagotovljeno vrednost 5 ali več. A zdaj kliče C da vidim, ali lahko dobi višjo vrednost od 5.
• pri C , alfa = 5 in beta = +INF. C klice F
• pri F , alfa = 5 in beta = +INF. F pogleda svojega levega otroka, ki je 1. alfa = max( 5, 1), ki je še vedno 5.
F pogleda svojega desnega otroka, ki je 2. Zato je najboljša vrednost tega vozlišča 2. Alfa še vedno ostaja 5 F vrne vrednost 2 v C . pri C , beta = min( +INF, 2). Pogoj beta <= alfa postane resničen, ko je beta = 2 in alfa = 5. Torej se zlomi in mu sploh ni treba izračunati celotnega poddrevesa G .
• Intuicija za tem prelomom je, da pri C minimizatorju je bila zagotovljena vrednost 2 ali manj. Toda maksimizatorju je bila že zagotovljena vrednost 5, če se je odločil B . Zakaj bi se torej maksimizator sploh odločil C in dobite vrednost manjšo od 2? Spet lahko vidite, da ni bilo pomembno, kaj sta bili ti zadnji 2 vrednosti. Prav tako smo prihranili veliko računanja s preskokom celotnega poddrevesa.
C zdaj vrne vrednost 2 do A . Zato je najboljša vrednost pri A je max( 5, 2), kar je 5.
• Zato je optimalna vrednost, ki jo lahko dobi maksimizator, 5

Takole izgleda naše končno drevo igre. Kot vidite G je prečrtano, ker ni bilo nikoli izračunano.

CPP

>

>

Java

>

>

Python3

>

>

C#

pretvori celo število v niz java

>

>

Javascript

>

>

The optimal value is : 5>