Algorytm Min Max w AI: komponenty, właściwości, zalety i ograniczenia

Algorytm min max w sztucznej inteligencji, popularnie znany jako minimax, jest algorytmem cofania stosowanym w podejmowaniu decyzji, teorii gier i sztucznej inteligencji (AI). Służy do znalezienia optymalnego ruchu dla gracza, zakładając, że przeciwnik również gra optymalnie. Popularne dwuosobowe gry komputerowe lub gry online, takie jak szachy, kółko i krzyżyk, warcaby, go itp., używają tego algorytmu.

Algorytm wycofywania jest używany do znalezienia rozwiązania problemów obliczeniowych w taki sposób, że kandydat jest stopniowo budowany w kierunku rozwiązania, krok po kroku. A kandydat, który nie zdoła uzupełnić rozwiązania, zostaje natychmiast porzucony.

Jak to działa?

W algorytmie min max w AI jest dwóch graczy, Maximiser i Minimiser. Obaj gracze grają w tę grę, gdy jeden próbuje uzyskać jak najwyższy wynik lub maksymalną korzyść, podczas gdy przeciwnik stara się uzyskać najniższy wynik lub minimalną korzyść.

Każda plansza ma przypisany wynik oceny, więc Maksymalizator wybierze zmaksymalizowaną wartość, a Minimalizator wybierze zminimalizowaną wartość za pomocą ruchów kontrujących. Jeśli maksymalizator ma przewagę, wynik tablicy będzie wartością dodatnią, a jeśli minimalizator ma przewagę, wynik tablicy będzie wartością ujemną.

Opiera się to na koncepcji gry o sumie zerowej, w której całkowity wynik użyteczności jest dzielony między dwóch graczy. Tak więc wzrost wyniku jednego gracza prowadzi do spadku wyniku przeciwnika, co powoduje, że całkowity wynik zawsze wynosi zero. Tak więc, aby jeden gracz wygrał, drugi musi przegrać.

Dołącz do kursów Certyfikacji i AI uczenia maszynowego online z najlepszych światowych uniwersytetów. Zdobywaj tytuły Masters, Executive PGP lub ACP, aby przyspieszyć swoją karierę.

Podział algorytmu min max w AI

Pełne drzewo gry jest eksplorowane za pomocą algorytmu wyszukiwania w głąb w algorytmie min max w sztucznej inteligencji. Przechodzi całkowicie w dół do końcowego węzła drzewa, a następnie cofa się przez drzewo.

Celem jest znalezienie najlepszego możliwego ruchu dla gracza. Można to zrobić, wybierając węzeł z najlepszym wynikiem oceny. Najlepszy wybór zostanie dokonany po ocenie wszystkich potencjalnych ruchów przeciwnika. Algorytm wybiega w przyszłość na wszystkie możliwe wartości do końca i podejmuje decyzję za gracza.

Źródło

Powyższe drzewo gry to zagnieżdżona struktura danych, która służy do oceny ruchów. Tutaj węzeł główny to poziom 0, który rozgałęzia się na poziom 1 lub węzły nadrzędne, które dalej rozgałęziają się na poziom 2 lub węzły podrzędne. Rozgałęzienie może trwać na wielu poziomach, mając potencjał nieskończonych poziomów. Poziom 0 jest jak obecny stan planszy, podczas gdy poziom 1 to wszystkie możliwe stany plansz w zależności od następnego ruchu.

Tak więc, jeśli Gracz 2 wykonał ruch, możemy założyć, że węzłem głównym jest aktualny stan planszy, oczekujący na ruch Gracza 1. Węzły poziomu 1 zawierają wszystkie możliwe ruchy gracza 1, a węzły poziomu 2 zawierają wszystkie możliwe ruchy gracza 2 w oparciu o każdy możliwy ruch gracza 1.

Rozważmy przykład, w którym istnieją cztery stany końcowe, a ścieżka do nich prowadzi od korzenia do czterech liści drzewa. Wartości czterech listków to 3, 6 po lewej i 4, 7 po prawej. Nadchodzi kolej Maksymalizatora/Gracza 1 na wykonanie ruchu. Aby przejść przez algorytm, należy poczynić założenia dla każdego ruchu.

Jeśli Gracz 1 zdecyduje się iść w lewo, Minimiser/Gracz 2 musi wybrać najmniej od 3 do 6, więc wybraliby 3. Natomiast jeśli Gracz 1 wybierze prawo, Gracz 2 wybierze 4, czyli minimum. z dwóch wartości, 4 i 7. Tak więc poziom 1 ma teraz wartości 3 i 4.

Ponieważ jest to tura Gracza 1/Maximisera, musi on wybrać maksymalnie 1 poziom węzłów. W ten sposób wybiorą 3. Wtedy optymalnym wyborem jest pójście w lewo.

Kroki algorytmu min max w AI można określić w następujący sposób:

1. Stwórz całe drzewo gry.
2. Oceń wyniki dla węzłów liści na podstawie funkcji oceny.
3. Cofnij się od liścia do węzłów głównych:

W przypadku Maksymalizatora wybierz węzeł z maksymalnym wynikiem.

W przypadku Minimizera wybierz węzeł z minimalnym wynikiem.

4. W węźle głównym wybierz węzeł z maksymalną wartością i wybierz odpowiedni ruch.

Przeczytaj także: Pomysły na projekty uczenia maszynowego

Własności algorytmu min max w AI

• Algorytm jest kompletny, co oznacza, że ​​w skończonym drzewie poszukiwań na pewno zostanie znalezione rozwiązanie.
• Optymalnie jest, jeśli obaj gracze grają optymalnie.
• Ze względu na Depth-First Search (DFS) dla drzewa gry, złożoność czasowa algorytmu wynosi O(b m ), gdzie b jest współczynnikiem rozgałęzienia, a m jest maksymalną głębokością drzewa.
• Podobnie jak DFS, złożoność przestrzenna tego algorytmu wynosi O(bm).

Zalety

• Przeprowadzana jest dokładna ocena przestrzeni poszukiwań.
• Podejmowanie decyzji w AI jest łatwo możliwe.
• Za pomocą tego algorytmu powstają nowe i inteligentne maszyny.

Ograniczenia

• Ze względu na duży czynnik rozgałęzień proces dochodzenia do celu jest wolniejszy.
• Ocena i wyszukiwanie wszystkich możliwych węzłów i gałęzi obniża wydajność i wydajność silnika.
• Obaj gracze mają zbyt wiele możliwości wyboru.
• Jeśli istnieje ograniczenie czasu i przestrzeni, nie jest możliwe zbadanie całego drzewa.

Ale dzięki przycinaniu Alpha-Beta algorytm można ulepszyć.

Wniosek

W tym artykule wyjaśniono wszystkie aspekty algorytmu min-max w AI. W pierwszej kolejności przedstawiono wprowadzenie do teorii z przykładami jej zastosowania, po czym następuje opis działania algorytmu w grze.

Algorytm jest podzielony, aby wyjaśnić, w jaki sposób podejmowana jest decyzja o wykonaniu optymalnego ruchu na podstawie ruchów i kontrataków graczy. Następnie wymienione są właściwości algorytmu. Na koniec przedstawiono zalety i wady algorytmu.

Jeśli chcesz dowiedzieć się więcej o uczeniu maszynowym, zapoznaj się z programem IIIT-B i upGrad Executive PG w zakresie uczenia maszynowego i sztucznej inteligencji , który jest przeznaczony dla pracujących profesjonalistów i oferuje ponad 450 godzin rygorystycznych szkoleń, ponad 30 studiów przypadków i zadań, IIIT Status -B Alumni, ponad 5 praktycznych praktycznych projektów zwieńczenia i pomoc w pracy z najlepszymi firmami.