- 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 3r & Dwartoś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:
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.