Alfa-beta ořezávání (angl. alpha-beta pruning) je vylepšení algoritmu minimax, které v průměrném případě zrychluje jeho běh. Je založeno na pozorování, že pokud právě zpracovávaný půltah už nemůže obstát v konkurenci s jiným, nemusíme dál prohledávat jeho důsledky.
Metoda byla pojmenována alfa-beta, protože v ní rozšiřujeme původní minimaxový algoritmus o dvě další hodnoty alfa a beta, které nám určují potřebné meze. Z tohoto pohledu jde o algoritmus používající metodu větví a mezí, kde meze jsou dvě, každá pro jednoho hráče.
Účinnost ořezání nepotřebných větví lze zvýšit vhodnou volbou pořadí, v němž jsou procházeny. Nejvýhodnější je projít nejprve ty větve, které by měly dát podle nějakého rychlého (ve srovnání s procházení kompletním minimaxem) odhadu nejlepší výsledky. Další možností, jak odlišit lepší tahy od horších je tzv. kaskádová metoda (anglicky iterative deepening depth-first search), která spočívá v tom, že pokud bychom chtěli prohledávat do hloubky n půltahů, budeme algoritmus postupně pouštět na hloubku 1, 2, …, n půltahů a v každé další iteraci budeme na tahy pouštět vylepšený minimax v tom pořadí, v jakém nám předchozí iterace ohodnotila tahy. V průběhu algoritmu (mezi iteracemi i v rámci iterace) se takové informace o tazích ukládají do transpozičních tabulek.
Pokud budeme mít při volbě pořadí procházení tahů smůlu, alfa-beta ořezávání běh nezrychlí vůbec. Naopak, při výběru optimálního tahu na začátku se dosažená hloubka prohledávání (při stejném čase) zdvojnásobí.
Související články
| Zdroj dat | cs.wikipedia.org |
|---|---|
| Originál | cs.wikipedia.org/wiki/Alfa-beta_ořezávání |
