Algorytm Minimax w teorii gier | Zestaw 1 (Wprowadzenie)
Minimax to rodzaj algorytmu cofania, który jest używany w podejmowaniu decyzji i teorii gier w celu znalezienia optymalnego ruchu dla gracza, przy założeniu, że Twój przeciwnik również gra optymalnie. Jest szeroko stosowany w grach turowych dla dwóch graczy, takich jak Kółko i krzyżyk, Backgammon, Mancala, Szachy itp.
W Minimaxie tych dwóch graczy nazywa się maksymalizatorem i minimalizatorem. The maksymalizator stara się uzyskać jak najwyższy wynik, podczas gdy minimalizator próbuje zrobić odwrotnie i uzyskać jak najniższy wynik.
Z każdym stanem planszy jest powiązana wartość. W danym stanie, jeśli maksymalizator ma przewagę, wynik na szachownicy będzie miał raczej wartość dodatnią. Jeśli minimalizator ma przewagę w tym stanie płytki, wówczas będzie to raczej wartość ujemna. Wartości planszy są obliczane za pomocą heurystyk, które są unikalne dla każdego rodzaju gry.
Przykład:
Rozważmy grę, która ma 4 stany końcowe, a ścieżki do osiągnięcia stanu końcowego prowadzą od korzenia do 4 liści doskonałego drzewa binarnego, jak pokazano poniżej. Załóżmy, że jesteś graczem maksymalizującym i masz pierwszą szansę na ruch, czyli jesteś u korzenia, a przeciwnik na następnym poziomie. Jaki ruch wykonałbyś jako gracz maksymalizujący, biorąc pod uwagę, że Twój przeciwnik również gra optymalnie?
Ponieważ jest to algorytm oparty na wycofywaniu się, próbuje wszystkich możliwych ruchów, następnie wycofuje się i podejmuje decyzję.
- Maksymalizator idzie w LEWO: teraz kolej na minimalizatory. Minimalizator ma teraz wybór pomiędzy 3 a 5. Jako minimalizator na pewno wybierze najmniej spośród obu, czyli 3
- Maksymalizator idzie W PRAWO: teraz kolej na minimalizatorów. Minimalizator ma teraz wybór pomiędzy 2 a 9. Wybierze 2, ponieważ jest to najmniejsza z dwóch wartości.
Będąc maksymalizatorem, wybrałbyś większą wartość, czyli 3. Zatem optymalnym ruchem dla maksymalizatora jest przejście w LEWO, a optymalna wartość to 3.
Teraz drzewo gry wygląda jak poniżej:
Powyższe drzewo pokazuje dwa możliwe wyniki, gdy maksymalizator wykonuje ruchy w lewo i w prawo.
Uwaga: mimo że w prawym poddrzewie znajduje się wartość 9, minimalizator nigdy jej nie wybierze. Zawsze musimy zakładać, że nasz przeciwnik gra optymalnie.
Poniżej znajduje się implementacja tego samego.
C++
// A simple C++ program to find> // maximum score that> // maximizing player can get.> #include> using> namespace> std;> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is> // of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> int> minimax(> int> depth,> int> nodeIndex,> bool> isMax,> > int> scores[],> int> h)> {> > // Terminating condition. i.e> > // leaf node is reached> > if> (depth == h)> > return> scores[nodeIndex];> > // If current move is maximizer,> > // find the maximum attainable> > // value> > if> (isMax)> > return> max(minimax(depth+1, nodeIndex*2,> false> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> false> , scores, h));> > // Else (If current move is Minimizer), find the minimum> > // attainable value> > else> > return> min(minimax(depth+1, nodeIndex*2,> true> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> true> , scores, h));> }> // A utility function to find Log n in base 2> int> log2(> int> n)> {> > return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> int> main()> {> > // The number of elements in scores must be> > // a power of 2.> > int> scores[] = {3, 5, 2, 9, 12, 5, 23, 23};> > int> n => sizeof> (scores)/> sizeof> (scores[0]);> > int> h = log2(n);> > int> res = minimax(0, 0,> true> , scores, h);> > cout < <> 'The optimal value is : '> < < res < < endl;> > return> 0;> }> |
Jawa
// A simple java program to find maximum score that> // maximizing player can get.> import> java.io.*;> class> GFG {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> > static> int> minimax(> int> depth,> int> nodeIndex,> boolean> isMax,> > int> scores[],> int> h)> {> > // Terminating condition. i.e leaf node is reached> > if> (depth == h)> > return> scores[nodeIndex];> > // If current move is maximizer, find the maximum attainable> > // value> > if> (isMax)> > return> Math.max(minimax(depth+> 1> , nodeIndex*> 2> ,> false> , scores, h),> > minimax(depth+> 1> , nodeIndex*> 2> +> 1> ,> false> , scores, h));> > // Else (If current move is Minimizer), find the minimum> > // attainable value> > else> > return> Math.min(minimax(depth+> 1> , nodeIndex*> 2> ,> true> , scores, h),> > minimax(depth+> 1> , nodeIndex*> 2> +> 1> ,> true> , scores, h));> }> // A utility function to find Log n in base 2> > static> int> log2(> int> n)> {> return> (n==> 1> )?> 0> :> 1> + log2(n/> 2> );> }> // Driver code> > public> static> void> main (String[] args) {> > // The number of elements in scores must be> > // a power of 2.> > int> scores[] = {> 3> ,> 5> ,> 2> ,> 9> ,> 12> ,> 5> ,> 23> ,> 23> };> > int> n = scores.length;> > int> h = log2(n);> > int> res = minimax(> 0> ,> 0> ,> true> , scores, h);> > System.out.println(> 'The optimal value is : '> +res);> > > }> }> // This code is contributed by vt_m> |
C#
// A simple C# program to find maximum score that> // maximizing player can get.> using> System;> public> class> GFG> {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> static> int> minimax(> int> depth,> int> nodeIndex,> bool> isMax,> > int> []scores,> int> h)> {> > // Terminating condition. i.e leaf node is reached> > if> (depth == h)> > return> scores[nodeIndex];> > // If current move is maximizer, find the maximum attainable> > // value> > if> (isMax)> > return> Math.Max(minimax(depth+1, nodeIndex*2,> false> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> false> , scores, h));> > // Else (If current move is Minimizer), find the minimum> > // attainable value> > else> > return> Math.Min(minimax(depth+1, nodeIndex*2,> true> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> true> , scores, h));> }> // A utility function to find Log n in base 2> static> int> log2(> int> n)> {> > return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> static> public> void> Main ()> {> > // The number of elements in scores must be> > // a power of 2.> > int> []scores = {3, 5, 2, 9, 12, 5, 23, 23};> > int> n = scores.Length;> > int> h = log2(n);> > int> res = minimax(0, 0,> true> , scores, h);> > Console.WriteLine(> 'The optimal value is : '> +res);> > }> }> // This code is contributed by ajit.> |
Python3
# A simple Python3 program to find> # maximum score that> # maximizing player can get> import> math> def> minimax (curDepth, nodeIndex,> > maxTurn, scores,> > targetDepth):> > # base case : targetDepth reached> > if> (curDepth> => => targetDepth):> > return> scores[nodeIndex]> > > if> (maxTurn):> > return> max> (minimax(curDepth> +> 1> , nodeIndex> *> 2> ,> > False> , scores, targetDepth),> > minimax(curDepth> +> 1> , nodeIndex> *> 2> +> 1> ,> > False> , scores, targetDepth))> > > else> :> > return> min> (minimax(curDepth> +> 1> , nodeIndex> *> 2> ,> > True> , scores, targetDepth),> > minimax(curDepth> +> 1> , nodeIndex> *> 2> +> 1> ,> > True> , scores, targetDepth))> > # Driver code> scores> => [> 3> ,> 5> ,> 2> ,> 9> ,> 12> ,> 5> ,> 23> ,> 23> ]> treeDepth> => math.log(> len> (scores),> 2> )> print> (> 'The optimal value is : '> , end> => '')> print> (minimax(> 0> ,> 0> ,> True> , scores, treeDepth))> # This code is contributed> # by rootshadow> |
JavaScript
> // Javascript program to find maximum score that> // maximizing player can get.> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> > function> minimax(depth, nodeIndex, isMax,> > scores, h)> {> > // Terminating condition. i.e leaf node is reached> > if> (depth == h)> > return> scores[nodeIndex];> > > // If current move is maximizer, find the maximum attainable> > // value> > if> (isMax)> > return> Math.max(minimax(depth+1, nodeIndex*2,> false> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> false> , scores, h));> > > // Else (If current move is Minimizer), find the minimum> > // attainable value> > else> > return> Math.min(minimax(depth+1, nodeIndex*2,> true> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> true> , scores, h));> }> > // A utility function to find Log n in base 2> > function> log2(n)> {> return> (n==1)? 0 : 1 + log2(n/2);> }> > // Driver Code> > // The number of elements in scores must be> > // a power of 2.> > let scores = [3, 5, 2, 9, 12, 5, 23, 23];> > let n = scores.length;> > let h = log2(n);> > let res = minimax(0, 0,> true> , scores, h);> > document.write(> 'The optimal value is : '> +res);> > > > |
Wyjście:
The optimal value is: 12
Złożoność czasowa: O(b^d) b jest współczynnikiem rozgałęzienia, a d jest liczbą głębokości lub warstwy wykresu lub drzewa.
Złożoność przestrzeni: O(bd) gdzie b jest współczynnikiem rozgałęzienia na d jest maksymalną głębokością drzewa podobną do DFS.
Ideą tego artykułu jest przedstawienie Minimaxa na prostym przykładzie.
- W powyższym przykładzie gracz ma tylko dwie możliwości wyboru. Ogólnie rzecz biorąc, może być więcej możliwości wyboru. W takim przypadku musimy powtórzyć wszystkie możliwe ruchy i znaleźć maksimum/minimum. Na przykład w Kółko i krzyżyk pierwszy gracz może wykonać 9 możliwych ruchów.
- W powyższym przykładzie przekazywane są nam partytury (liście Drzewa Gry). W przypadku typowej gry musimy wyprowadzić te wartości
Wkrótce będziemy omawiać kółko i krzyżyk z algorytmem Minimax.
Współautorem tego artykułu jest Akshay L. Aradhya.
