Alfa -beta prořezávání je vyhledávací algoritmus, který se snaží snížit počet uzlů vyhodnocovaných ve vyhledávacím stromu algoritmem minimax . Navrženo pro antagonistické hry a používané pro strojové hry (v počítačových šachách , počítačových go a dalších). Algoritmus je založen na myšlence, že vyhodnocení větve vyhledávacího stromu lze předčasně ukončit (bez výpočtu všech hodnot vyhodnocovací funkce), pokud bylo zjištěno, že hodnota vyhodnocovací funkce pro tuto větev je v v každém případě horší, než jaký byl vypočten pro předchozí větev. Alfa-beta prořezávání je optimalizace , protože neovlivňuje správnost algoritmu.
Allen Newell a Herbert Simon , používající to, co John McCarthy nazval „přiblížením“ [1] v roce 1958, napsali, že alfa-beta prořezávání „ zdá se, že bylo vynalezeno opakovaně “ [2] . Arthur Samuel , Richards, Hart, Levin, Edwards nezávisle navrhli rané verze tohoto algoritmu [3] . McCarthy také předložil podobné myšlenky na Dartmouthském semináři v roce 1956 a poté v roce 1961 navrhl skupině svých studentů na MIT , včetně Alana Kotoka [4] , pro výzkum . Alexander Brudno nezávisle objevil algoritmus a publikoval své výsledky v roce 1963 [5] . V roce 1975 Donald Knuth a Ronald Moore vylepšili algoritmus přidáním „beta“ prořezávání [6] [7] .
Výhodou alfa-beta prořezávání je ve skutečnosti to, že některé z podúrovňových větví vyhledávacího stromu lze vyloučit poté, co byla alespoň jedna z větví úrovně zvážena jako celek. Vzhledem k tomu, že k oříznutí dochází na každé úrovni vnoření (kromě poslední), může být účinek poměrně významný. Účinnost metody je výrazně ovlivněna předběžným tříděním opcí (bez výčtu nebo s výčtem do menší hloubky) - při třídění platí, že čím více „dobrých“ možností je na začátku zvažováno, tím více „špatných“ větví lze řezat bez vyčerpávající analýzy.
| Algoritmy pro vyhledávání grafů | ||
|---|---|---|
| Neinformované metody | ||
| Informované metody | ||
| Zkratky | ||
| Minimální kostra | ||
| jiný | ||