Zrozumienie algorytmu Minmax w AI
![Zrozumienie algorytmu Minmax w AI](https://oen.pl/wp-content/uploads/2023/01/1673954538_1200-630-770x470.png)
Minimaks to algorytm śledzenia wstecznego używany w podejmowaniu decyzji i teorii gier w celu określenia najlepszego ruchu dla gracza, pod warunkiem, że przeciwnik również gra optymalnie. Jest powszechnie stosowany w grach turowych dla dwóch graczy, takich jak Kółko i krzyżyk, Backgammon, Mancala i Chess.
Minimax to reguła decyzyjna stosowana w sztucznej inteligencji, teorii decyzji, teorii gier, statystyce i filozofii, aby zminimalizować potencjalną stratę w najgorszym przypadku (maksymalna strata). Kiedy mamy do czynienia z zyskami, określa się to jako „maximin” – aby zmaksymalizować najniższy zysk. Początkowo opracowany dla kilkuosobowej teorii gier o sumie zerowej, został rozszerzony na bardziej skomplikowane gry i ogólne podejmowanie decyzji w warunkach niepewności.
Teoria gry
Dwóch uczestników Minimax jest określanych jako maksymalizator i minimalizator. Maksymalizujący dąży do osiągnięcia maksymalnego wyniku, podczas gdy minimalizujący dąży do osiągnięcia najniższego wyniku. Wartość towarzyszy każdemu stanowi planszy. Jeśli maksymalizator ma przewagę w określonej sytuacji, wynik planszy będzie zazwyczaj pozytywny. W tym stanie planszy, jeśli minimalizator ma przewagę, zazwyczaj będzie to pewna liczba ujemna.
Pseudo kod
function minimax( node, depth, maximizingPlayer ) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max( value, minimax( child, depth − 1, FALSE ) )
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min( value, minimax( child, depth − 1, TRUE ) )
return value
Operacja
Działanie algorytmu minimax możemy wyjaśnić na przykładzie. Przykład drzewa gry ilustrujący rozgrywkę dwuosobową pokazano poniżej.
- W tym przykładzie jest dwóch graczy o nazwach Maximizer i Minimizer.
- Maximizer będzie dążył do jak najwyższego wyniku, podczas gdy Minimizer będzie dążył do najniższego możliwego wyniku.
- Algorytm ten wykorzystuje DFS. Dlatego, aby dotrzeć do węzłów końcowych w tym drzewie gry, musimy przejść przez wszystkie liście.
- W węźle końcowym dostarczane są wartości końcowe. Dlatego porównamy te wartości i przejdziemy przez drzewo w odwrotnej kolejności, aż dojdziemy do stanu pierwotnego.
Nieruchomości
- Algorytm Min-Max został zakończony. Prawie na pewno znajdzie rozwiązanie (jeśli takie istnieje) w skończonym drzewie poszukiwań.
- Jeśli obaj przeciwnicy grają optymalnie, algorytm Min-Max jest optymalny.
- Złożoność czasowa – ponieważ wykonuje DFS dla drzewa gry, złożoność czasowa algorytmu Min-Max wynosi O (bm), gdzie b to współczynnik drzewa rozgałęzień gry, a m to maksymalna głębokość drzewa.
- Złożoność przestrzenna — Algorytm Mini-max ma taką samą złożoność przestrzenną jak DFS, czyli O. (bm).
Wniosek
Podejmowanie decyzji Minimax jest nieprobabilistyczne: w przeciwieństwie do decyzji opartych na oczekiwanej wartości lub użyteczności, nie przyjmuje żadnych założeń dotyczących prawdopodobieństwa alternatywnych wyników, zamiast tego polega na analizie scenariuszy możliwych wyników. W przeciwieństwie do tych innych podejść do wyboru, jest zatem odporny na zmiany założeń. Inne adaptacje tej nieprobabilistycznej metody obejmują minimaksowy żal i teorię podejmowania decyzji z przerwami w informacjach.
Co więcej, podstawową wadą algorytmu minimax jest to, że wydłuża się on podczas grania w złożone gry, takie jak szachy, go i tak dalej. Ten styl gry charakteryzuje się wysokim współczynnikiem rozgałęzień, dając graczowi wiele opcji. Wadę algorytmu minimax można przezwyciężyć przez przycinanie alfa-beta.