Forudsætninger: Minimax-algoritme i spilteori , Evalueringsfunktion i spilteori
Alpha-Beta beskæring er faktisk ikke en ny algoritme, men derimod en optimeringsteknik for minimax-algoritmen. Det reducerer beregningstiden med en enorm faktor. Dette giver os mulighed for at søge meget hurtigere og endda gå ind på dybere niveauer i spiltræet. Den skærer grene af i spiltræet, som ikke skal søges i, fordi der allerede findes et bedre træk. Det kaldes Alpha-Beta-beskæring, fordi det passerer 2 ekstra parametre i minimax-funktionen, nemlig alfa og beta.

Lad os definere parametrene alfa og beta.

Alfa er den bedste værdi, som maksimerer i øjeblikket kan garantere på det niveau eller derover.
Beta er den bedste værdi, som minimer i øjeblikket kan garantere på det niveau eller derunder.

Pseudokode:

 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) 

Lad os gøre ovenstående algoritme klar med et eksempel.

• Det indledende opkald starter kl EN . Værdien af ​​alfa her er -UENDELIGHED og værdien af ​​beta er +INFINITY . Disse værdier overføres til efterfølgende noder i træet. På EN maximizeren skal vælge max af B og C , så EN opkald B først
• På B det skal minimizeren vælge min af D og OG og derfor opkald D først.
• På D , den ser på sit venstre barn, som er en bladknude. Denne node returnerer en værdi på 3. Nu værdien af ​​alfa ved D er max( -INF, 3), hvilket er 3.
• For at afgøre, om det er værd at se på dens højre knude eller ej, tjekker den betingelsen beta <=alpha. Dette er falsk, da beta = +INF og alfa = 3. Så den fortsætter søgningen.
D ser nu på dets højre underordnede, som returnerer en værdi på 5.At D , alpha = max(3, 5) som er 5. Nu værdien af ​​node D er 5 D returnerer en værdi på 5 til B . På B , beta = min( +INF, 5) som er 5. Minimeren er nu garanteret en værdi på 5 eller mindre. B ringer nu OG for at se, om han kan få en lavere værdi end 5.
• På OG værdierne af alfa og beta er ikke -INF og +INF, men i stedet for henholdsvis -INF og 5, fordi værdien af ​​beta blev ændret kl. B og det er hvad B gået i arv til OG
• Nu OG ser på sit venstre barn som er 6. Kl OG , alpha = max(-INF, 6) som er 6. Her bliver betingelsen sand. beta er 5 og alfa er 6. Så beta <=alfa er sandt. Derfor går den i stykker og OG returnerer 6 til B
• Bemærk, hvordan det var ligegyldigt, hvad værdien af OG ’s rette barn er. Det kunne have været +INF eller -INF, det ville stadig være ligegyldigt. Vi behøvede aldrig engang at se på det, fordi minimizeren var garanteret en værdi på 5 eller mindre. Så så snart maximizeren så 6'eren vidste han, at minimizeren aldrig ville komme på denne måde, fordi han kan få en 5'er i venstre side af B . På denne måde behøvede vi ikke at se på den 9 og sparede derfor beregningstid.
E returnerer en værdi på 6 til B . På B , beta = min( 5, 6) som er 5. Værdien af ​​node B er også 5

Indtil videre er det sådan vores spiltræ ser ud. 9 er streget over, fordi det aldrig er blevet beregnet.

B returnerer 5 til EN . På EN , alpha = max( -INF, 5) som er 5. Nu er maksimeringsværktøjet garanteret en værdi på 5 eller større. EN ringer nu C for at se, om den kan få en højere værdi end 5.
• På C , alfa = 5 og beta = +INF. C opkald F
• På F , alfa = 5 og beta = +INF. F ser på dets venstre barn, som er en 1. alpha = max( 5, 1), som stadig er 5.
F ser på dets højre underordnede, som er en 2. Derfor er den bedste værdi af denne node 2. Alfa forbliver stadig 5 F returnerer en værdi på 2 til C . På C , beta = min( +INF, 2). Betingelsen beta <= alpha bliver sand, da beta = 2 og alfa = 5. Så den går i stykker, og den behøver ikke engang at beregne hele undertræet af G .
• Intuitionen bag dette break-off er, at kl C minimeren var garanteret en værdi på 2 eller mindre. Men maksimeren var allerede garanteret en værdi på 5, hvis han valgte B . Så hvorfor skulle maksimeren nogensinde vælge C og få en værdi mindre end 2 ? Igen kan du se, at det var lige meget, hvad de sidste 2 værdier var. Vi sparede også en masse beregninger ved at springe et helt undertræ over.
C returnerer nu en værdi på 2 til EN . Derfor den bedste værdi til EN er max( 5, 2), hvilket er en 5.
• Derfor er den optimale værdi, som maksimeringen kan få, 5

Sådan ser vores sidste spiltræ ud. Som du kan se G er streget over, da det aldrig er blevet beregnet.

CPP

Java

Python3

C#

Javascript

The optimal value is : 5