tăiere alfa Beta în AI

tunderea Alpha beta este o tehnică de optimizare pentru algoritmul minimax. Pe parcursul acestui blog, vom discuta despre ce înseamnă tăierea alfa beta, vom discuta algoritmul minimax, regulile pentru a găsi o comandă bună și multe altele.

1. Introducere
2. algoritm Minimax
3. puncte cheie în alfa-beta tăiere
4. de lucru de alfa-beta tăiere
5. muta comanda în tăiere
6. reguli pentru a găsi comanda bun
7. coduri în Python

introducere

Cuvântul ‘tăiere’ înseamnă tăierea ramurilor și a frunzelor. În știința datelor, tăierea este un termen mult folosit care se referă la post și pre-tăiere în copaci de decizie și pădure aleatoare. Tunderea alfa-beta nu este altceva decât tăierea ramurilor inutile în copacii de decizie. Acest algoritm de tăiere alfa-beta a fost descoperit independent de cercetători în anii 1900.

tăierea alfa-beta este o tehnică de optimizare pentru algoritmul minimax, care este discutată în secțiunea următoare. Nevoia de tăiere a venit din faptul că, în unele cazuri, copacii de decizie devin foarte complexi. În acel copac, unele ramuri inutile cresc complexitatea modelului. Deci, pentru a evita acest lucru, tăierea Alfa-Beta vine să se joace, astfel încât computerul să nu fie nevoit să privească întregul copac. Aceste noduri neobișnuite fac algoritmul lent. Prin urmare, prin eliminarea acestor noduri algoritm devine rapid.

Aflați mai multe despre un algoritm*.

algoritmul Minimax

Minimax este o tehnică clasică de căutare în profunzime pentru un joc secvențial cu doi jucători. Cei doi jucători se numesc MAX și MIN. Algoritmul minimax este conceput pentru a găsi mișcarea optimă pentru MAX, jucătorul de la nodul rădăcină. Arborele de căutare este creat prin extinderea recursivă a tuturor nodurilor de la rădăcină într-o manieră de adâncime până la sfârșitul jocului sau la adâncimea maximă de căutare. Să explorăm acest algoritm în detaliu.

după cum sa menționat deja, există doi jucători în joc, și anume – Max și Min. Max joacă primul pas. Sarcina lui Max este de a-și maximiza recompensa, în timp ce sarcina lui Min este de a minimiza recompensa lui Max, mărindu-și propria recompensă în același timp. Să presupunem că Max poate lua acțiunile a, b sau c. care dintre ele îi va oferi lui Max cea mai bună recompensă la sfârșitul jocului? Pentru a răspunde la această întrebare, trebuie să explorăm arborele de joc la o adâncime suficientă și să presupunem că Min joacă optim pentru a minimiza recompensa lui Max.

Iată un exemplu. Patru monede sunt într-un rând și fiecare jucător poate ridica o monedă sau două monede pe rândul său. Jucătorul care ridică ultima monedă câștigă. Presupunând că Max joacă primul,ce mișcare ar trebui să facă Max pentru a câștiga?

dacă Max alege două monede, atunci rămân doar două monede, iar Min poate alege două monede și câștiga. Astfel, ridicarea a 1 monedă va maximiza recompensa lui Max.

după cum ați observat, nodurile arborelui din figura de mai jos au unele valori înscrise pe ele, acestea se numesc valoare minimax. Valoarea minimax a unui nod este utilitatea nodului dacă este un nod terminal.

dacă nodul este un nod max non-terminal, valoarea minimax a nodului este maximul valorilor minimax ale tuturor succesorilor nodului. Pe de altă parte, dacă nodul este un nod min non-terminal, valoarea minimax a nodului este minimul valorilor minimax ale tuturor succesorilor nodului.

acum vom discuta ideea din spatele tăierii alfa beta. Dacă aplicăm tăierea alfa-beta algoritmului minimax standard, acesta dă aceeași decizie ca cea a algoritmului standard, dar prune sau taie nodurile neobișnuite în arborele de decizie, adică care nu afectează decizia finală luată de algoritm. Acest lucru va ajuta la evitarea complexității interpretării copacilor complexi.

vedeți cum funcționează algoritmul KNN.

acum să discutăm intuiția din spatele acestei tehnici. Să încercăm să găsim decizia minimax în arborele de mai jos :

în acest caz,

aici, în rezultatul de mai sus, trebuie să aveți o îndoială în mintea dvs. că cum putem găsi maximul din valoarea lipsă. Deci, aici este soluția de îndoială, de asemenea:

în al doilea nod vom alege valoarea minimă ca c, care este mai mică sau egală cu 2 adică c <= 2. Acum, Dacă c < = 3 și trebuie să alegem max 3, c, 2 valoarea maximă va fi 3.

am ajuns la o decizie fără să ne uităm la acele noduri. Și aici intră în joc tăierea alfa-beta.

puncte cheie în tăierea alfa-beta

• alfa: alfa este cea mai bună alegere sau cea mai mare valoare pe care am găsit-o în orice caz pe calea Maximizatorului. Valoarea inițială pentru alfa este-XV.

• Beta: Beta este cea mai bună alegere sau cea mai mică valoare pe care am găsit-o în orice instanță de-a lungul căii Minimizer. Valoarea inițială pentru alfa este de + XV.

• condiția pentru tăierea alfa-beta este aceea că: > = 0x.

• fiecare nod trebuie să țină evidența valorilor sale alfa și beta. Alpha poate fi actualizat numai atunci când este rândul lui MAX și, în mod similar, beta poate fi actualizat numai atunci când este șansa lui MIN.

• MAX va actualiza numai valorile alfa și Min player va actualiza numai valorile beta.

• valorile nodului vor fi transmise nodurilor superioare în loc de valori ale alfa și beta în timpul mersului în reversul arborelui.

• valorile Alfa și Beta vor fi transmise numai nodurilor copil.

de lucru de tăiere alfa-beta

1. vom începe mai întâi cu mutarea inițială. Vom defini inițial valorile alfa și beta ca fiind cel mai rău caz, adică. Vom tăia nodul numai atunci când alfa devine mai mare sau egal cu beta.

2. Deoarece valoarea inițială a alfa este mai mică decât beta, așa că nu am tăiat-o. Acum e rândul lui MAX. Deci, la nodul D, valoarea alfa va fi calculată. Valoarea alfa la nodul D va fi max (2, 3). Deci, valoarea alfa la nodul D va fi 3.

3. Acum, următoarea mișcare va fi pe nodul B și rândul său, pentru MIN acum. Deci, la nodul B, valoarea alfa beta va fi min (3, hectolix). Deci, la nodul B, valorile vor fi alfa = – XV, iar beta va fi 3.

în etapa următoare, algoritmii traversează următorul succesor al nodului B, care este nodul E, iar valorile de la XlX= – XlX și XlX= 3 vor fi, de asemenea, trecute.

4. Acum e rândul lui MAX. Deci, la nodul E vom căuta MAX. Valoarea actuală a lui Alfa la E este de-XV și va fi comparată cu 5. Deci, MAX (- 0,5) va fi 5. Deci, la nodul e, alfa = 5, Beta = 5. Acum, după cum putem vedea că alfa este mai mare decât beta, care satisface condiția de tăiere, astfel încât să putem tăia succesorul potrivit al nodului E și algoritmul nu va fi traversat, iar valoarea la nodul E va fi 5.

6. În pasul următor algoritmul vine din nou la nodul A de la nodul B. la nodul a alfa va fi schimbat la valoarea maximă ca MAX (- XV, 3). Deci, acum, valoarea alfa și beta la nodul a va fi (3, + XV) respectiv și va fi transferată la nodul C. aceleași valori vor fi transferate la nodul F.

7. La nodul F valoarea alfa va fi comparată cu ramura stângă care este 0. Deci, MAX (0, 3) va fi 3 și apoi comparat cu copilul potrivit care este 1, iar MAX (3,1) = 3 încă rămâne 3, dar valoarea nodului F va deveni 1.

8. Acum nodul F va returna valoarea nodului 1 la C și se va compara cu valoarea beta la C. acum rândul său, pentru MIN. Deci, MIN (+0,1) va fi 1. Acum, la nodul c, XV = 3, și 0xtx= 1 și alfa este mai mare decât beta, care satisface din nou starea de tăiere. Deci, următorul succesor al nodului C adică. G va fi tăiat și algoritmul nu a calculat întregul subarbor G.

acum, C va returna valoarea nodului la A și cea mai bună valoare A lui a va fi MAX (1, 3) va fi 3.

arborele reprezentat mai sus este arborele final care arată nodurile care sunt calculate și nodurile care nu sunt calculate. Deci, pentru acest exemplu, valoarea optimă a maximizatorului va fi 3.

Uită-te la bibliotecile Python open source.

ordonarea mișcării în tăiere

eficacitatea tăierii alfa – beta se bazează pe ordinea în care este examinat nodul. Ordonarea mișcărilor joacă un rol important în tăierea alfa beta.

există două tipuri de ordonare a mișcărilor în tăierea alfa beta:

1. cea mai proastă comandă: în unele cazuri de tăiere alfa beta, niciunul dintre noduri nu este tăiat de algoritm și funcționează ca algoritmul minimax standard. Acest lucru consumă o mulțime de timp ca din cauza factorilor alfa și beta și, de asemenea, nu dă rezultate eficiente. Aceasta se numește cea mai proastă ordonare în tăiere. În acest caz, cea mai bună mișcare are loc în partea dreaptă a copacului.
2. ordonare ideală: în unele cazuri de alfa beta lot de tăiere a nodurilor tunși de algoritmul. Aceasta se numește ordonare ideală în tăiere. În acest caz, cea mai bună mișcare are loc în partea stângă a copacului. Aplicăm DFS, prin urmare, prima căutare stânga a arborelui și du-te adânc de două ori algoritm minimax în aceeași cantitate de timp.

reguli pentru a găsi o ordonare bună

• cea mai bună mișcare se întâmplă de la cel mai mic nod
• utilizați cunoștințele de domeniu în timp ce găsiți cea mai bună mișcare
• ordinea nodurilor ar trebui să fie în așa fel încât cele mai bune noduri să fie calculate mai întâi

consultați acest tutorial Python pentru începători

coduri în 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

în acest document am văzut o componentă importantă a teoriei jocurilor. Deși performanța algoritmului minimax este bun, dar algoritmul este lent. Deci, pentru a face rapid vom folosi algoritmul de tăiere alfa-beta, care va reduce nodurile neobișnuite din arborele de decizie pentru a îmbunătăți performanța. În prezent, algoritmul rapid și bine realizat este utilizat pe scară largă.

consultați aceste cursuri de inteligență artificială și învățare automată de la învățare excelentă până la perfecționare în domeniu și master Alpha Beta tunderea și alți astfel de algoritmi.

lecturi suplimentare

1. a* algoritm de căutare în inteligență artificială (AI)
2. algoritm arbore de decizie explicat cu exemple
3. cel mai bun prim algoritm de căutare în AI | Concept, implementare, avantaje, dezavantaje
4. ce este Inteligența Artificială? Cum funcționează AI, tipurile și viitorul it?