Warunki wstępne: Algorytm Minimax w teorii gier , Funkcja oceny w teorii gier
Przycinanie alfa-beta nie jest w rzeczywistości nowym algorytmem, ale raczej techniką optymalizacji algorytmu minimax. Skraca to czas obliczeń w ogromnym stopniu. Dzięki temu możemy wyszukiwać znacznie szybciej, a nawet wchodzić na głębsze poziomy drzewa gry. Odcina gałęzie w drzewie gry, których nie trzeba przeszukiwać, ponieważ istnieje już lepszy dostępny ruch. Nazywa się to przycinaniem alfa-beta, ponieważ przekazuje 2 dodatkowe parametry w funkcji minimax, mianowicie alfa i beta.
Zdefiniujmy parametry alfa i beta.
Alfa jest najlepszą wartością, jaką może osiągnąć maksymalizator obecnie może zagwarantować na tym poziomie lub wyższym.
Beta jest najlepszą wartością, jaką może osiągnąć minimalizator obecnie może zagwarantować na tym poziomie lub poniżej.
Pseudo kod :
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)>
Wyjaśnijmy powyższy algorytm na przykładzie.
- Pierwsze połączenie rozpoczyna się od A . Wartość alfa wynosi tutaj -NIESKOŃCZONOŚĆ a wartość beta wynosi +NIESKOŃCZONOŚĆ . Wartości te przekazywane są do kolejnych węzłów w drzewie. Na A maksymalizator musi wybrać max B I C , Więc A dzwoni B Pierwszy
- Na B to minimalizator musi wybrać min D I I i dlatego dzwoni D Pierwszy.
- Na D , patrzy na swoje lewe dziecko, które jest węzłem liścia. Węzeł ten zwraca wartość 3. Teraz wartość alfa at D to max(-INF, 3), czyli 3.
- Aby zdecydować, czy warto patrzeć na jego prawy węzeł, czy nie, sprawdza warunek beta<=alfa. Jest to fałszywe, ponieważ beta = +INF i alfa = 3. Zatem wyszukiwanie jest kontynuowane. D patrzy teraz na swoje prawe dziecko, które zwraca wartość 5.At D , alfa = max(3, 5), czyli 5. Teraz wartość węzła D wynosi 5 D zwraca wartość 5 do B . Na B , beta = min( +INF, 5), czyli 5. Minimalizator ma teraz gwarantowaną wartość 5 lub mniejszą. B teraz dzwoni I sprawdzić, czy uda mu się uzyskać wartość niższą niż 5.
- Na I wartości alfa i beta to nie -INF i +INF, ale odpowiednio -INF i 5, ponieważ wartość beta została zmieniona o B i to jest to B przekazane do I
- Teraz I patrzy na swoje lewe dziecko, które ma 6 lat I , alfa = max(-INF, 6), czyli 6. Tutaj warunek staje się prawdziwy. beta wynosi 5, a alfa wynosi 6. Zatem beta<=alfa jest prawdą. Dlatego pęka i I zwraca 6 do B
- Zwróć uwagę, że nie ma znaczenia, jaka jest wartość I właściwym dzieckiem jest. Mogło to być +INF lub -INF, to i tak nie miałoby znaczenia. Nigdy nawet nie musieliśmy na to patrzeć, ponieważ minimalizator miał gwarantowaną wartość 5 lub mniejszą. Zatem gdy tylko maksymalizator zobaczył 6, wiedział, że minimalizator nigdy nie przejdzie w tę stronę, ponieważ może uzyskać 5 po lewej stronie B . W ten sposób nie musieliśmy patrzeć na tę 9, co pozwoliło zaoszczędzić czas obliczeń. E zwraca wartość 6 do B . Na B , beta = min( 5, 6), czyli 5. Wartość węzła B jest również 5
Na razie tak wygląda nasze drzewo gry. Liczba 9 została przekreślona, ponieważ nigdy nie została obliczona.
- B zwraca 5 do A . Na A , alfa = max(-INF, 5), czyli 5. Teraz maksymalizator ma gwarantowaną wartość 5 lub większą. A teraz dzwoni C aby sprawdzić, czy może uzyskać wartość wyższą niż 5.
- Na C , alfa = 5 i beta = +INF. C dzwoni F
- Na F , alfa = 5 i beta = +INF. F patrzy na swoje lewe dziecko, które jest 1. alfa = max( 5, 1), które wciąż wynosi 5. F patrzy na swoje prawe dziecko, którym jest 2. Zatem najlepszą wartością tego węzła jest 2. Alfa nadal pozostaje 5 F zwraca wartość 2 do C . Na C , beta = min( +INF, 2). Warunek beta <= alfa staje się prawdziwy, gdy beta = 2 i alfa = 5. Zatem się psuje i nie musi nawet obliczać całego poddrzewa G .
- Intuicja stojąca za tym zerwaniem jest taka, że o godz C minimalizator miał gwarantowaną wartość 2 lub mniejszą. Ale maksymalizator miał już gwarantowaną wartość 5, jeśli tak zdecydował B . Dlaczego więc maksymalizator miałby kiedykolwiek wybierać C i uzyskać wartość mniejszą niż 2? Znów widać, że nie miało znaczenia, jakie były te 2 ostatnie wartości. Zaoszczędziliśmy także wiele obliczeń, pomijając całe poddrzewo. C zwraca teraz wartość 2 do A . Dlatego najlepsza wartość przy A to max( 5, 2), czyli 5.
- Zatem optymalna wartość, jaką może uzyskać maksymalizator, wynosi 5
Tak wygląda nasze ostateczne drzewo gry. Jak widzisz G została przekreślona, gdyż nigdy nie została obliczona.
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;> }> |
>
maszynopis mapy
>
Jawa
// 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> |
>
>
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> > |
programowanie stdin c
>
>Wyjście
The optimal value is : 5>