Alfa-beta ořezávání

Ukázka alpha-beta ořezávání. Šedé části stromu nemusí algoritmus procházet (prochází-li strom zleva doprava), protože nemohou jakkoli ovlivnit výsledek. 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. +more 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

Minimax * Negamax * MTD(f)

Kategorie:Optimalizační algoritmy a metody Kategorie:Grafové algoritmy Kategorie:Vyhledávací algoritmy