Alpha Beta beskæring i AI

Alpha beta beskæring er en optimering teknik til minimaks algoritme. I løbet af denne blog, vi vil diskutere, hvad alpha beta beskæring betyder, vi vil diskutere minimaksalgoritme, regler for at finde god bestilling, og mere.

1. introduktion
2. minimaksalgoritme
3. nøglepunkter i alfa-beta beskæring
4. arbejde med alfa-beta beskæring
5. Flyt bestilling i beskæring
6. regler for at finde god bestilling
7. koder i Python

introduktion

ordet ‘beskæring’ betyder at skære grene og blade ned. I datavidenskab beskæring er et meget brugt udtryk, der refererer til post og forbeskæring i beslutningstræer og tilfældig skov. Alpha-beta beskæring er intet andet end beskæring af ubrugelige grene i beslutningstræer. Denne alfa-beta beskæringsalgoritme blev opdaget uafhængigt af forskere i 1900 ‘ erne.

alfa-beta beskæring er en optimeringsteknik til minimaksalgoritmen, som diskuteres i næste afsnit. Behovet for beskæring kom fra det faktum, at beslutningstræer i nogle tilfælde bliver meget komplekse. I det træ øger nogle ubrugelige grene kompleksiteten af modellen. Så for at undgå dette kommer alfa-Beta beskæring til at spille, så computeren ikke behøver at se på hele træet. Disse usædvanlige noder gør algoritmen langsom. Derfor ved at fjerne disse noder algoritme bliver hurtig.

Lær om en * algoritme.

minimaks algoritme

Minimaks er en klassisk dybde-første søgeteknik til et sekventielt to-spiller spil. De to spillere kaldes maks og MIN. Minimaksalgoritmen er designet til at finde det optimale træk for maks, afspilleren ved rodnoden. Søgetræet oprettes ved rekursivt at udvide alle noder fra roden på en dybde-første måde, indtil enten slutningen af spillet eller den maksimale søgedybde er nået. Lad os undersøge denne algoritme i detaljer.

som allerede nævnt er der to spillere i spillet, nemlig Maks og Min. Maks spiller det første skridt. Maks opgave er at maksimere sin belønning, mens Min opgave er at minimere maks belønning, øge sin egen belønning på samme tid. Lad os sige, at maks kan tage handlinger A, b eller c. hvilken af dem giver maks den bedste belønning, når spillet slutter? For at besvare dette spørgsmål er vi nødt til at udforske spiltræet til en tilstrækkelig dybde og antage, at Min spiller optimalt for at minimere belønningen på maks.

her er et eksempel. Fire mønter er i træk, og hver spiller kan hente en mønt eller to mønter på hans/hendes tur. Den spiller, der henter den sidste mønt vinder. Hvis man antager, at maks spiller først, hvilket træk skal maks gøre for at vinde?

hvis maks. vælger to mønter, er der kun to mønter tilbage, og Min kan vælge to mønter og vinde. Således opsamling 1 mønt skal maksimere maks belønning.

som du måske har bemærket, har træets noder i nedenstående figur nogle værdier indskrevet på dem, disse kaldes minimaksværdi. Det minimakseværdi af en node er nytten af noden, hvis det er en terminal node.

hvis noden er en ikke-terminal maks.node, er nodens minimakseværdi det maksimale af minimakseværdierne for alle nodens efterfølgere. På den anden side, hvis noden er en ikke-terminal min-node, er nodens minimakseværdi minimumet af minimakseværdierne for alle nodens efterfølgere.

nu vil vi diskutere ideen bag alpha beta beskæring. Hvis vi anvender alfa-beta beskæring til standard minimaksalgoritmen, giver den samme beslutning som standardalgoritmen, men den beskærer eller skærer ned de noder, der er usædvanlige i beslutningstræet, dvs.som ikke påvirker den endelige beslutning truffet af algoritmen. Dette vil bidrage til at undgå kompleksiteten i fortolkningen af komplekse træer.

se hvordan KNN algoritme fungerer.

lad os nu diskutere intuitionen bag denne teknik. Lad os prøve at finde minimaks beslutning i nedenstående træ :

i dette tilfælde,

her i ovenstående resultat skal du være i tvivl om, at hvordan kan vi finde det maksimale fra manglende værdi. Så her er løsningen af din tvivl også:

i den anden knude vælger vi minimumsværdien som c, som er mindre end eller lig med 2, dvs.c < = 2. Nu hvis c < = 3, og vi skal vælge maks.3, c, 2, vil den maksimale værdi være 3.

vi har nået en beslutning uden at se på disse noder. Og det er her, alpha-beta beskæring kommer ind i stykket.

nøglepunkter i alfa-beta beskæring

• Alpha: Alpha er det bedste valg eller den højeste værdi, som vi har fundet i ethvert tilfælde langs Maksimeringsstien. Den oprindelige værdi for Alfa er-kr.

• Beta: Beta er det bedste valg eller den laveste værdi, som vi har fundet i ethvert tilfælde langs Minimeringsstien. Den oprindelige værdi for Alfa er + liter.

• betingelsen for alfa-beta-beskæring er, at liter >= liter.

• hver node skal holde styr på sine alfa-og beta-værdier. Alpha kan kun opdateres, når det er maks tur, og på samme måde kan beta kun opdateres, når det er MIN chance.

• maks opdaterer kun alfa-værdier, og min player opdaterer kun betaværdier.

• nodeværdierne overføres til øvre noder i stedet for værdier af alfa og beta under gå i omvendt træ.

• Alfa-og Beta-værdier overføres kun til underordnede noder.

arbejde med alfa-beta beskæring

1. vi starter først med det første træk. Vi vil oprindeligt definere alfa-og beta-værdierne som det værste tilfælde, dvs. Vi beskærer kun noden, når alfa bliver større end eller lig med beta.

2. Da den oprindelige værdi af alpha er mindre end beta, så vi beskærede det ikke. Nu er det tur til maks. Så ved node D beregnes værdien af alfa. Værdien af alfa ved node D vil være maks (2, 3). Så værdien af alfa ved node D vil være 3.

3. Nu er det næste træk på node B og dets tur til MIN nu. Så ved node B vil værdien af alpha beta være min (3, liter). Så ved node B-værdier vil være alpha= – kur og beta vil være 3.

i det næste trin krydser algoritmer den næste efterfølger af Node B, som er node E, og værdierne for length= – length og length= 3 vil også blive bestået.

4. Nu er det tur til maks. Så ved node E vil vi kigge efter maks. Den aktuelle værdi af alfa ved E er-kr., og den vil blive sammenlignet med 5. Så, maks (- kr., 5) vil være 5. Så ved node E, Alfa = 5, Beta = 5. Nu som vi kan se, at alpha er større end beta, som opfylder beskæringstilstanden, så vi kan beskære den rigtige efterfølger af node E og algoritme vil ikke blive krydset, og værdien ved node E vil være 5.

6. I det næste trin kommer algoritmen igen til node A fra node B. ved node a alfa vil blive ændret til maksimal værdi som maks. Så nu vil værdien af alfa og beta ved node A være (henholdsvis 3, + liter) og overføres til node C. Disse samme værdier overføres til node F.

7. Ved node F sammenlignes værdien af alpha med den venstre gren, der er 0. Så, maks (0, 3) vil være 3 og derefter sammenlignet med det rigtige barn, som er 1, og maks (3,1) = 3 stadig forbliver 3, men nodeværdien af F bliver 1.

8. NU Returnerer node F nodeværdien 1 til C og sammenligner med beta-værdi ved C. nu er det min. Så MIN (+lp, 1) vil være 1. Nu ved node C, er LARP= 3, og LARP= 1 og alfa større end beta, som igen opfylder beskæringstilstanden. Så den næste efterfølger af node C dvs. G vil blive beskåret, og algoritmen beregnede ikke hele undertræet G.

NU Returnerer C nodeværdien til A, og den bedste værdi af A vil være maks (1, 3) vil være 3.

ovenstående repræsenterede træ er det sidste træ, der viser de noder, der beregnes, og de noder, der ikke beregnes. Så for dette eksempel vil den optimale værdi af maksimeringen være 3.

kig på Open source Python biblioteker.

Flyt bestilling i beskæring

effektiviteten af alfa – beta beskæring er baseret på den rækkefølge, hvor node undersøges. Flyt bestilling spiller en vigtig rolle i alpha beta beskæring.

der er to typer af flytte bestilling i Alpha beta beskæring:

1. værste bestilling: i nogle tilfælde af alpha beta beskæring ingen af noden beskåret af algoritmen og fungerer som standard minimaks algoritme. Dette bruger meget tid som på grund af alfa-og beta-faktorer og giver heller ikke nogen effektive resultater. Dette kaldes værste bestilling i beskæring. I dette tilfælde sker det bedste træk på højre side af træet.
2. ideel bestilling: i nogle tilfælde af alpha beta beskæring parti af knuderne beskåret af algoritmen. Dette kaldes ideel bestilling i beskæring. I dette tilfælde sker det bedste træk på venstre side af træet. Vi anvender DFS dermed det første søgning til venstre for træet og gå dybt dobbelt så minimaks algoritme i den samme mængde tid.

regler for at finde god bestilling

• det bedste træk sker fra den laveste node
• brug domæneviden, mens du finder det bedste træk
• rækkefølgen af noder skal være på en sådan måde, at de bedste noder beregnes først

Tjek denne Python-Tutorial til begyndere

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 dokument har vi set en vigtig komponent i spilteori. Selvom minimaksalgoritmens ydeevne er god, men algoritmen er langsom. Så for at gøre det hurtigt bruger vi alfa-beta beskæringsalgoritme, som vil skære ned de usædvanlige noder fra beslutningstræet for at forbedre ydeevnen. I dag er hurtig og veludført algoritme meget udbredt.

tjek disse kunstig intelligens og Machine Learning Kurser fra stor læring til opkvalificering i domænet og master Alpha Beta beskæring og andre sådanne algoritmer.

yderligere læsning

1. A * søgealgoritme i kunstig intelligens (AI)
2. Beslutningstræalgoritme forklaret med eksempler
3. bedste første søgealgoritme i AI | koncept, implementering, Fordele, Ulemper
4. Hvad er kunstig intelligens? Hvordan fungerer AI, typer og fremtid for it?