Alfa Beta Prořezávání v AI

Alfa-beta prořezávání je optimalizační technika pro minimax algoritmus. V průběhu tohoto blogu, budeme diskutovat o tom, co znamená prořezávání alfa beta, budeme diskutovat o algoritmu minimax, pravidla pro nalezení dobrého uspořádání, a více.

1. Úvod
2. Minimax algoritmus
3. Klíčové body v Alfa-beta Prořezávání
4. Pracovní Alfa-beta Prořezávání
5. Přesunout Objednání v Prořezávání
6. Pravidla, jak najít Dobré uspořádání
7. Kódy v Pythonu

Úvod

slovo ‚prořezávání‘ znamená kácení větví a listí. V datové vědě je prořezávání velmi používaným termínem, který odkazuje na post a pre-prořezávání v rozhodovacích stromech a náhodném lese. Alfa-beta prořezávání není nic jiného než prořezávání zbytečných větví ve stromech. Tento alfa-beta prořezávání algoritmus byl objeven nezávisle na sobě vědci v 1900s.

Alfa-beta prořezávání je optimalizační technika pro minimax algoritmus, který je popsán v další části. Potřeba prořezávání vycházela ze skutečnosti, že v některých případech se rozhodovací stromy stávají velmi složitými. V tomto stromu některé zbytečné větve zvyšují složitost modelu. Aby se tomu zabránilo, hraje se alfa-Beta prořezávání, takže se počítač nemusí dívat na celý strom. Tyto neobvyklé uzly zpomalují algoritmus. Proto odstraněním těchto uzlů algoritmus se stává rychle.

další informace o * algoritmu.

Minimax algoritmus

Minimax je klasická hloubková vyhledávací technika pro sekvenční hru pro dva hráče. Oba hráči se nazývají MAX A MIN. Algoritmus minimax je určen pro nalezení optimálního tahu pro MAX, přehrávač v kořenovém uzlu. Vyhledávací strom je vytvořen rekurzivním rozšiřováním všech uzlů z kořene způsobem první hloubky až do konce hry nebo do maximální hloubky vyhledávání. Podívejme se podrobně na tento algoritmus.

jak již bylo zmíněno, ve hře jsou dva hráči, viz-Max a Min. Max hraje první krok. Maxovým úkolem je maximalizovat svou odměnu, zatímco minovým úkolem je minimalizovat Maxovu odměnu a současně zvýšit svou vlastní odměnu. Řekněme, že Max může podniknout kroky a, b nebo c. který z nich dá Maxovi nejlepší odměnu, když hra skončí? Odpovědět na tuto otázku, musíme prozkoumat herní strom do dostatečné hloubky a předpokládat, že Min hraje optimálně pro minimalizaci odměnu Max.

zde je příklad. Čtyři mince jsou v řadě a každý hráč si může vyzvednout jednu minci nebo dvě mince na svém tahu. Hráč, který zvedne poslední minci, vyhrává. Za předpokladu, že Max hraje první, jaký krok by měl Max udělat, aby vyhrál?

pokud Max vybere dvě mince, zůstanou pouze dvě mince a Min může vybrat dvě mince a vyhrát. Vyzvednutí 1 mince tak maximalizuje Maxovu odměnu.

Jak jste si možná všimli, uzlech stromu na obrázku níže máte některé hodnoty napsané na ně, jedná se o tzv. minimax hodnotu. Hodnota minimax uzlu je užitečnost uzlu, pokud se jedná o koncový uzel.

Pokud uzel je non-terminál Max uzlu, minimax hodnota uzlu je maximální minimax hodnoty všech uzlu nástupci. Na druhou stranu, pokud uzel je non-terminál Min uzlu, minimax hodnota uzlu je minimální minimax hodnoty všech uzlu nástupci.

nyní budeme diskutovat o myšlence alfa beta prořezávání. Pokud budeme aplikovat alfa-beta prořezávání standardní minimax algoritmus dává stejné rozhodnutí jako standardní algoritmus, ale to, sušené švestky nebo snižuje uzly, které jsou neobvyklé v tom, rozhodovací strom, tj. které nemají vliv na konečné rozhodnutí algoritmu. To pomůže vyhnout se složitosti interpretace složitých stromů.

podívejte se, jak funguje KNN algoritmus.

Nyní pojďme diskutovat o intuici za touto technikou. Pokusme se najít minimax rozhodnutí v níže uvedeném stromu :

V tomto případě,

Zde ve výše uvedených výsledků je nutné mít pochybnost ve vaší mysli, že, jak můžeme najít maximum z chybějící hodnota. Takže zde je také řešení vašich pochybností:

ve druhém uzlu zvolíme minimální hodnotu jako c, která je menší nebo rovna 2, tj. c <= 2. Nyní, pokud c <= 3 a musíme zvolit max 3, c, 2 maximální hodnota bude 3.

dosáhli jsme rozhodnutí, aniž bychom se podívali na tyto uzly. A to je místo, kde alfa-beta prořezávání přichází do hry.

Klíčové body v Alfa-beta Prořezávání

• Alfa: Alfa je nejlepší volbou, nebo nejvyšší hodnotu, která jsme našli na nějaké stupně na cestě Maximizer. Počáteční hodnota pro Alfa je -∞.

• Beta: Beta je nejlepší volbou nebo nejnižší hodnotou, kterou jsme našli v jakékoli instanci podél cesty Minimizer. Počáteční hodnota pro Alfa je + ∞.

• podmínkou pro alfa-beta prořezávání je, že α >= β.

• každý uzel musí sledovat své hodnoty alfa a beta. Alfa lze aktualizovat pouze tehdy, když je na řadě MAX, a podobně beta lze aktualizovat pouze tehdy, když je to Minova šance.

• MAX bude aktualizovat pouze hodnoty alfa A MIN player bude aktualizovat pouze hodnoty beta.

• hodnoty uzlu budou předány horním uzlům místo hodnot alfa a beta během přechodu do reverse of tree.

• hodnoty alfa a Beta se předávají pouze podřízeným uzlům.

zpracování alfa-beta prořezávání

1. nejprve začneme počátečním tahem. Nejprve definujeme hodnoty alfa a beta jako nejhorší případ, tj. α = – ∞ a β= +∞. Uzel prořízneme pouze tehdy, když se alfa stane větší nebo rovna beta.

2. Protože počáteční hodnota alfa je menší než beta, tak jsme ji neřízli. Teď je řada na Maxovi. Takže v uzlu D se vypočítá hodnota alfa. Hodnota alfa v uzlu D bude max (2, 3). Takže hodnota alfa v uzlu D bude 3.

3. Nyní bude další krok na uzlu B a jeho řada na MIN nyní. Takže v uzlu B bude hodnota alfa beta min (3, ∞). Takže v uzlu B budou hodnoty alfa= – ∞ a beta bude 3.

V dalším kroku, algoritmy procházet další nástupce z Uzlu B, které je uzel E, a hodnoty α= -∞, a β= 3 budou také předány.

4. Teď je řada na Maxovi. Takže v uzlu E budeme hledat MAX. Aktuální hodnota alfa na E je – ∞ a bude porovnána s 5. Takže MAX ( – ∞ , 5) bude 5. Takže v uzlu E Alfa = 5, Beta = 5. Nyní vidíme, že alfa je větší než beta, což splňuje podmínky prořezávání, takže můžeme prořezat správného nástupce uzlu E a algoritmus nebude překročen a hodnota v uzlu E bude 5.

6. V dalším kroku algoritmus opět přichází do uzlu a z uzlu B. v uzlu se alfa změní na maximální hodnotu jako MAX ( – ∞ , 3). Takže nyní hodnota alfa a beta v uzlu a bude (3, + ∞) a bude přenesena do uzlu C. tyto stejné hodnoty budou přeneseny do uzlu F.

7. V uzlu F bude hodnota alfa porovnána s levou větví, která je 0. Takže MAX (0, 3) bude 3 a pak ve srovnání se správným dítětem, které je 1, a MAX (3,1) = 3 stále α zůstává 3, ale hodnota uzlu F se stane 1.

8. Nyní uzel F vrátí hodnotu uzlu 1 na C a porovná se s hodnotou beta na C. Nyní je řada na MIN. Takže MIN ( + ∞ , 1) bude 1. Nyní v uzlu C je α= 3 a β= 1 a alfa větší než beta, což opět splňuje podmínky prořezávání. Takže další nástupce uzlu C, tj. G bude stříhat a algoritmus nepočítá celý podstrom G.

Teď, C vrátí uzlu, hodnotu a nejlepší hodnota bude MAX (1, 3) bude 3.

výše uvedený strom je konečný strom, který zobrazuje uzly, které jsou vypočteny, a uzly, které nejsou vypočteny. Takže pro tento příklad bude optimální hodnota maximalizátoru 3.

podívejte se na open source knihovny Pythonu.

přesunout pořadí v prořezávání

účinnost alfa-beta prořezávání je založena na pořadí, ve kterém je uzel zkoumán. Řazení přesunů hraje důležitou roli při prořezávání alfa beta.

k Dispozici jsou dva typy pohybu objednání v Alfa-beta prořezávání:

1. Nejhorší Objednávání: V některých případech, alfa-beta prořezávání žádný uzel, stříhat algoritmus a funguje jako standardní algoritmus minimax. To spotřebovává spoustu času, protože alfa a beta faktory a také nedává žádné efektivní výsledky. Toto se nazývá nejhorší uspořádání při prořezávání. V tomto případě se nejlepší pohyb vyskytuje na pravé straně stromu.
2. ideální uspořádání: v některých případech alfa beta prořezávání hodně uzlů prořezaných algoritmem. Toto se nazývá ideální uspořádání při prořezávání. V tomto případě se nejlepší pohyb vyskytuje na levé straně stromu. Aplikujeme DFS proto nejprve hledat vlevo od stromu a jít hluboko dvakrát jako minimax algoritmu ve stejném množství času.

Pravidla, jak najít Dobré uspořádání

• nejlepší pohybovat se stane od nejnižšího uzlu
• Použití doménových znalostí při hledání nejlepší tah
• Pořadí uzlů by měla být takovým způsobem, že nejlepší uzly bude vypočítán jako první

Podívejte se na tento Python Tutorial pro Začátečníky

Kódy v Pythonu

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

V tomto dokumentu jsme viděli, důležitou součástí teorie her. Výkon minimax algoritmu je sice dobrý, ale algoritmus je pomalý. Abychom to udělali rychle, používáme algoritmus prořezávání alfa-beta, který sníží neobvyklé uzly z rozhodovacího stromu, aby se zlepšil výkon. V současné době je široce používán rychlý a dobře provedený algoritmus.

Podívejte se na tyto Umělé Inteligence a Strojového Učení kurzy z Velké Učení, zvyšování kvalifikace v doméně a mistr Alfa-Beta prořezávání a další algoritmy.

Další Čtení

1. A* Vyhledávací Algoritmus Umělé Inteligence (AI)
2. Rozhodovací Strom Algoritmus Vysvětlil s Příklady
3. Nejlepší První Vyhledávací Algoritmus v AI | Koncepce, Realizace, Výhody, Nevýhody
4. Co je Umělá Inteligence? Jak AI funguje, typy a budoucnost it?