logo

TechCodeview

Minimax Algoritmus v teórii hier | Sada 4 (Alfa-Beta prerezávanie)

Predpoklady: Minimax algoritmus v teórii hier , Funkcia hodnotenia v teórii hier
Alfa-Beta prerezávanie nie je v skutočnosti nový algoritmus, ale skôr optimalizačná technika pre minimax algoritmus. Výrazne znižuje čas výpočtu. To nám umožňuje hľadať oveľa rýchlejšie a dokonca ísť do hlbších úrovní v strome hry. Odreže vetvy v strome hry, ktoré netreba hľadať, pretože už existuje lepší dostupný ťah. Volá sa prerezávanie Alpha-Beta, pretože vo funkcii minimax odovzdáva 2 ďalšie parametre, a to alfa a beta.

Definujme parametre alfa a beta.

Alfa je najlepšia hodnota, ktorá maximalizátor v súčasnosti môže garantovať na tejto úrovni alebo vyššej.
Beta je najlepšia hodnota, ktorá minimalizátor v súčasnosti môže garantovať na tejto alebo nižšej úrovni.



Pseudokód:

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

Vysvetlíme si vyššie uvedený algoritmus na príklade.

Alfa Beta prerezávanie

  • Počiatočný hovor začína od A . Tu je hodnota alfa -NEKONEČNO a hodnota beta je + NEKONEČNO . Tieto hodnoty sa prenášajú do nasledujúcich uzlov v strome. o A maximalizátor musí zvoliť max B a C , takže A hovory B najprv
  • o B minimalizátor musí zvoliť min D a A a teda volania D najprv.
  • o D , pozerá sa na svoje ľavé dieťa, ktorým je listový uzol. Tento uzol vráti hodnotu 3. Teraz hodnota alfa at D je max(-INF, 3), čo je 3.
  • Aby sa rozhodol, či stojí za to pozrieť sa na jeho pravý uzol alebo nie, kontroluje stav beta<=alfa. Toto je nepravda, pretože beta = +INF a alfa = 3. Takže pokračuje v hľadaní.
    • D sa teraz pozrie na svojho pravého potomka, ktorý vráti hodnotu 5.At D , alpha = max(3, 5), čo je 5. Teraz hodnota uzla D je 5 D vráti hodnotu 5 až B . o B , beta = min( +INF, 5), čo je 5. Minimalizátor má teraz zaručenú hodnotu 5 alebo menej. B teraz volá A aby zistil, či môže získať nižšiu hodnotu ako 5.
  • o A hodnoty alfa a beta nie sú -INF a +INF, ale namiesto toho -INF a 5, pretože hodnota beta sa zmenila o B a to je čo B odovzdaný do A
  • Teraz A pozerá na svoje ľavé dieťa, ktoré má 6. At A , alfa = max(-INF, 6), čo je 6. Tu sa podmienka stáva pravdivou. beta je 5 a alfa je 6. Takže beta<=alfa je pravda. Preto sa láme a A vráti 6 do B
  • Všimnite si, ako nezáležalo na hodnote A 'správne dieťa je. Mohlo to byť +INF alebo -INF, aj tak by na tom nezáležalo, ani sme sa na to nemuseli pozerať, pretože minimalizátor mal garantovanú hodnotu 5 alebo menej. Takže akonáhle maximalizátor videl 6, vedel, že minimalizátor nikdy nepríde týmto smerom, pretože môže dostať 5 na ľavej strane B . Týmto spôsobom sme sa nemuseli pozerať na tých 9, a tým sme ušetrili výpočtový čas.
    • E vráti hodnotu 6 až B . o B , beta = min( 5, 6), čo je 5. Hodnota uzla B je tiež 5

Náš herný strom zatiaľ vyzerá takto. Číslo 9 je prečiarknuté, pretože nebolo nikdy vypočítané.

Alfa beta prerezávanie 2

0,0625 ako zlomok
    B vráti 5 až A . o A , alpha = max( -INF, 5), čo je 5. Teraz má maximalizér zaručenú hodnotu 5 alebo vyššiu. A teraz volá C aby ste zistili, či môže získať vyššiu hodnotu ako 5.
  • o C , alfa = 5 a beta = + INF. C hovory F
  • o F , alfa = 5 a beta = + INF. F pozrie sa na svoje ľavé dieťa, ktoré je 1. alfa = max( 5, 1), čo je stále 5.
    • F sa pozrie na svoje pravé potomstvo, ktoré je 2. Preto je najlepšia hodnota tohto uzla 2. Alfa stále zostáva 5 F vráti hodnotu 2 až C . o C , beta = min ( + INF, 2). Podmienka beta <= alfa sa stane pravdivou ako beta = 2 a alfa = 5. Takže sa poruší a nemusí ani vypočítať celý podstrom G .
  • Intuícia za týmto zlom je, že pri C minimalizátorom bola garantovaná hodnota 2 alebo menšia. Ale maximalizér už mal garantovanú hodnotu 5, ak si vyberie B . Prečo by si teda maximalizátor vôbec vybral C a získať hodnotu menšiu ako 2? Opäť môžete vidieť, že nezáleží na tom, aké boli posledné 2 hodnoty. Tiež sme ušetrili veľa výpočtov preskočením celého podstromu.
    • C teraz vráti hodnotu 2 to A . Preto najlepšia hodnota pri A je max (5, 2), čo je 5.
  • Optimálna hodnota, ktorú môže maximalizátor získať, je teda 5

Takto vyzerá náš posledný herný strom. Ako môžeš vidieť G bola prečiarknutá, pretože nebola nikdy vypočítaná.

Alfa beta prerezávanie 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>

knn 

>

>

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

>

>

Výkon 

The optimal value is : 5>