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.