Alpha beta beskjæring er en optimaliseringsteknikk for minimax algoritmen. I løpet av denne bloggen vil vi diskutere hva alpha beta beskjæring betyr, vi vil diskutere minimax algoritme, regler for å finne god bestilling og mer.
- Innledning
- Minimax algoritme
- Nøkkelpunkter I Alfa-beta Beskjæring
- Arbeid Av Alfa-beta Beskjæring
- Flytt Bestilling I Beskjæring
- Regler for Å finne God bestilling
- Koder I Python
innledning
Ordet ‘Beskjæring’ Betyr Å Kutte Ned Grener og blader. I datavitenskap er beskjæring et mye brukt begrep som refererer til post og pre-beskjæring i beslutningstrær og tilfeldig skog. Alpha-beta beskjæring er ingenting annet enn beskjæring av ubrukelige grener i beslutningstrær. Denne alfa-beta beskjæringsalgoritmen ble oppdaget uavhengig av forskere på 1900-tallet.
Alfa-beta beskjæring er en optimaliseringsteknikk for minimax-algoritmen som diskuteres i neste avsnitt. Behovet for beskjæring kom fra det faktum at i noen tilfeller beslutning trær blir svært komplekse. I det treet øker noen ubrukelige grener kompleksiteten til modellen. Så, for å unngå Dette, Kommer Alpha-Beta beskjæring til å spille slik at datamaskinen ikke trenger å se på hele treet. Disse uvanlige noder gjør algoritmen sakte. Derfor ved å fjerne disse nodene algoritmen blir rask.
Lær om a * – algoritmen.
Minimax algoritme
Minimax er en klassisk dybde-første søketeknikk for en sekvensiell to-player spill. De to spillerne kalles MAX og MIN. Minimax-algoritmen er designet for å finne det optimale trekket FOR MAX, spilleren på rotnoden. Søketreet er opprettet ved rekursivt å utvide alle noder fra roten på en dybde – første måte til enten slutten av spillet eller maksimal søkedybde er nådd. La oss utforske denne algoritmen i detalj.
som allerede nevnt er det to spillere i spillet, nemlig-Max Og Min. Max spiller det første trinnet. Max oppgave er å maksimere sin belønning mens Min oppgave er å minimere Max belønning, øke sin egen belønning på samme tid. La Oss si At Max kan ta handlinger a, b eller c. Hvilken Av Dem vil Gi Max den beste belønningen når spillet slutter? For å svare på dette spørsmålet, må vi utforske spilltreet til en tilstrekkelig dybde og anta At Min spiller optimalt for Å minimere belønningen På Maks.
her er et eksempel. Fire mynter er på rad, og hver spiller kan plukke opp en mynt eller to mynter på hans / hennes tur. Spilleren som plukker opp den siste mynten vinner. Forutsatt At Max spiller først, hvilket trekk Skal Max gjøre for å vinne?
Hvis Maks velger to mynter, forblir bare To mynter og Min kan velge to mynter og vinne. Dermed plukke opp 1 mynt skal maksimere Max belønning.
som du kanskje har lagt merke til, har nodene til treet i figuren nedenfor noen verdier innskrevet på dem, disse kalles minimax-verdi. Minimax verdien av en node er nytten av noden hvis det er en terminal node.
hvis noden er En Ikke-terminal Max-node, er minimax-verdien for noden maksimum minimax-verdiene for alle nodens etterfølgere. På den annen side, hvis noden er en Ikke-terminal min-node, er minimax-verdien av noden minimum av minimax-verdiene for alle nodens etterfølgere.
nå skal Vi diskutere ideen bak alpha beta beskjæring. Hvis vi bruker alfa-beta beskjæring til standard minimax algoritmen det gir samme beslutning som standard algoritme, men det svisker eller kutter ned nodene som er uvanlig i beslutningstreet dvs. som ikke påvirker den endelige avgjørelsen gjort av algoritmen. Dette vil bidra til å unngå kompleksiteten i tolkningen av komplekse trær.
Se HVORDAN knn-algoritmen fungerer.
la Oss nå diskutere intuisjonen bak denne teknikken. La oss prøve å finne minimax avgjørelse i under treet :
I dette tilfellet,
Minimax Avgjørelse = MAKS {MIN {3, 5, 10}, MIN {2, a, b}, MIN {2, 7, 3}}
= MAKS {3, c, 2} = 3
Her i det ovennevnte resultatet må du ha tvil i tankene om at hvordan kan vi finne maksimumet fra manglende verdi. Så her er løsningen av din tvil også:
i den andre noden velger vi minimumsverdien som c som er mindre enn eller lik 2, dvs.c <= 2. Nå hvis c < = 3 og vi må velge maks 3, c, 2 vil maksimumsverdien være 3.
Vi har nådd en beslutning uten å se på disse nodene. Og det er her alpha-beta beskjæring kommer inn i stykket.
Viktige punkter I Alpha-beta Beskjæring
- Alpha: Alpha er det beste valget eller den høyeste verdien som vi har funnet på noen forekomst langs Banen Til Maximizer. Den opprinnelige verdien for alpha er -∞.
- Beta: Beta Er det beste valget eller den laveste verdien som vi har funnet på noen forekomst langs Banen Minimizer. Den opprinnelige verdien for alpha er + ∞
- betingelsen for Alfa-beta-Beskjæring er at α > = β.
- hver node må holde styr på alfa-og beta-verdiene. Alpha kan oppdateres bare NÅR DET ER MAX tur og, tilsvarende, beta kan oppdateres bare når DET ER MIN sjanse.
- MAX vil oppdatere bare alfa verdier OG MIN player vil oppdatere bare beta verdier.
- nodeverdiene vil bli sendt til øvre noder i stedet for verdier av alfa og beta under gå i revers av treet.
- Alfa-og Beta-verdier sendes bare til underordnede noder.
Arbeid Av Alfa-beta Beskjæring
- Vi starter først med det første trekket. I utgangspunktet vil vi definere alfa-og beta-verdiene som i verste fall, dvs. α = – ∞ og β= +∞ Vi vil beskjære noden bare når alfa blir større enn eller lik beta.
2. Siden den opprinnelige verdien av alpha er mindre enn beta så vi ikke beskjære det. Nå er DET TUR FOR MAX. Så, ved node D, vil verdien av alfa bli beregnet. Verdien av alfa Ved node D vil være maks (2, 3). Så, verdien av alfa ved node D vil være 3.
3. Nå vil neste trekk være på node B og sin tur for MIN nå. Så, på node B, vil verdien av alfa beta være min (3,∞). Så, ved node B-verdier vil være alfa= – ∞ og beta vil være 3.
i neste trinn går algoritmene gjennom den neste etterfølgeren til Node B, som er node E, og verdiene til α= – ∞ og β vil også bli bestått.
4. Nå er DET TUR FOR MAX. Så, på node E vil VI se ETTER MAX. Den nåværende verdien av alpha Ved E er – ∞ og den vil bli sammenlignet med 5. SÅ, MAKS ( – ∞ , 5) vil være 5. Så, ved node E, alfa = 5, Beta = 5. Nå som vi kan se at alfa er større enn beta som tilfredsstiller beskjæringstilstanden, slik at vi kan beskjære den rette etterfølgeren til node E, og algoritmen vil ikke bli krysset og verdien Ved node E vil være 5.
6. I neste trinn kommer algoritmen igjen til node A Fra node B. ved node a alfa vil bli endret TIL maksimumsverdi SOM MAKS (- ∞, 3). Så nå vil verdien av alfa og beta ved node a være henholdsvis (3, + ∞) og overføres til node C. De samme verdiene overføres til node F.
7. Ved node F vil verdien av alfa bli sammenlignet med venstre gren som er 0. SÅ, MAKS (0, 3) vil være 3 og deretter sammenlignet med riktig barn som er 1, OG MAKS (3,1) = 3 fortsatt α forblir 3, men nodeverdien Av F blir 1.
8. Nå node F vil returnere node verdi 1 Til C og vil sammenligne til beta verdi Ved C. Nå sin tur FOR MIN. SÅ, MIN ( + ∞ , 1) vil være 1. Nå På node C, α= 3, og β= 1 og alfa er større enn beta som igjen tilfredsstiller beskjæringstilstanden. Så, den neste etterfølgeren til node C dvs. G vil bli beskåret og algoritmen ikke beregne hele undertreet G.
Nå vil C returnere nodeverdien Til A, og den beste verdien Av A VIL VÆRE MAKS (1, 3) vil være 3.
ovennevnte representert treet er det endelige treet som viser nodene som er beregnet og nodene som ikke er beregnet. Så for dette eksemplet vil den optimale verdien av maksimatoren være 3.
Se på Open source Python-Biblioteker.
Flytt Bestilling I Beskjæring
effektiviteten av alfa – beta beskjæring er basert på rekkefølgen der noden undersøkes. Flytt bestilling spiller en viktig rolle i alpha beta beskjæring.
Det finnes to typer flyttebestilling I Alpha beta beskjæring:
- Verste Bestilling: i noen tilfeller av alpha beta beskjæring ingen av noden beskjæres av algoritmen og fungerer som standard minimax algoritme. Dette bruker mye tid som på grunn av alfa og beta faktorer og heller ikke gir noen effektive resultater. Dette kalles Verste bestilling i beskjæring. I dette tilfellet skjer det beste trekket på høyre side av treet.
- Ideell Bestilling: i noen tilfeller av alpha beta beskjæring mye av nodene beskjæres av algoritmen. Dette kalles Ideell bestilling i beskjæring. I dette tilfellet skjer det beste trekket på venstre side av treet. Vi bruker DFS derfor det første søk igjen av treet og gå dypt dobbelt så minimax algoritme i samme tidsperiode.
Regler for Å finne God bestilling
- det beste trekket skjer fra den laveste noden
- Bruk domenekunnskap mens du finner det beste trekket
- Rekkefølge av noder bør være på en slik måte at de beste nodene blir beregnet først
Sjekk Ut Denne Python-Opplæringen For Nybegynnere
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 dette dokumentet har vi sett en viktig komponent I Spillteori. Selv om minimax algoritmen ytelse er bra, men algoritmen er treg. Så for å gjøre det raskt bruker vi alpha-beta beskjæring algoritme som vil kutte ned de uvanlige noder fra beslutningstreet for å forbedre ytelsen. I dag er rask og godt utført algoritme mye brukt.
Sjekk Ut Disse Artificial Intelligence og Machine Learning kurs Fra Stor Læring å upskill i domenet og master Alpha Beta beskjæring og andre slike algoritmer.
Videre Lesing
- A* Søkealgoritme I Kunstig Intelligens (AI)
- Beslutningstrealgoritme Forklart Med Eksempler
- Beste Første Søkealgoritme I AI | Konsept, Implementering, Fordeler, Ulemper
- Hva Er Kunstig Intelligens? HVORDAN JOBBER AI, Typer og Fremtid for it?