Būtinos sąlygos: Minimax algoritmas žaidimų teorijoje , Vertinimo funkcija žaidimų teorijoje
Alfa-Beta genėjimas iš tikrųjų nėra naujas algoritmas, o veikiau minimalaus algoritmo optimizavimo technika. Tai labai sumažina skaičiavimo laiką. Tai leidžia mums ieškoti daug greičiau ir netgi pereiti į gilesnius žaidimo medžio lygius. Jis žaidimo medyje nupjauna šakas, kurių nereikia ieškoti, nes jau yra geresnis judesys. Jis vadinamas alfa-beta genėjimu, nes per „minimax“ funkciją perduoda 2 papildomus parametrus, būtent alfa ir beta.
Apibrėžkime parametrus alfa ir beta.
Alfa yra geriausia vertė maksimizatorius šiuo metu gali garantuoti tokį ar aukštesnį lygį.
Beta yra geriausia vertė minimizatorius šiuo metu gali garantuoti tokį ar žemesnį lygį.
Greatandhra
Pseudokodas:
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)>
Paaiškinkime aukščiau pateiktą algoritmą pavyzdžiu.
- Pradinis skambutis prasideda nuo A . Alfa vertė čia yra -BEGALINĖ o beta vertė yra +BEGALIS . Šios reikšmės perduodamos tolesniems medžio mazgams. At A maksimizatorius turi pasirinkti maks B ir C , taip A skambučių B Pirmas
- At B tai minimalizatorius turi pasirinkti min D ir IR ir todėl skambina D Pirmas.
- At D , jis žiūri į savo kairįjį vaiką, kuris yra lapo mazgas. Šis mazgas grąžina reikšmę 3. Dabar alfa reikšmė at D yra maksimalus (-INF, 3), kuris yra 3.
- Kad nuspręstų, ar verta žiūrėti į dešinįjį mazgą, ar ne, jis patikrina sąlygą beta<=alpha. Tai klaidinga, nes beta = +INF ir alfa = 3. Taigi ji tęsia paiešką. D dabar žiūri į savo dešinįjį atžalą, kuris grąžina reikšmę 5.At D , alfa = max(3, 5), kuri yra 5. Dabar mazgo reikšmė D yra 5 D grąžina reikšmę nuo 5 iki B . At B , beta = min( +INF, 5), kuri yra 5. Dabar minimalizatoriaus vertė yra 5 arba mažesnė. B dabar skambina IR kad pamatytumėte, ar jis gali gauti mažesnę reikšmę nei 5.
- At IR alfa ir beta vertės yra ne -INF ir +INF, o atitinkamai -INF ir 5, nes beta vertė buvo pakeista B ir tai yra kas B perduotas IR
- Dabar IR žiūri į savo kairįjį vaiką, kuris yra 6. Prie IR , alfa = max(-INF, 6), kuri yra 6. Čia sąlyga tampa teisinga. beta yra 5, o alfa yra 6. Taigi beta<=alfa yra tiesa. Todėl sugenda ir IR grąžina 6 į B
- Atkreipkite dėmesį, kaip nesvarbu, kokia vertė IR teisingas vaikas. Tai galėjo būti +INF arba -INF, vis tiek nesvarbu, mums niekada net nereikėjo į tai žiūrėti, nes minimalizatoriaus vertė buvo garantuota 5 ar mažesnė. Taigi, kai tik maksimizatorius pamatė 6, jis žinojo, kad sumažinimas niekada nepasirodys tokiu būdu, nes jis gali gauti 5 kairėje B . Tokiu būdu mums nereikėjo žiūrėti į tą 9 ir taip sutaupėme skaičiavimo laiko. E grąžina reikšmę nuo 6 iki B . At B , beta = min( 5, 6), tai yra 5. Mazgo reikšmė B taip pat yra 5
Kol kas taip atrodo mūsų žaidimų medis. 9 yra perbrauktas, nes jis niekada nebuvo apskaičiuotas.
- B grąžina 5 į A . At A , alfa = max( -INF, 5), kuri yra 5. Dabar maksimizatoriaus vertė yra 5 arba didesnė. A dabar skambina C kad pamatytumėte, ar jo vertė gali būti didesnė nei 5.
- At C , alfa = 5 ir beta = +INF. C skambučių F
- At F , alfa = 5 ir beta = +INF. F žiūri į savo kairįjį vaiką, kuris yra 1. alfa = max( 5, 1), kuris vis dar yra 5. F žiūri į savo dešinįjį atžalą, kuris yra 2. Taigi geriausia šio mazgo vertė yra 2. Alfa vis tiek išlieka 5 F grąžina 2 reikšmę C . At C , beta = min( +INF, 2). Sąlyga beta <= alfa tampa teisinga, kai beta = 2 ir alfa = 5. Taigi ji nutrūksta ir net nereikia skaičiuoti viso medžio submedžio. G .
- Šio nutraukimo slypi intuicija ta, kad C minimalizatoriui buvo garantuota 2 ar mažesnė vertė. Bet maksimizeriui jau buvo garantuota 5 vertė, jei jis pasirinks B . Taigi kodėl maksimizatorius kada nors turėtų pasirinkti C ir gauti vertę, mažesnę nei 2? Vėlgi matote, kad nesvarbu, kokios buvo paskutinės 2 vertės. Taip pat sutaupėme daug skaičiavimo, praleisdami visą pomedį. C dabar grąžina reikšmę nuo 2 iki A . Todėl geriausia kaina A yra maksimalus (5, 2), tai yra 5.
- Taigi optimali vertė, kurią gali gauti maksimizatorius, yra 5
Štai kaip atrodo mūsų galutinis žaidimo medis. Kaip matai G buvo perbrauktas, nes niekada nebuvo apskaičiuotas.
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;> }> |
ar klasė gali išplėsti kelias klases
>
>
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
žibintuvėlio montavimas
# 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> |
>
>
10 iš 40
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
surūšiuotas tuple python
> // 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> > |
>
>Išvestis
The optimal value is : 5>