alfa Beta beskärning i AI

Alpha beta beskärning är en optimeringsteknik för minimax-algoritmen. Genom denna blogg kommer vi att diskutera vad alpha beta beskärning betyder, vi kommer att diskutera minimax algoritm, regler för att hitta bra beställning och mer.

1. Inledning
2. Minimax algoritm
3. viktiga punkter i alfa-beta beskärning
4. arbetar med alfa-beta beskärning
5. flytta beställning i beskärning
6. regler för att hitta bra beställning
7. koder i Python

inledning

ordet beskärning betyder att skära ned grenar och löv. I datavetenskap beskärning är en mycket använd term som hänvisar till post och pre-beskärning i beslutsträd och slumpmässig skog. Alfa-beta beskärning är inget annat än beskärning av värdelösa grenar i beslutsträd. Denna alfa-beta beskärningsalgoritm upptäcktes oberoende av forskare på 1900-talet.

alfa-beta beskärning är en optimeringsteknik för minimax-algoritmen som diskuteras i nästa avsnitt. Behovet av beskärning kom från det faktum att beslutsträd i vissa fall blir mycket komplexa. I det trädet ökar vissa värdelösa grenar modellens komplexitet. Så för att undvika detta kommer alfa-Beta beskärning att spela så att datorn inte behöver titta på hela trädet. Dessa ovanliga noder gör algoritmen långsam. Därför genom att ta bort dessa noder algoritm blir snabb.

lär dig mer om en * algoritm.

Minimax algoritm

Minimax är en klassisk djup första sökteknik för en sekventiell två spelare. De två spelarna heter MAX och MIN. Minimax-algoritmen är utformad för att hitta det optimala draget för MAX, spelaren vid rotnoden. Sökträdet skapas genom att rekursivt expandera alla noder från roten på ett djup-först sätt tills antingen slutet av spelet eller det maximala sökdjupet uppnås. Låt oss utforska denna algoritm i detalj.

som redan nämnts finns det två spelare i spelet, nämligen – Max och Min. Max spelar det första steget. Max uppgift är att maximera sin belöning medan Min uppgift är att minimera Max belöning, öka sin egen belöning samtidigt. Låt oss säga att Max kan vidta åtgärder a, b eller c. vilken av dem ger Max den bästa belöningen när spelet slutar? För att svara på denna fråga måste vi utforska spelträdet till ett tillräckligt djup och anta att Min spelar optimalt för att minimera belöningen för Max.

här är ett exempel. Fyra mynt är i rad och varje spelare kan plocka upp ett mynt eller två mynt på hans/hennes tur. Spelaren som plockar upp det sista myntet vinner. Förutsatt att Max spelar först, vilket drag ska Max göra för att vinna?

om Max väljer två mynt, återstår bara två mynt och Min kan välja två mynt och vinna. Således plocka upp 1 mynt ska maximera Max belöning.

som du kanske har märkt har noderna i trädet i figuren nedan några värden inskrivna på dem, dessa kallas minimax-värde. Minimax-värdet för en nod är nodens nytta om det är en terminalnod.

om noden är en icke-terminal Max-nod är nodens minimax-värde det maximala av minimax-värdena för alla nodens efterträdare. Å andra sidan, om noden är en icke-terminal min-nod, är nodens minimax-värde det minsta av minimax-värdena för alla nodens efterträdare.

nu kommer vi att diskutera tanken bakom alfa beta beskärning. Om vi tillämpar alfa-beta beskärning till standard minimax algoritm det ger samma beslut som standard algoritm men det katrinplommon eller skär ner noderna som är ovanliga i beslutsträdet dvs som inte påverkar det slutliga beslutet av algoritmen. Detta kommer att bidra till att undvika komplexiteten i tolkningen av komplexa träd.

se hur KNN-algoritmen fungerar.

låt oss nu diskutera intuitionen bakom denna teknik. Låt oss försöka hitta minimax beslut i nedanstående träd :

i detta fall,

här i ovanstående resultat måste du ha tvivel i ditt sinne att hur kan vi hitta maximalt från saknat värde. Så här är lösningen av ditt tvivel också:

i den andra noden väljer vi minimivärdet som c vilket är mindre än eller lika med 2 dvs c <= 2. Nu om c < = 3 och vi måste välja max 3, c, 2 blir det maximala värdet 3.

vi har fattat ett beslut utan att titta på dessa noder. Och det är här alfa-beta beskärning kommer in i leken.

viktiga punkter i alfa-beta beskärning

• Alpha: Alpha är det bästa valet eller det högsta värdet som vi har hittat vid något tillfälle längs vägen för Maximizer. Det ursprungliga värdet för Alfa är-Xiaomi.

• Beta: Beta är det bästa valet eller det lägsta värdet som vi har hittat i alla fall längs Minimizer-vägen. Det ursprungliga värdet för Alfa är + GHz.

• villkoret för alfa-beta-beskärning är att 0,1844 = xnumx xnumx = xnumx xnumx.

• varje nod måste hålla reda på dess alfa-och betavärden. Alpha kan uppdateras endast när det är MAX tur och, liknande, beta kan uppdateras endast när det är MIN chans.

• MAX uppdaterar endast alfavärden och MIN spelare uppdaterar endast betavärden.

• nodvärdena kommer att skickas till övre noder istället för värden av alfa och beta Under gå in i omvänd träd.

• Alfa-och betavärden skickas endast till barnnoder.

bearbetning av alfa-beta beskärning

1. vi börjar först med det första draget. Vi kommer initialt att definiera alfa-och betavärdena som det värsta fallet, dvs. Vi kommer att beskära noden endast när Alfa blir större än eller lika med beta.

2. Eftersom det ursprungliga värdet av alfa är mindre än beta så vi inte beskära det. Nu är det dags för MAX. Så vid nod D kommer värdet av alfa att beräknas. Värdet av alfa vid nod D kommer att vara max (2, 3). Så värdet av alfa vid nod D kommer att vara 3.

3. Nu kommer nästa drag att vara på nod B och dess tur för MIN nu. Så, vid nod B, kommer värdet av alfa beta att vara min (3, POV). Så, vid nod B-värden kommer att vara alfa= – megapixlar och beta blir 3.

i nästa steg går algoritmer över nästa efterträdare av nod B som är nod E, och värdena på 2= – xnumx och 3 xnumx xnumx kommer också att skickas.

4. Nu är det dags för MAX. Så på nod E letar vi efter MAX. Det nuvarande värdet av alfa vid E är-GHz och det kommer att jämföras med 5. Så, MAX (- 0,5 xnumx) blir 5. Så vid nod E, Alfa = 5, Beta = 5. Nu som vi kan se att alfa är större än beta som uppfyller beskärningsförhållandet så att vi kan beskära rätt efterträdare av nod E och algoritmen kommer inte att korsas och värdet vid nod E kommer att vara 5.

6. I nästa steg kommer algoritmen igen till nod A från nod B. vid nod A kommer alfa att ändras till maximalt värde som MAX (- xhamster, 3). Så nu kommer värdet av alfa och beta vid nod A att vara (3, + GHz) respektive kommer att överföras till nod C. samma värden kommer att överföras till nod F.

7. Vid nod F värdet av alfa kommer att jämföras med den vänstra grenen som är 0. Så, MAX (0, 3) blir 3 och jämförs sedan med rätt barn som är 1, och MAX (3,1) = 3 fortfarande förblir 3, men nodvärdet för F blir 1.

8. Nu kommer nod F att returnera nodvärdet 1 till C och jämföra med betavärdet vid C. Nu är det tur för MIN. Så, MIN (+2BG, 1) kommer att vara 1. Nu vid nod C, är 6= 3, och 1= 1 och alfa större än beta, vilket igen uppfyller beskärningsförhållandet. Så nästa efterträdare av nod C dvs. G kommer att beskäras och algoritmen beräknade inte hela underträdet G.

nu kommer C att returnera nodvärdet till A och det bästa värdet av A kommer att vara MAX (1, 3) kommer att vara 3.

ovanstående representerade träd är det sista trädet som visar noderna som beräknas och noderna som inte beräknas. Så, för detta exempel kommer det optimala värdet av maximiseraren att vara 3.

titta på Python-bibliotek med öppen källkod.

flytta beställning i beskärning

effektiviteten av alfa-beta beskärning baseras på den ordning i vilken nod undersöks. Flytta beställning spelar en viktig roll i alfa beta beskärning.

det finns två typer av flytt beställning i alfa beta beskärning:

1. värsta beställning: i vissa fall av alfa beta beskärning ingen av noden beskäras av algoritmen och fungerar som standard minimax algoritm. Detta förbrukar mycket tid på grund av alfa-och betafaktorer och ger inte några effektiva resultat. Detta kallas värsta beställning i beskärning. I det här fallet sker det bästa draget på höger sida av trädet.
2. idealisk beställning: i vissa fall av alfa beta beskärning mycket av noderna beskärs av algoritmen. Detta kallas perfekt beställning vid beskärning. I det här fallet sker det bästa draget på vänster sida av trädet. Vi tillämpar DFS därmed det första sök kvar av trädet och gå djupt dubbelt så minimax algoritm i samma tid.

regler för att hitta bra beställning

• det bästa draget händer från den lägsta noden
• använd domänkunskap medan du hittar det bästa draget
• ordning av noder ska vara på ett sådant sätt att de bästa noderna beräknas först

kolla in denna Python-handledning för nybörjare

koder i Python

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

i detta dokument har vi sett en viktig del av spelteori. Även om minimax-algoritmens prestanda är bra men algoritmen är långsam. Så för att göra det snabbt använder vi alfa-beta beskärningsalgoritm som kommer att skära ner de ovanliga noderna från beslutsträdet för att förbättra prestanda. Numera används snabb och väl utförd algoritm i stor utsträckning.

kolla in dessa artificiell intelligens och Maskininlärningskurser från bra lärande till kompetensutveckling i domänen och master Alpha Beta beskärning och andra sådana algoritmer.

Vidare läsning

1. A * sökalgoritm i artificiell intelligens (AI)
2. Beslutsträdsalgoritm förklarad med exempel
3. bästa första sökalgoritm i AI | koncept, implementering, Fördelar, Nackdelar
4. Vad är artificiell intelligens? Hur fungerar AI, typer och framtid för it?