• Algorytm mini-max to algorytm rekurencyjny lub cofający się, stosowany w podejmowaniu decyzji i teorii gier. Zapewnia optymalny ruch dla gracza, przy założeniu, że przeciwnik również gra optymalnie.
• Algorytm Mini-Max wykorzystuje rekurencję do przeszukiwania drzewa gry.
• Algorytm Min-Max jest najczęściej używany do grania w gry w AI. Takie jak szachy, warcaby, kółko i krzyżyk, go i różne gry holownicze. Algorytm ten oblicza decyzję minimaksową dla bieżącego stanu.
• W tym algorytmie w grę gra dwóch graczy, jeden nazywa się MAX, a drugi MIN.
• Obaj gracze walczą tak, aby przeciwnik uzyskał minimalną korzyść, podczas gdy on uzyskał maksymalną korzyść.
• Obaj Gracze są wobec siebie przeciwnikami, przy czym MAX wybierze wartość maksymalną, a MIN wartość minimalną.
• Algorytm minimax wykonuje algorytm przeszukiwania w głąb w celu eksploracji całego drzewa gier.
• Algorytm minimax przechodzi aż do końcowego węzła drzewa, a następnie cofa drzewo w drodze rekurencji.

Pseudokod dla algorytmu MinMax:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

Początkowe połączenie:

Minimax(węzeł, 3, prawda)

Działanie algorytmu Min-Max:

• Działanie algorytmu minimax można łatwo opisać na przykładzie. Poniżej wzięliśmy przykład drzewa gry reprezentującego grę dla dwóch graczy.
• W tym przykładzie jest dwóch graczy, jeden nazywa się Maximizer, a drugi Minimizer.
• Maximizer spróbuje uzyskać maksymalny możliwy wynik, a Minimizer spróbuje uzyskać minimalny możliwy wynik.
• Algorytm ten stosuje DFS, więc w tym drzewie gry musimy przejść całą drogę przez liście, aby dotrzeć do węzłów końcowych.
• W węźle końcowym podane są wartości końcowe, więc porównamy te wartości i cofniemy się po drzewie, aż do wystąpienia stanu początkowego. Poniżej znajdują się główne kroki potrzebne do rozwiązania drzewa gry dla dwóch graczy:

Krok 1: W pierwszym kroku algorytm generuje całe drzewo gry i stosuje funkcję użyteczności w celu uzyskania wartości użyteczności dla stanów terminala. Na poniższym diagramie drzewa załóżmy, że A jest stanem początkowym drzewa. Załóżmy, że maksymalizator wykonuje pierwszą turę, która ma najgorszą wartość początkową = - nieskończoność, a minimalizator wykonuje następną turę, która ma najgorszą wartość początkową = + nieskończoność.

Krok 2: Teraz najpierw znajdujemy wartość użyteczności dla Maximizera, jej wartość początkowa wynosi -∞, więc porównamy każdą wartość w stanie końcowym z początkową wartością Maximizera i określimy wartości wyższych węzłów. Znajdzie maksimum spośród wszystkich.

• Dla węzła D max(-1,- -∞) => max(-1,4)= 4
• Dla węzła E max(2, -∞) => max(2, 6)= 6
• Dla węzła F max(-3, -∞) => max(-3,-5) = -3
• Dla węzła G max(0, -∞) = max(0, 7) = 7

Krok 3: W następnym kroku kolej na minimalizator, więc porówna on wartość wszystkich węzłów z +∞ i znajdzie 3^{r & D}wartości węzłów warstwy.

• Dla węzła B= min(4,6) = 4
• Dla węzła C= min (-3, 7) = -3

Krok 4: Teraz kolej na Maximizer, który ponownie wybierze maksymalną wartość wszystkich węzłów i znajdzie maksymalną wartość dla węzła głównego. W tym drzewie gry są tylko 4 warstwy, stąd od razu docieramy do węzła głównego, ale w prawdziwych grach będzie ich więcej niż 4.

• Dla węzła A max(4, -3)= 4

Tak wyglądał cały przebieg gry minimax dla dwóch graczy.

Właściwości algorytmu Mini-Max:

Kompletny-Algorytm Min-Max został ukończony. Na pewno znajdzie rozwiązanie (jeśli istnieje) w skończonym drzewie wyszukiwania.Optymalny-Algorytm Min-Max jest optymalny, jeśli obaj przeciwnicy grają optymalnie.Złożoność czasowa-Ponieważ wykonuje DFS dla drzewa gier, tak złożoność czasowa algorytmu Min-Max wynosi O(ur^M) , gdzie b jest współczynnikiem rozgałęzienia drzewa gry, a m jest maksymalną głębokością drzewa.Złożoność przestrzeniZłożoność przestrzenna algorytmu Mini-max jest również podobna do DFS O .

Ograniczenia algorytmu minimax:

Główną wadą algorytmu minimax jest to, że działa bardzo wolno w przypadku złożonych gier, takich jak szachy, go itp. W tego typu grach występuje ogromny współczynnik rozgałęzienia, a gracz ma wiele możliwości wyboru. To ograniczenie algorytmu minimax można ulepszyć przycinanie alfa-beta o czym pisaliśmy w następnym temacie.