Decuparea alfa beta

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.

Istorie

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] .

Optimizare Minimax

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ă.

Note

1. ↑ McCarthy J. Human Level AI Is Harder Than It Seemed în 1955 (LaTeX2HTML 27 noiembrie 2006). Data accesului: 20 decembrie 2006. Arhivat din original la 8 aprilie 2012. (nedefinit)
2. ↑ Newell A. , Simon HA Computer Science as Empirical Inquiry: Symbols and Search  //  Communications of the ACM, Vol. 19, nr. 3: jurnal. - 1976. - Martie. Arhivat din original pe 28 iunie 2007.
3. ↑ Richards DJ, Hart TP The Alpha-Beta Euristic (AIM-030) . Massachusetts Institute of Technology (4 decembrie 1961 până la 28 octombrie 1963). Consultat la 21 decembrie 2006. Arhivat din original pe 8 aprilie 2012. (nedefinit)
4. ↑ Kotok A. MIT Artificial Intelligence Memo 41 (XHTML 3 decembrie 2004). Preluat la 1 iulie 2006. Arhivat din original la 8 aprilie 2012. (nedefinit)
5. ↑ Marsland TA Computer Chess Methods (PDF) din Encyclopedia of Artificial Intelligence / S. Shapiro (editor) (PDF) 159-171. J. Wiley & Sons (mai 1987). Consultat la 21 decembrie 2006. Arhivat din original pe 8 aprilie 2012. (nedefinit)
6. ↑ Knuth DE, Moore RW An Analysis of Alpha-Beta Pruning  (neopr.)  // Artificial Intelligence Vol. 6, nr. 4. - 1975. - S. 293-326 . , retipărit ca „Partea a 9-a” a cărții: Knuth DE Selected Papers on Analysis of Algorithms  (engleză) . — Stanford, California: Centrul pentru Studiul Limbii și Informației - Note de curs CSLI, nr. 102, 2000. ISBN 1-57586-212-3 .
7. ↑ Abramson B. Control Strategies for Two-Player Games  (nedefinit)  // ACM Computing Surveys, Vol. 21, nr. 2. - 1989. - iunie ( vol. 21 ). - S. 137 . - doi : 10.1145/66443.66444 . Arhivat din original pe 20 august 2008. Copie arhivată (link indisponibil) . Consultat la 25 octombrie 2009. Arhivat din original pe 20 august 2008. (nedefinit)