Tăiere alfa-beta

Tăierea alfa-beta accelerează căutarea efectuată de un motor de șah, adică un program care compară mutări și răspunsuri. Căutarea poate fi imaginată ca un arbore: fiecare nod este o poziție, iar fiecare ramură este o mutare legală. Fără tăiere, programul ar examina multe continuări care în cele din urmă se dovedesc irelevante.

Metoda menține două limite în timpul căutării. Alfa este cel mai bun rezultat pe care una dintre părți îl poate garanta deja pe traseul curent. Beta este o limită creată de o alternativă pe care adversarul o are deja la dispoziție. Când o continuare este atât de slabă încât un jucător rațional nu ar alege-o niciodată, aprofundarea ei nu mai poate schimba decizia din nodul superior.

Ramura este oprită datorită unei limite logice din arbore, nu doar fiindcă o mutare pare neatrăgătoare. La aceeași adâncime și cu aceleași evaluări la limita căutării, alfa-beta întoarce aceeași alegere ca o căutare completă care presupune că ambele părți oferă cele mai bune răspunsuri.

Economia depinde foarte mult de ordinea mutărilor. Testarea timpurie a mutărilor puternice stabilește mai repede limite utile și permite oprirea mai multor ramuri fără examinare suplimentară. O funcție de evaluare, care atribuie unei poziții o estimare numerică, furnizează valorile acolo unde se încheie căutarea finită.