logo

TechCodeview

Algoritmul Minimax în teoria jocurilor | Setul 4 (Tăieri Alpha-Beta)

Cerințe preliminare: Algoritmul Minimax în teoria jocurilor , Funcția de evaluare în teoria jocurilor
Tăierea Alpha-Beta nu este de fapt un algoritm nou, ci mai degrabă o tehnică de optimizare pentru algoritmul minimax. Reduce timpul de calcul cu un factor uriaș. Acest lucru ne permite să căutăm mult mai rapid și chiar să intrăm în niveluri mai profunde din arborele jocului. Taie ramurile din arborele jocului care nu trebuie căutate, deoarece există deja o mișcare mai bună disponibilă. Se numește tăiere Alpha-Beta deoarece trece 2 parametri suplimentari în funcția minimax și anume alfa și beta.

Să definim parametrii alfa și beta.

Alfa este cea mai bună valoare pe care maximizator în prezent poate garanta la acel nivel sau mai sus.
Beta este cea mai bună valoare pe care minimizator în prezent poate garanta la acel nivel sau mai jos.



Pseudo cod :

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

Să clarificăm algoritmul de mai sus cu un exemplu.

Tunderea Alpha Beta

  • Apelul inițial începe de la A . Valoarea lui alfa este aici -INFINIT iar valoarea beta este +INFINITATE . Aceste valori sunt transmise nodurilor ulterioare din arbore. La A maximizatorul trebuie să aleagă max de B și C , asa de A apeluri B primul
  • La B minimizatorul trebuie să aleagă min de D și ȘI și deci apeluri D primul.
  • La D , se uită la copilul său stâng care este un nod frunză. Acest nod returnează o valoare de 3. Acum valoarea lui alpha at D este max( -INF, 3) care este 3.
  • Pentru a decide dacă merită să se uite la nodul său drept sau nu, verifică condiția beta<=alpha. Acest lucru este fals deoarece beta = +INF și alfa = 3. Deci continuă căutarea.
    • D acum se uită la copilul său drept care returnează o valoare de 5.At D , alpha = max(3, 5) care este 5. Acum valoarea nodului D este 5 D returnează o valoare de 5 la B . La B , beta = min( +INF, 5) care este 5. Minimizatorul are acum garantată o valoare de 5 sau mai mică. B acum sună ȘI pentru a vedea dacă poate obține o valoare mai mică decât 5.
  • La ȘI valorile alfa și beta nu sunt -INF și +INF, ci în schimb -INF și respectiv 5, deoarece valoarea beta a fost modificată la B si asta este ceea ce B transmis în jos la ȘI
  • Acum ȘI se uită la copilul său stâng care are 6. At ȘI , alfa = max(-INF, 6) care este 6. Aici condiția devine adevărată. beta este 5 și alfa este 6. Deci beta<=alpha este adevărat. Prin urmare se rupe și ȘI revine 6 la B
  • Observați cum nu a contat care este valoarea ȘI copilul potrivit este. Ar fi putut fi +INF sau -INF, tot nu ar conta, nici măcar nu a trebuit să ne uităm la el, deoarece minimizatorului i se garanta o valoare de 5 sau mai mică. Deci, de îndată ce maximizatorul a văzut 6, a știut că minimizatorul nu va veni niciodată în acest sens, deoarece poate obține un 5 pe partea stângă a B . În acest fel, nu a trebuit să ne uităm la acel 9 și, prin urmare, am economisit timp de calcul.
    • E returnează o valoare de 6 la B . La B , beta = min( 5, 6) care este 5. Valoarea nodului B este de asemenea 5

Până acum, așa arată arborele nostru de jocuri. 9 este tăiat pentru că nu a fost niciodată calculat.

Tunderea Alpha Beta 2

    B returnează 5 la A . La A , alpha = max( -INF, 5) care este 5. Acum maximizatorului i se garantează o valoare de 5 sau mai mare. A acum sună C pentru a vedea dacă poate obține o valoare mai mare decât 5.
  • La C , alfa = 5 și beta = +INF. C apeluri F
  • La F , alfa = 5 și beta = +INF. F se uită la copilul său stâng care este un 1. alfa = max( 5, 1) care este încă 5.
    • F se uită la copilul său drept, care este un 2. Prin urmare, cea mai bună valoare a acestui nod este 2. Alpha rămâne 5 F returnează o valoare de 2 la C . La C , beta = min( +INF, 2). Condiția beta <= alfa devine adevărată ca beta = 2 și alfa = 5. Deci se rupe și nici măcar nu trebuie să calculeze întregul sub-arboresc al G .
  • Intuiția din spatele acestei rupturi este că, la C minimizatorului i sa garantat o valoare de 2 sau mai mică. Dar maximizatorului i s-a garantat deja o valoare de 5 dacă alege B . Deci, de ce ar alege vreodată maximizatorul C și obțineți o valoare mai mică de 2? Din nou, puteți vedea că nu a contat care au fost ultimele 2 valori. De asemenea, am salvat o mulțime de calcule omitând un întreg sub-arboresc.
    • C returnează acum o valoare de 2 la A . Prin urmare, cea mai bună valoare la A este max( 5, 2) care este un 5.
  • Prin urmare, valoarea optimă pe care o poate obține maximizatorul este 5

Așa arată arborele nostru final de joc. După cum puteți vedea G a fost tăiat deoarece nu a fost niciodată calculat.

Tunderea Alpha Beta 3

CPP




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


logo 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.> 

>

>

Python3




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

index de java 

>

>

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

>

>

Ieșire 

The optimal value is : 5>