Tăierea alpha -beta este un algoritm de căutare care încearcă să reducă numărul de noduri evaluate într-un arbore de căutare de către algoritmul minimax . Conceput pentru jocuri antagoniste și folosit pentru jocuri cu mașini (în șah computerizat, computer go și altele). Algoritmul se bazează pe ideea că evaluarea unei ramuri a arborelui de căutare poate fi încheiată prematur (fără a calcula toate valorile funcției de evaluare) dacă s-a constatat că valoarea funcției de evaluare pentru această ramură este în orice caz mai rău decât cel calculat pentru ramura anterioară. Tăierea alfa-beta este o optimizare deoarece nu afectează corectitudinea algoritmului.
Allen Newell și Herbert Simon , folosind ceea ce John McCarthy a numit o „aproximare” [1] în 1958, au scris că tăierea alfa-beta „ pare să fi fost inventată în mod repetat ” [2] . Arthur Samuel , Richards, Hart, Levin, Edwards au propus în mod independent versiuni timpurii ale acestui algoritm [3] . De asemenea, McCarthy a prezentat idei similare la Seminarul de la Dartmouth din 1956, iar apoi, în 1961, a propus unui grup de studenți ai săi de la MIT , inclusiv lui Alan Kotok [4] , pentru cercetare . Alexander Brudno a descoperit independent algoritmul și și-a publicat rezultatele în 1963 [5] . În 1975, Donald Knuth și Ronald Moore au îmbunătățit algoritmul prin adăugarea de tăiere „beta” [6] [7] .
Avantajul tăierii alfa-beta este, de fapt, că unele dintre ramurile de subnivel ale arborelui de căutare pot fi excluse după ce cel puțin una dintre ramurile de nivel a fost luată în considerare în întregime. Deoarece tăierea are loc la fiecare nivel de cuibărit (cu excepția ultimului), efectul poate fi destul de semnificativ. Eficiența metodei este afectată semnificativ de sortarea preliminară a opțiunilor (fără enumerare sau cu enumerare la o adâncime mai mică) - la sortare, cu cât sunt luate în considerare mai multe opțiuni „bune” la început, cu atât mai multe ramuri „rele” pot fi tăiate oprit fără o analiză exhaustivă.
Algoritmi de căutare grafică | ||
---|---|---|
Metode neinformate | ||
Metode informate | ||
Comenzi rapide | ||
Arborele de întindere minim | ||
Alte |