Edellytykset: Minimax-algoritmi peliteoriassa , Arviointifunktio peliteoriassa
Alfa-Beta-leikkaus ei itse asiassa ole uusi algoritmi, vaan pikemminkin minimax-algoritmin optimointitekniikka. Se vähentää laskenta-aikaa valtavasti. Tämä antaa meille mahdollisuuden etsiä paljon nopeammin ja jopa mennä syvemmille tasoille pelipuussa. Se katkaisee pelipuusta oksia, joita ei tarvitse etsiä, koska tarjolla on jo parempi siirto. Sitä kutsutaan Alpha-Beta-leikkaukseksi, koska se välittää 2 ylimääräistä parametria minimax-funktiossa, nimittäin alfa- ja beetaversion.
Määritetään parametrit alfa ja beta.
Alpha on paras arvo maksimoija tällä hetkellä voi taata tällä tai korkeammalla tasolla.
Beeta on paras arvo minimointi tällä hetkellä voi taata tällä tai sen alapuolella.
Pseudokoodi:
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)>
Tehdään yllä olevasta algoritmista selväksi esimerkin avulla.
- Ensimmäinen puhelu alkaa A . Alfan arvo tässä on - ÄPÄÄTÖS ja betan arvo on + INFINITY . Nämä arvot välitetään puun seuraaville solmuille. klo A maksimoijan on valittava max B ja C , niin A puhelut B ensimmäinen
- klo B se minimoijan on valittava min D ja JA ja siksi puhelut D ensimmäinen.
- klo D , se katsoo vasenta lastaan, joka on lehtisolmu. Tämä solmu palauttaa arvon 3. Nyt arvo alfa at D on max(-INF, 3), joka on 3.
- Päättääkseen, kannattaako katsoa oikeaa solmua vai ei, se tarkistaa ehdon beta<=alpha. Tämä on väärin, koska beta = +INF ja alfa = 3. Joten se jatkaa hakua. D tarkastelee nyt oikeaa lastaan, joka palauttaa arvon 5.At D , alfa = max(3, 5), joka on 5. Nyt solmun arvo D on 5 D palauttaa arvon 5 to B . klo B , beeta = min( +INF, 5), joka on 5. Minimoijalle on nyt taattu arvo 5 tai pienempi. B nyt soittaa JA nähdäkseen, voiko hän saada pienemmän arvon kuin 5.
- klo JA alfan ja betan arvot eivät ole -INF ja +INF, vaan sen sijaan -INF ja 5, koska beetan arvoa muutettiin B ja se on mitä B siirtyi alas JA
- Nyt JA katsoo vasenta lastaan, joka on 6. At JA , alfa = max(-INF, 6), joka on 6. Tässä ehdosta tulee tosi. beeta on 5 ja alfa on 6. Joten beta<=alfa on totta. Siksi se katkeaa ja JA palauttaa 6 - B
- Huomaa, kuinka arvolla ei ollut väliä JA oikea lapsi on. Se olisi voinut olla +INF tai -INF, sillä ei silti olisi väliä. Meidän ei koskaan tarvinnut edes katsoa sitä, koska minimoinnin arvoksi taattiin 5 tai vähemmän. Joten heti kun maksimoija näki kuuden, hän tiesi, että pienentäjä ei koskaan tulisi tällä tavalla, koska hän voi saada 5:n vasemmalla puolella B . Tällä tavalla meidän ei tarvinnut katsoa sitä yhdeksää ja näin säästää laskenta-aikaa. E palauttaa arvon 6 to B . klo B , beeta = min( 5, 6), joka on 5. Solmun arvo B on myös 5
Toistaiseksi pelipuumme näyttää tältä. 9 on yliviivattu, koska sitä ei koskaan laskettu.
- B palauttaa 5:stä A . klo A , alfa = max( -INF, 5), joka on 5. Nyt maksimoijalle taataan arvo 5 tai suurempi. A nyt soittaa C nähdäksesi, voiko se saada korkeamman arvon kuin 5.
- klo C , alfa = 5 ja beta = +INF. C puhelut F
- klo F , alfa = 5 ja beta = +INF. F katsoo vasenta lastaan, joka on 1. alfa = max( 5, 1), joka on edelleen 5. F tarkastelee oikeaa lastaan, joka on 2. Tästä syystä tämän solmun paras arvo on 2. Alfa on edelleen 5 F palauttaa arvon 2 C . klo C , beeta = min( +INF, 2). Ehto beeta <= alfa tulee todeksi, kun beta = 2 ja alfa = 5. Joten se katkeaa eikä sen tarvitse edes laskea koko alipuuta G .
- Tämän katkaisun takana oleva intuitio on, että klo C minimoijalle taattiin arvo 2 tai vähemmän. Mutta maksimoijalle oli jo taattu arvo 5, jos hän valitsi B . Joten miksi maksimoija koskaan valitsisi? C ja saat arvon alle 2? Jälleen voit nähdä, että sillä ei ollut väliä mitkä nämä kaksi viimeistä arvoa olivat. Säästimme myös paljon laskentaa ohittamalla kokonaisen alipuun. C palauttaa nyt arvon 2 to A . Siksi paras hinta-laatusuhde A on max (5, 2), joka on 5.
- Siksi maksimoinnin optimaalinen arvo on 5
Tältä näyttää viimeinen pelipuumme. Kuten näet G on yliviivattu, koska sitä ei ole koskaan laskettu.
CPP
mamta kulkarni näyttelijä
// C++ program to demonstrate> // working of Alpha-Beta Pruning> #include> using> namespace> std;> // Initial values of> // Alpha and Beta> const> int> MAX = 1000;> const> int> MIN = -1000;> // Returns optimal value for> // current player(Initially called> // for root and maximizer)> int> minimax(>int> depth,>int> nodeIndex,> >bool> maximizingPlayer,> >int> values[],>int> alpha,> >int> beta)> {> > >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == 3)> >return> values[nodeIndex];> >if> (maximizingPlayer)> >{> >int> best = MIN;> >// Recur for left and> >// right children> >for> (>int> i = 0; i <2; i++)> >{> > >int> val = minimax(depth + 1, nodeIndex * 2 + i,> >false>, values, alpha, beta);> >best = max(best, val);> >alpha = max(alpha, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> >else> >{> >int> best = MAX;> >// Recur for left and> >// right children> >for> (>int> i = 0; i <2; i++)> >{> >int> val = minimax(depth + 1, nodeIndex * 2 + i,> >true>, values, alpha, beta);> >best = min(best, val);> >beta = min(beta, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> }> // Driver Code> int> main()> {> >int> values[8] = { 3, 5, 6, 9, 1, 2, 0, -1 };> >cout <<>'The optimal value is : '><< minimax(0, 0,>true>, values, MIN, MAX);;> >return> 0;> }> |
>
>
Java
// Java program to demonstrate> // working of Alpha-Beta Pruning> import> java.io.*;> class> GFG {> // Initial values of> // Alpha and Beta> static> int> MAX =>1000>;> static> int> MIN = ->1000>;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> static> int> minimax(>int> depth,>int> nodeIndex,> >Boolean maximizingPlayer,> >int> values[],>int> alpha,> >int> beta)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth ==>3>)> >return> values[nodeIndex];> >if> (maximizingPlayer)> >{> >int> best = MIN;> >// Recur for left and> >// right children> >for> (>int> i =>0>; i <>2>; i++)> >{> >int> val = minimax(depth +>1>, nodeIndex *>2> + i,> >false>, values, alpha, beta);> >best = Math.max(best, val);> >alpha = Math.max(alpha, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> >else> >{> >int> best = MAX;> >// Recur for left and> >// right children> >for> (>int> i =>0>; i <>2>; i++)> >{> > >int> val = minimax(depth +>1>, nodeIndex *>2> + i,> >true>, values, alpha, beta);> >best = Math.min(best, val);> >beta = Math.min(beta, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> }> >// Driver Code> >public> static> void> main (String[] args)> >{> > >int> values[] = {>3>,>5>,>6>,>9>,>1>,>2>,>0>, ->1>};> >System.out.println(>'The optimal value is : '> +> >minimax(>0>,>0>,>true>, values, MIN, MAX));> > >}> }> // This code is contributed by vt_m.> |
>
>
Python 3
# Python3 program to demonstrate> # working of Alpha-Beta Pruning> # Initial values of Alpha and Beta> MAX>,>MIN> => 1000>,>->1000> # Returns optimal value for current player> #(Initially called for root and maximizer)> def> minimax(depth, nodeIndex, maximizingPlayer,> >values, alpha, beta):> > ># Terminating condition. i.e> ># leaf node is reached> >if> depth>=>=> 3>:> >return> values[nodeIndex]> >if> maximizingPlayer:> > >best>=> MIN> ># Recur for left and right children> >for> i>in> range>(>0>,>2>):> > >val>=> minimax(depth>+> 1>, nodeIndex>*> 2> +> i,> >False>, values, alpha, beta)> >best>=> max>(best, val)> >alpha>=> max>(alpha, best)> ># Alpha Beta Pruning> >if> beta <>=> alpha:> >break> > >return> best> > >else>:> >best>=> MAX> ># Recur for left and> ># right children> >for> i>in> range>(>0>,>2>):> > >val>=> minimax(depth>+> 1>, nodeIndex>*> 2> +> i,> >True>, values, alpha, beta)> >best>=> min>(best, val)> >beta>=> min>(beta, best)> ># Alpha Beta Pruning> >if> beta <>=> alpha:> >break> > >return> best> > # Driver Code> if> __name__>=>=> '__main__'>:> > >values>=> [>3>,>5>,>6>,>9>,>1>,>2>,>0>,>->1>]> >print>(>'The optimal value is :'>, minimax(>0>,>0>,>True>, values,>MIN>,>MAX>))> > # This code is contributed by Rituraj Jain> |
>
>
C#
// C# program to demonstrate> // working of Alpha-Beta Pruning> using> System;> > class> GFG> {> // Initial values of> // Alpha and Beta> static> int> MAX = 1000;> static> int> MIN = -1000;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> static> int> minimax(>int> depth,>int> nodeIndex,> >Boolean maximizingPlayer,> >int> []values,>int> alpha,> >int> beta)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == 3)> >return> values[nodeIndex];> >if> (maximizingPlayer)> >{> >int> best = MIN;> >// Recur for left and> >// right children> >for> (>int> i = 0; i <2; i++)> >{> >int> val = minimax(depth + 1, nodeIndex * 2 + i,> >false>, values, alpha, beta);> >best = Math.Max(best, val);> >alpha = Math.Max(alpha, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> >else> >{> >int> best = MAX;> >// Recur for left and> >// right children> >for> (>int> i = 0; i <2; i++)> >{> > >int> val = minimax(depth + 1, nodeIndex * 2 + i,> >true>, values, alpha, beta);> >best = Math.Min(best, val);> >beta = Math.Min(beta, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> }> // Driver Code> public> static> void> Main (String[] args)> {> > >int> []values = {3, 5, 6, 9, 1, 2, 0, -1};> >Console.WriteLine(>'The optimal value is : '> +> >minimax(0, 0,>true>, values, MIN, MAX));> }> }> // This code is contributed by 29AjayKumar> |
>
>
Javascript
> // Javascript program to demonstrate> // working of Alpha-Beta Pruning> // Initial values of> // Alpha and Beta> let MAX = 1000;> let MIN = -1000;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> function> minimax(depth,nodeIndex,maximizingPlayer,values,alpha,beta)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == 3)> >return> values[nodeIndex];> > >if> (maximizingPlayer)> >{> >let best = MIN;> > >// Recur for left and> >// right children> >for> (let i = 0; i <2; i++)> >{> >let val = minimax(depth + 1, nodeIndex * 2 + i,> >false>, values, alpha, beta);> >best = Math.max(best, val);> >alpha = Math.max(alpha, best);> > >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> >else> >{> >let best = MAX;> > >// Recur for left and> >// right children> >for> (let i = 0; i <2; i++)> >{> > >let val = minimax(depth + 1, nodeIndex * 2 + i,> >true>, values, alpha, beta);> >best = Math.min(best, val);> >beta = Math.min(beta, best);> > >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> }> // Driver Code> let values=[3, 5, 6, 9, 1, 2, 0, -1];> document.write(>'The optimal value is : '> +> >minimax(0, 0,>true>, values, MIN, MAX));> // This code is contributed by rag2127> > |
>
>Lähtö
The optimal value is : 5>