logo

TechCodeview

Minimax algoritms spēļu teorijā | 4. komplekts (alfa-beta atzarošana)

Priekšnosacījumi: Minimax algoritms spēļu teorijā , Novērtēšanas funkcija spēļu teorijā
Alfa-Beta atzarošana patiesībā nav jauns algoritms, bet gan minimax algoritma optimizācijas paņēmiens. Tas ievērojami samazina aprēķina laiku. Tas ļauj mums meklēt daudz ātrāk un pat iedziļināties spēles koka līmeņos. Tas nogriež spēļu kokā zarus, kas nav jāmeklē, jo jau ir pieejams labāks gājiens. To sauc par alfa-beta apgriešanu, jo tā nodod 2 papildu parametrus minimax funkcijā, proti, alfa un beta.

Definēsim parametrus alfa un beta.

Alfa ir labākā vērtība maksimizētājs šobrīd var garantēt šajā vai augstākajā līmenī.
Beta ir labākā vērtība minimizētājs šobrīd var garantēt šajā vai zemākā līmenī.



Pseidokods:

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

Skaidrosim iepriekš minēto algoritmu ar piemēru.

Alfa beta atzarošana

  • Sākotnējais zvans sākas no plkst A . Alfa vērtība šeit ir -BEZGALĪBA un beta vērtība ir +BEZGALĪBA . Šīs vērtības tiek nodotas nākamajiem koka mezgliem. Plkst A maksimizatoram jāizvēlas maks. no B un C , tātad A zvani B vispirms
  • Plkst B tas minimizētājam jāizvēlas min no D un UN un līdz ar to zvani D vispirms.
  • Plkst D , tas skatās uz savu kreiso bērnu, kas ir lapas mezgls. Šis mezgls atgriež vērtību 3. Tagad alfa vērtība ir D ir max (-INF, 3), kas ir 3.
  • Lai izlemtu, vai ir vērts aplūkot tā labo mezglu, tas pārbauda nosacījumu beta<=alpha. Tas ir nepatiess, jo beta = +INF un alfa = 3. Tātad tas turpina meklēšanu.
    • D tagad aplūko savu labo atvasi, kas atgriež vērtību 5.At D , alfa = max(3, 5), kas ir 5. Tagad mezgla vērtība D ir 5 D atgriež vērtību no 5 līdz B . Plkst B , beta = min( +INF, 5), kas ir 5. Minimizētājam tagad tiek garantēta vērtība 5 vai mazāka. B tagad zvani UN lai redzētu, vai viņš var iegūt mazāku vērtību par 5.
  • Plkst UN alfa un beta vērtības nav -INF un +INF, bet gan attiecīgi -INF un 5, jo beta vērtība tika mainīta plkst. B un tas ir kas B nodots UN
  • Tagad UN skatās uz savu kreiso bērnu, kas ir 6. Plkst UN , alfa = max(-INF, 6), kas ir 6. Šeit nosacījums kļūst patiess. beta ir 5 un alfa ir 6. Tātad beta<=alfa ir taisnība. Līdz ar to tas saplīst un UN atgriež 6 līdz B
  • Ņemiet vērā, ka nebija svarīgi, kāda vērtība UN īstais bērns ir. Tas varēja būt +INF vai -INF, tam joprojām nebūtu nozīmes. Mums tas nekad nebija pat jāskatās, jo minimizeram tika garantēta vērtība 5 vai mazāka. Tātad, tiklīdz maksimizētājs ieraudzīja 6, viņš zināja, ka minimizētājs nekad nenonāks šādā veidā, jo viņš var iegūt 5 kreisajā pusē. B . Tādā veidā mums nebija jāskatās uz 9 un tādējādi tika ietaupīts aprēķina laiks.
    • E atgriež vērtību no 6 līdz B . Plkst B , beta = min( 5, 6), kas ir 5. Mezgla vērtība B ir arī 5

Līdz šim šādi izskatās mūsu spēļu koks. 9 ir izsvītrots, jo tas nekad netika aprēķināts.

Alfa beta atzarošana 2

    B atgriež 5 uz A . Plkst A , alfa = max( -INF, 5), kas ir 5. Tagad maksimizatoram tiek garantēta vērtība 5 vai lielāka. A tagad zvani C lai redzētu, vai tā var iegūt lielāku vērtību par 5.
  • Plkst C , alfa = 5 un beta = +INF. C zvani F
  • Plkst F , alfa = 5 un beta = +INF. F skatās uz kreiso bērnu, kas ir 1. alfa = max( 5, 1), kas joprojām ir 5.
    • F aplūko savu labo bērnu, kas ir 2. Tādējādi šī mezgla labākā vērtība ir 2. Alfa joprojām paliek 5 F atgriež vērtību 2, lai C . Plkst C , beta = min( +INF, 2). Nosacījums beta <= alfa kļūst patiess, jo beta = 2 un alfa = 5. Tātad tas sabojājas, un tai pat nav jāaprēķina viss apakškoks. G .
  • Šīs pārtraukuma pamatā ir intuīcija, ka plkst C minimizeram tika garantēta vērtība 2 vai mazāka. Bet maksimizētājam jau bija garantēta vērtība 5, ja viņš izvēlēsies B . Tātad, kāpēc maksimizētājs kādreiz izvēlētos? C un iegūt vērtību, kas mazāka par 2? Atkal jūs varat redzēt, ka nebija svarīgi, kādas bija šīs pēdējās 2 vērtības. Mēs arī ietaupījām daudz aprēķinu, izlaižot visu apakškoku.
    • C tagad atgriež vērtību no 2 līdz A . Tāpēc vislabākā vērtība A ir max (5, 2), kas ir 5.
  • Tādējādi maksimālā vērtība, ko var iegūt maksimizators, ir 5

Šādi izskatās mūsu gala spēles koks. Kā jūs redzat G ir izsvītrots, jo tas nekad netika aprēķināts.

Alfa beta atzarošana 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




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

>

>

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>

mysql parādīt visus lietotājus 
>

>

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

>

>

Izvade 

The optimal value is : 5>