algorytm Minimax z przycinaniem alfa-beta

od czasu pojawienia się sztucznej inteligencji (AI) gra jest jednym z najciekawszych zastosowań sztucznej inteligencji.

pierwsze programy szachowe zostały napisane przez Claude ’ a Shannona i Alana Turinga w 1950 roku, niemal natychmiast po tym, jak komputery stały się programowalne.

gry takie jak szachy, kółko i krzyżyk są interesujące, ponieważ oferują czystą abstrakcję rywalizacji między obiema armiami.

to właśnie ta abstrakcja sprawia, że gra jest atrakcyjnym obszarem dla badań nad sztuczną inteligencją.

w tym artykule omówimy podstawy algorytmu Minimax wraz z jego funkcjonowaniem.

przyjrzymy się również optymalizacji algorytmu minimax, przycinania alfa-beta.

co to jest algorytm Minimax?

Minimax jest rekurencyjnym algorytmem, który służy do wyboru optymalnego ruchu dla gracza, zakładając, że drugi gracz również gra optymalnie.

jest używany w grach takich jak Kółko i krzyżyk, go, szachy, Isola, warcaby i wiele innych gier dla dwóch graczy.

takie gry nazywane są grami doskonałej informacji, ponieważ można zobaczyć wszystkie możliwe ruchy danej gry.

mogą być Gry dla dwóch graczy, które nie są doskonałej informacji, takich jak Scrabble, ponieważ nie można przewidzieć ruchu przeciwnika.

jest to podobne do tego, jak myślimy, gdy gramy w grę: „jeśli wykonam ten ruch, mój przeciwnik może wykonać tylko te ruchy” i tak dalej.

Minimax jest tak nazywany, ponieważ pomaga w minimalizacji straty, gdy drugi gracz wybiera strategię o maksymalnej stracie.

Terminologia

• drzewo gry: jest to struktura w formie drzewa składająca się ze wszystkich możliwych ruchów, które pozwalają na przejście ze stanu gry do następnego stanu.

grę można zdefiniować jako problem z wyszukiwaniem z następującymi komponentami:

• stan początkowy: zawiera pozycję planszy i pokazuje, czyj to ruch.
• funkcja następcy: Określa, jakie są legalne ruchy gracza.
• Stan terminala: jest to pozycja planszy, gdy gra się kończy.
• funkcja użytkowa: jest to funkcja, która przypisuje wartość liczbową do wyniku gry. Na przykład w szachach lub w kółko i krzyżyk (Tic-Tac-toe) wynikiem jest wygrana, przegrana lub remis, które mogą być reprezentowane odpowiednio przez wartości +1, -1 lub 0. Istnieją gry, które mają znacznie większy zakres możliwych wyników; na przykład narzędzia w backgammonie wahają się od +192 do -192. Funkcję użyteczności można również nazwać funkcją wypłaty.

jak działa algorytm?

w grze bierze udział dwóch graczy, min i MAX. Gracz MAX stara się uzyskać najwyższy możliwy wynik, a MIN stara się uzyskać najniższy możliwy wynik, tj. MIN i MAX próbują działać przeciwstawnie do siebie.

ogólny proces algorytmu Minimax jest następujący:

Krok 1: Najpierw Wygeneruj całe drzewo gry, zaczynając od bieżącej pozycji gry aż do Stanów terminalu. Tak wygląda drzewo gry w kółko i krzyżyk.

zrozummy zdefiniowaną terminologię w kategoriach powyższego diagramu.

1. stan początkowy jest pierwszą warstwą, która określa, że plansza jest pusta.
2. funkcja następcy wyświetla wszystkie możliwe ruchy następcy. Jest zdefiniowany dla wszystkich warstw w drzewie.
3. Stan terminalu jest ostatnią warstwą drzewa, która pokazuje stan końcowy, tj. czy gracz MAX wygrywa, przegrywa lub więzi z przeciwnikiem.
4. narzędzia w tym przypadku dla Stanów terminala są 1, 0 i -1, jak omówiono wcześniej, i mogą być użyte do określenia narzędzi innych węzłów, jak również.

Krok 2: zastosuj funkcję narzędzia, aby uzyskać wartości użytkowe dla wszystkich stanów terminala.
Krok 3: Określ narzędzia wyższych węzłów za pomocą narzędzi węzłów terminalowych. Na przykład na poniższym diagramie mamy narzędzia dla Stanów terminali zapisane w kwadratach.

obliczmy użyteczność dla lewego węzła (czerwonego) warstwy nad terminalem. Ponieważ jest to ruch gracza MIN, wybierzemy minimum wszystkich narzędzi. W tym przypadku musimy obliczyć MIN{3, 5, 10}, co jak wiemy jest z pewnością 3. Więc użyteczność dla czerwonego węzła to 3.

podobnie, dla zielonego węzła w tej samej warstwie, będziemy musieli obliczyć MIN{2,2} czyli 2.

Krok 4: Oblicz wartości użytkowe za pomocą liści, biorąc pod uwagę jedną warstwę na raz, aż do korzenia drzewa.
Krok 5: ostatecznie wszystkie wartości kopii zapasowej docierają do korzenia drzewa, czyli najwyższego punktu. W tym momencie MAX musi wybrać najwyższą wartość.

w naszym przykładzie mamy tylko 3 warstwy, więc natychmiast dotarliśmy do korzenia, ale w rzeczywistych grach będzie o wiele więcej warstw i węzłów. Więc musimy obliczyć MAX{3,2} czyli 3.

dlatego najlepszym ruchem otwarcia dla MAX jest lewy węzeł(lub czerwony). Ruch ten nazywany jest decyzją minimax, ponieważ maksymalizuje użyteczność, przyjmując założenie, że przeciwnik również gra optymalnie, aby go zminimalizować.

Podsumowując,

Minimax = MAX{MIN{3,5,10}, MIN{2,2}}
= MAX{3,2}
= 3

Psuedocode:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

Optymalizacja

drzewa gier są na ogół bardzo czasochłonne w budowie, a tylko w przypadku prostych gier można je wygenerować w krótkim czasie.

jeśli istnieją\ (B\) ruchy prawne, tzn.,\ (b\) węzły w każdym punkcie i maksymalna głębokość drzewa to \(m\), złożoność czasowa algorytmu minimax jest rzędu \(b^M(O (B^m))\).

aby ograniczyć tę sytuację, istnieje kilka optymalizacji, które można dodać do algorytmu.

na szczęście jest realne, aby znaleźć rzeczywistą decyzję minimax, nawet nie patrząc na każdy węzeł drzewa gry. Dlatego eliminujemy węzły z drzewa bez analizy, a proces ten nazywa się przycinaniem.

przycinanie alfa-beta

metoda, którą zamierzamy przyjrzeć się w tym artykule, nazywa się przycinanie alfa-beta.

jeśli zastosujemy przycinanie Alfa-beta do standardowego algorytmu minimax, zwróci on ten sam ruch co standardowy, ale usunie (ścina) wszystkie węzły, które prawdopodobnie nie mają wpływu na ostateczną decyzję.

najpierw zrozumiemy intuicję, a potem sformalizujemy algorytm. Załóżmy, że mamy następujące drzewo gry:

w tym przypadku,
Minimax Decision = MAX{MIN{3,5,10}, MIN{2,A,b}, MIN{2,7,3}}
= MAX{3, c,2}
= 3

zdziwiłbyś się!

jak możemy obliczyć maksimum z brakującą wartością? Oto sztuczka. MIN{2, A, b} byłby z pewnością mniejszy lub równy 2, tzn. c<=2 i stąd MAX{3,c, 2} musi być równy 3.

teraz pytanie, czy naprawdę musimy obliczyć c? Oczywiście, że nie.

mogliśmy dojść do wniosku bez patrzenia na te węzły. I tu pojawia się przycinanie alfa-beta.

kilka definicji:

Alpha: jest to najlepszy wybór do tej pory dla gracza MAX. Chcemy uzyskać najwyższą możliwą wartość tutaj.
Beta: Jest to najlepszy wybór do tej pory dla MIN i musi być najniższą możliwą wartością.

uwaga: każdy węzeł musi śledzić swoje wartości alfa i beta. Alfa może być aktualizowana tylko wtedy, gdy nadchodzi kolej Maxa, a beta może być aktualizowana tylko wtedy, gdy jest szansa MIN.

jak działa przycinanie alfa-beta?

1. Inicjalizuj alpha = -infinity i beta = infinity jako najgorsze możliwe przypadki. Warunkiem przycinania węzła jest, gdy Alfa staje się większa lub równa beta.
2. zacznij od przypisania początkowych wartości alfa i beta do root, a ponieważ alfa jest mniejsza niż beta, nie przycinamy jej.
3. przenieś te wartości alfa i beta do węzła podrzędnego po lewej stronie. A teraz od wartości użytkowej stanu końcowego, zaktualizujemy wartości alpha I be, więc nie musimy aktualizować wartości beta. Ponownie, nie przycinamy, ponieważ warunek pozostaje taki sam. Podobnie, trzeci węzeł potomny również. A następnie cofając się do pierwiastka, ustawiamy alpha=3, ponieważ jest to minimalna wartość, którą alfa może mieć.
   
4. teraz, alfa=3 i beta=nieskończoność w korzeniu. Więc nie przycinamy. Przenosząc to do węzła centralnego i obliczając MIN{2, nieskończoność}, otrzymujemy alpha=3 i beta=2.
5. przycina drugi i trzeci węzeł potomny, ponieważ alfa jest teraz większa niż beta.
6. alfa u korzenia pozostaje 3, ponieważ jest większa od 2. Przenosząc to do prawego węzła potomnego, Oblicz MIN{nieskończoność,2}=2. Aktualizacja beta do 2 i Alfa pozostaje 3.
7. przycina drugi i trzeci węzeł potomny, ponieważ alfa jest teraz większa niż beta.
8. stąd otrzymujemy 3, 2, 2 odpowiednio w lewym, środkowym i prawym WĘZLE MIN. I obliczając MAX{3,2,2}, otrzymujemy 3. Dlatego nawet nie patrząc na cztery liście mogliśmy poprawnie znaleźć decyzję minimax.

Pseudokod (źródło: kurs NPTEL):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

wnioski

gry są bardzo atrakcyjne, a pisanie programów do gry jest być może jeszcze bardziej ekscytujące. Czym wyścigi Grand Prix są dla przemysłu samochodowego, gra jest dla AI.

tak jak nie spodziewalibyśmy się, że samochód wyścigowy będzie jeździł idealnie po wyboistej drodze, nie powinniśmy oczekiwać, że algorytmy gry będą idealne w każdej sytuacji.

tak samo jest z algorytmem minimax. To nie może być najlepsze rozwiązanie dla wszelkiego rodzaju gier komputerowych, które muszą mieć AI.

ale biorąc pod uwagę dobrą implementację, może stworzyć twardego konkurenta.