Tăierea alfa-beta

Tăierea alfa-beta
Tăierea alfa-beta. Puteți ignora subarborele potrivit, deoarece știm deja că are o valoare de 1 sau mai puțin și, prin urmare, nu conține cea mai bună soluție
Clasă	Algoritm de căutare
Cel mai rău caz din punct de vedere temporal	$O(b^{d})$ ${\ displaystyle O (b ^ {d})}$ ${\ displaystyle O (b ^ {d})}$
Caz optim în timp	$O\left({\sqrt {b^{d}}}\right)$ ${\ displaystyle O \ left ({\ sqrt {b ^ {d}}} \ right)}$ ${\ displaystyle O \ left ({\ sqrt {b ^ {d}}} \ right)}$
Manual

Tunderea alfa-beta este un algoritm de căutare care reduce drastic numărul de noduri care trebuie evaluate în arborele de căutare al algoritmului minimax . Este utilizat în mod obișnuit în programele de jocuri automate pe computer, pentru jocuri pe rând cu doi sau mai mulți jucători ( Tic-tac-toe , Go , Șah etc.) și constă în încheierea evaluării unei posibile mișcări imediat ce este a dovedit că este în orice caz mai rău decât o mutare.evaluată deja anterior: este o optimizare sigură, care nu modifică rezultatul final al algoritmului la care este aplicat.

Funcționarea algoritmului

Tunderea alfa-beta se bazează pe două valori, numite alfa și beta, care reprezintă, în fiecare punct al copacului, cea mai bună și cea mai proastă poziție care poate fi atinsă. Mai precis, dacă A este jucătorul care maximizează și B jucătorul care minimizează :

α este scorul minim pe care îl poate atinge A , pornind de la poziția în cauză; la începutul algoritmului este setat la -∞. În timpul calculului, α coincide cu valoarea celei mai bune mișcări posibile calculate în prezent pentru A.
β este scorul maxim pe care B îl poate atinge pornind din aceeași poziție; la începutul algoritmului este setat la + ∞. În timpul calculului, β coincide cu valoarea celei mai bune mișcări posibile calculate în prezent pentru B.

Căutarea continuă ca o căutare minimax normală, în care totuși valorile α și β pentru fiecare nod sunt actualizate pe măsură ce căutarea se aprofundează. Dacă în timpul căutării, pentru un anumit nod α devine mai mare decât β , căutarea sub acel nod se oprește și programul trece la un alt subarbore, deoarece poziția acelui nod nu poate fi atinsă în timpul jocului normal (adică de la acea poziție înainte, A ar pierde inevitabil chiar dacă a jucat să câștige, ceea ce într-un joc competitiv este absurd și cu siguranță nu rezultatul pe care îl dorim). Se spune că subarborele corespunzător nodului cu α și β „inversat” este tăiat , de unde și numele algoritmului însuși.

Îmbunătățiri față de minimaxul simplu

Beneficiul cheie al tăierii alfa-beta este eliminarea ramurilor întregi ale arborelui de cercetare; acest lucru permite limitarea căutării la cele mai promițătoare mișcări, aprofundând în continuare evaluarea lor în timpul dat. La fel ca predecesorii săi, tăierea alfa-beta este, de asemenea, un algoritm ramificat și legat .

Având în vedere un factor de ramură (mediu sau constant) b și o adâncime de căutare de d mișcări, numărul maxim de mișcări evaluate (atunci când ordinea arborelui este rău) este O ( b * b * ... * b ) = O ( b ^d ) - la fel ca o căutare simplă minimax. Dacă, pe de altă parte, ordonarea este perfectă (cele mai bune mișcări sunt întotdeauna evaluate mai întâi), numărul de poziții căutate devine O ( b * 1 * b * 1 * ... * b ) pentru adâncimea d uniformă și O ( b * 1 * b * 1 * ... * 1) pentru d impar, adică

$O(b^{d/2})=O({\sqrt {b^{d}}})$ ${\ displaystyle O (b ^ {d / 2}) = O ({\ sqrt {b ^ {d}}})}$ ${\ displaystyle O (b ^ {d / 2}) = O ({\ sqrt {b ^ {d}}})}$ .

Astfel, în cel mai bun caz, factorul efectiv de ramificare este redus la rădăcina sa pătrată , adică căutarea poate atinge dublul adâncimii cu același număr de calcule ^[1] . Motivul pentru b * 1 * b * 1 * ... este că pentru jucătorul A, toate mișcările posibile trebuie evaluate pentru a găsi cea mai bună, în timp ce cunoașterea celei mai bune mișcări a lui B este suficientă pentru a arunca toate mișcările lui A minus cea mai bună.; principiul alfa-beta garantează că nu este necesar să se ia în considerare nicio altă mișcare de B. În cazul șahului, unde factorul de ramificare este de aproximativ 40 și având în vedere o adâncime de căutare de 12 spire, relația dintre cel mai bun caz și cel mai rău caz este de aproximativ 40 ⁶ , adică o căutare optimă alfa-beta pentru șah este de 4 miliarde de ori mai rapidă decât simpla minimax.

Prin urmare, întrucât numărul pozițiilor care urmează să fie evaluate scade exponențial odată cu scăderea adâncimii, merită depuse chiar eforturi mari pentru a păstra arborele de căutare cât mai ordonat: chiar și un sortare parțială poate îmbunătăți performanța de milioane de ori. Prin urmare, în practică, înainte de căutarea propriu-zisă, se efectuează o primă „pre-căutare” foarte superficială pentru a obține un prim arbore care este deja parțial ordonat, pe care căutarea propriu-zisă se va ocupa de aprofundarea și completarea până la adâncimea stabilită.

În programele de jocuri pe computer, această căutare prealabilă nu este, în general, necesară: de fapt, se adoptă o procedură de rafinare ulterioară, astfel că la fiecare nouă mișcare calculul reîncepe aprofundând subarborele ales de jucătorul de serviciu, deja parțial ordonat de căutări precedent

În mod normal, pe parcursul algoritmului, subarborii sunt temporar dominați de avantajul unuia dintre cei doi jucători; acest lucru se întâmplă de obicei atunci când un jucător poate face multe mișcări bune și la fiecare iterație primele mișcări controlate sunt deja bune, în timp ce toate mișcările celuilalt necesită o analiză mai aprofundată pentru a fi judecată). De asemenea, se poate întâmpla ca acest avantaj aparent să treacă adesea de la un jucător la altul, în cazul în care arborele de căutare al jocului este slab ordonat.

Ameliorări euristice

Puteți îmbunătăți performanța fără a sacrifica acuratețea rezultatelor folosind euristica de sortare pentru a căuta rapid părțile copacului care sunt cele mai susceptibile de a forța imediat tăieturi alfa-beta: de exemplu, în șah examinați mișcările care iau piesele mai întâi sau cine au obținut scoruri foarte mari în prima căutare superficială. O altă optimizare euristică foarte comună și ieftină este euristica ucigașă , prin care ultima mișcare care a provocat o tăiere beta la același nivel în copac este întotdeauna căutată mai întâi; această optimizare poate fi generalizată la un set de tabele de respingere .

Căutarea alfa-beta poate fi accelerată în continuare luând în considerare o fereastră de căutare foarte îngustă (diferența α - β ), de obicei cu o valoare ipotezată bazată pe experiență; această tehnică este cunoscută sub numele de căutare a aspirației . În caz extrem, căutarea se efectuează cu α = β , rezultând tehnica cunoscută sub numele de căutare cu ferestre zero, căutare cu ferestre nule sau căutare cercetă . Această tehnică este deosebit de eficientă la sfârșitul jocului, atunci când încerci să faci mat. Dacă o căutare de aspirație eșuează, este imediat să știm dacă intervalul ales a fost prea mare sau prea mic, obținându-se o nouă ipoteză a intervalului alfa-beta pentru o posibilă nouă căutare pe aceeași poziție.

Alți algoritmi de căutare

În literatura de specialitate sunt cunoscuți algoritmi de căutare similari mai rapizi și mai avansați, capabili în egală măsură să calculeze exact valoarea minimă, precum Negascout și MTD-f . Deoarece algoritmul minimax și variantele sale sunt în mod inerent căutarea adâncimii, o strategie de aprofundare iterativă este de obicei adoptată împreună cu tăierea alfa-beta, care permite căutarea să ofere o mișcare rezonabilă, chiar dacă căutarea este oprită înainte de termen. Un alt avantaj al aprofundării iterative este că vă permite să sortați parțial arborele de căutare, ceea ce vă permite să tăiați mai repede ramurile inutile, economisind timp.

Pe de altă parte, există și algoritmi precum SSS * , care analizează în schimb arborele posibilelor mișcări pornind de la cele mai bune. Acest lucru le poate face mai eficiente din punct de vedere al calculului, dar costă foarte mult din punct de vedere al spațiului de memorie ocupat.

Pseudo cod

Iată o formă pseudocodică a algoritmului de tăiere alfa-beta. Este numit de exemplu funcția „minimax”.

 01 alpha_beta FUNCȚIE (nod, adâncime, α, β, maximizare)
02 IF adâncime = 0 SAU nodul este terminal
03 RETURN valoarea euristică a nodului
04 SE maximizează
05 v: = -∞
06 PENTRU FIECARE copil al nodului
07 v: = max (v, alpha_beta (copil, adâncime - 1, α, β, FALS))
08 α: = max (α, v)
09 IF β ≤ α
10 OPRIȚI CICLUL (* tăiați conform β *)
11 RETURN v
12 ALTĂ
13 v: = + ∞
14 PENTRU FIECARE copil al nodului
15 v: = min (v, alpha_beta (copil, adâncime - 1, α, β, TRUE))
16 β: = min (β, v)
17 IF β ≤ α
18 OPRIȚI CICLUL (* tăiați conform α *)
19 RETURN v

(* memento inițial *)
alpha_beta (origine, adâncime, - ∞ , + ∞, TRUE)

Notă

^ SJ Russell și P. Norvig (2003). Inteligența artificială: o abordare modernă . A doua ediție, Prentice Hall.

Elemente conexe

linkuri externe

[1] SJ Russell și P. Norvig (2003). Inteligența artificială: o abordare modernă . A doua ediție, Prentice Hall.

[1]