przycinanie Alfa beta jest techniką optymalizacji dla algorytmu minimax. W trakcie tego bloga omówimy, co oznacza przycinanie alfa beta, omówimy algorytm minimax, Zasady znajdowania dobrego porządku i wiele więcej.
- wprowadzenie
- algorytm Minimax
- kluczowe punkty w przycinaniu alfa-beta
- praca z przycinaniem alfa-beta
- Przenieś kolejność w przycinaniu
- zasady dobrego zamawiania
- kody w Pythonie
wprowadzenie
słowo „przycinanie” oznacza ścinanie gałęzi i liści. W naukach o danych przycinanie jest często używanym terminem, który odnosi się do przycinania po i przed przycinaniem w drzewach decyzyjnych i lesie losowym. Przycinanie alfa-beta to nic innego jak przycinanie bezużytecznych gałęzi w drzewach decyzyjnych. Ten algorytm przycinania alfa-beta został odkryty niezależnie przez naukowców w 1900 roku.
przycinanie Alfa-beta jest techniką optymalizacji dla algorytmu minimax, który jest omówiony w następnej sekcji. Potrzeba przycinania wynikała z faktu, że w niektórych przypadkach drzewa decyzyjne stają się bardzo złożone. W tym drzewie niektóre bezużyteczne gałęzie zwiększają złożoność modelu. Aby tego uniknąć, Alpha-Beta przycinanie przychodzi grać tak, że komputer nie musi patrzeć na całe drzewo. Te nietypowe węzły powodują, że algorytm zwalnia. Stąd przez usunięcie tych węzłów algorytm staje się szybki.
poznaj algorytm*.
algorytm Minimax
Minimax jest klasyczną techniką wyszukiwania głębi dla sekwencyjnej gry dla dwóch graczy. Dwóch graczy nazywa się MAX I MIN. Algorytm minimax jest przeznaczony do znalezienia optymalnego ruchu dla Maxa, gracza na węźle głównym. Drzewo wyszukiwania jest tworzone przez rekurencyjnie rozszerzające wszystkie węzły z korzenia w pierwszy sposób, aż do końca gry lub do osiągnięcia maksymalnej głębokości wyszukiwania. Zbadajmy ten algorytm szczegółowo.
jak już wspomniano, w grze jest dwóch graczy, mianowicie Max I Min. Max gra pierwszy krok. Zadaniem Maxa jest maksymalizacja nagrody, podczas gdy zadaniem Min jest zminimalizowanie nagrody Maxa, zwiększając jednocześnie własną nagrodę. Powiedzmy, że Max może podjąć działania a, b lub C. który z nich da Maxowi najlepszą nagrodę po zakończeniu gry? Aby odpowiedzieć na to pytanie, musimy zbadać drzewo gry na dostateczną głębokość i założyć, że Min gra optymalnie, aby zminimalizować nagrodę Max.
oto przykład. Cztery monety są z rzędu i każdy gracz może podnieść jedną monetę lub dwie monety w swojej turze. Wygrywa gracz, który podniesie ostatnią monetę. Zakładając, że Max zagra jako pierwszy, jaki ruch powinien wykonać Max, aby wygrać?
jeśli Max wybiera dwie monety, to zostają tylko dwie monety, A Min może wybrać dwie monety i wygrać. W ten sposób zdobycie 1 monety zmaksymalizuje maksymalną nagrodę.
jak mogłeś zauważyć, węzły drzewa na poniższym rysunku mają zapisane na nich wartości, są one nazywane wartością minimax. Wartość minimax węzła jest użytecznością węzła, jeśli jest węzłem terminalowym.
jeśli węzeł jest nieterminalnym węzłem Max, wartość minimax węzła jest maksymalną z wartości minimax wszystkich następców węzła. Z drugiej strony, jeśli węzeł nie jest terminalnym węzłem Min, wartość minimax węzła jest minimum wartości minimax wszystkich następców węzła.
teraz omówimy ideę przycinania alfa beta. Jeśli zastosujemy przycinanie Alfa-beta do standardowego algorytmu minimax, daje to taką samą decyzję jak algorytm standardowy, ale przycina lub wycina węzły, które są nietypowe w drzewie decyzyjnym, tj. które nie mają wpływu na ostateczną decyzję podjętą przez algorytm. Pomoże to uniknąć złożoności interpretacji złożonych drzew.
zobacz jak działa algorytm KNN.
teraz omówmy intuicję stojącą za tą techniką. Spróbujmy znaleźć decyzję minimax w poniższym drzewie :
w tym przypadku,
Minimax = MAX {MIN {3, 5, 10}, MIN {2, A, b}, MIN {2, 7, 3}}
= MAX {3, c, 2} = 3
tutaj w powyższym wyniku musisz mieć wątpliwości w swoim umyśle, że jak możemy znaleźć maksimum z brakującej wartości. Tak więc, oto rozwiązanie Twojej wątpliwości również:
w drugim węźle wybieramy minimalną wartość jako C, która jest mniejsza lub równa 2, czyli c < = 2. Teraz, jeśli c < = 3 i musimy wybrać max 3, c, 2 maksymalna wartość będzie 3.
podjęliśmy decyzję bez patrzenia na te węzły. I tu pojawia się przycinanie alfa-beta.
kluczowe punkty w przycinaniu alfa-beta
- Alpha: Alpha jest najlepszym wyborem lub najwyższą wartością, jaką znaleźliśmy w dowolnej instancji wzdłuż ścieżki Maximizera. Początkową wartością alfa jest -∞.
- Beta: Beta jest najlepszym wyborem lub najniższą wartością, jaką znaleźliśmy w dowolnej instancji na ścieżce Minimizera. Wartość początkowa dla Alfy to+∞.
- warunkiem przycinania Alfa-beta jest to, że α > = β.
- 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.
- MAX zaktualizuje tylko wartości alfa, a MIN gracz zaktualizuje tylko wartości beta.
- wartości węzłów będą przekazywane do górnych węzłów zamiast wartości alfa i beta podczas przechodzenia na odwrotność drzewa.
- wartości alfa i Beta są przekazywane tylko do węzłów potomnych.
praca przycinania alfa-beta
- zaczniemy od pierwszego ruchu. Początkowo zdefiniujemy wartości alfa i beta jako najgorszy przypadek, tj. α = – ∞ i β=+∞. Przycinamy węzeł tylko wtedy, gdy Alfa stanie się większa lub równa beta.
2. Ponieważ początkowa wartość alfa jest mniejsza niż beta, więc nie przycinaliśmy jej. Teraz kolej na MAXA. W węźle D zostanie obliczona wartość alfa. Wartość alfa w węźle D będzie wynosić max (2, 3). Zatem wartość alfa w węźle D będzie równa 3.
3. Teraz następny ruch będzie na węźle B i jego kolej na MIN. Tak więc, w węźle B, wartość alfa beta będzie min (3,∞). Tak więc, w węźle B wartości będą alfa= -∞, a beta będzie 3.
w następnym kroku algorytmy przechodzą przez następny następca węzła B, którym jest węzeł E, a wartości α= – ∞ i β= 3 również zostaną przekazane.
4. Teraz kolej na MAXA. Więc na węźle E będziemy szukać Maxa. Aktualna wartość alfa w E wynosi – ∞ I będzie porównywana z 5. Więc MAX ( – ∞ , 5) będzie 5. Więc, w węźle E, Alfa = 5, Beta = 5. Teraz, jak widzimy, alfa jest większa niż beta, która spełnia warunek przycinania, więc możemy przycinać prawego następcę węzła E i algorytm nie będzie przechodził, a wartość w węźle E będzie wynosić 5.
6. W następnym kroku algorytm ponownie przechodzi do węzła A z węzła B. na węźle a Alfa zostanie zmieniona na wartość maksymalną jako MAX ( – ∞ , 3). Tak więc teraz wartości alfa i beta w węźle A będą odpowiednio (3,+∞) i zostaną przeniesione do węzła C. te same wartości zostaną przeniesione do węzła F.
7. W węźle F wartość alfa będzie porównywana do lewej gałęzi, która wynosi 0. Tak więc, MAX (0, 3) będzie 3, a następnie w porównaniu z prawym dzieckiem, które jest 1, A MAX (3,1) = 3 nadal α pozostaje 3, ale wartość węzła F będzie 1.
8. Teraz węzeł F zwróci wartość węzła 1 do C i będzie porównywany z wartością beta w C. teraz jego kolej na MIN. Więc MIN ( + ∞ , 1) będzie 1. Teraz w węźle C, α= 3 i β = 1, A alfa jest większa niż beta, która ponownie spełnia warunek przycinania. Tak więc, kolejny następca node C tj. G zostanie przycięte, a algorytm nie obliczył całego podzbioru G.
teraz C zwróci wartość węzła do A, A najlepszą wartością a będzie MAX (1, 3) będzie 3.
powyżej reprezentowane drzewo jest ostatnim drzewem, które pokazuje węzły, które są obliczane i węzły, które nie są obliczane. Dla tego przykładu optymalną wartością maksymalizatora będzie 3.
spójrz na otwarte Biblioteki Pythona.
Przenieś kolejność przycinania
skuteczność przycinania alfa – beta opiera się na kolejności, w jakiej badany jest węzeł. Kolejność ruchów odgrywa ważną rolę w przycinaniu alfa beta.
w przycinaniu alfa beta istnieją dwa rodzaje porządkowania ruchu:
- najgorsza kolejność: w niektórych przypadkach przycinania alfa beta żaden z węzłów nie jest przycinany przez algorytm i działa jak standardowy algorytm minimax. To zużywa dużo czasu, ponieważ ze względu na czynniki alfa i beta, a także nie daje żadnych skutecznych wyników. To się nazywa najgorsza kolejność przycinania. W tym przypadku najlepszy ruch występuje po prawej stronie drzewa.
- idealne uporządkowanie: w niektórych przypadkach alpha beta przycinanie wielu węzłów przycinanych przez algorytm. To się nazywa idealne uporządkowanie w przycinaniu. W tym przypadku najlepszy ruch występuje po lewej stronie drzewa. Stosujemy DFS, dlatego najpierw przeszukujemy po lewej stronie drzewa i zagłębiamy się dwa razy w algorytm minimax w tym samym czasie.
Zasady, aby znaleźć dobrą kolejność
- najlepszy ruch dzieje się od najniższego węzła
- użyj wiedzy o domenie, znajdując najlepszy ruch
- kolejność węzłów powinna być taka, aby najlepsze węzły były obliczane jako pierwsze
sprawdź ten samouczek Pythona dla początkujących
kody w Pythonie
class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target
w tym dokumencie widzieliśmy ważny element teorii gier. Chociaż wydajność algorytmu minimax jest dobra, ale algorytm jest powolny. Aby to przyspieszyć, używamy algorytmu przycinania alfa-beta, który usunie nietypowe węzły z drzewa decyzyjnego, aby poprawić wydajność. Obecnie powszechnie stosowany jest szybki i dobrze wykonany algorytm.
Sprawdź te kursy sztucznej inteligencji i uczenia maszynowego od doskonałej nauki do podnoszenia umiejętności w dziedzinie i opanowania przycinania Alfa Beta i innych podobnych algorytmów.
Czytaj dalej
- a * algorytm wyszukiwania w sztucznej inteligencji (AI)
- algorytm drzewa decyzyjnego objaśniony przykładami
- najlepszy pierwszy algorytm wyszukiwania w sztucznej inteligencji | koncepcja, implementacja, Zalety, Wady
- co to jest sztuczna inteligencja? Jak działa AI, rodzaje i Przyszłość it?