Alfa-beta ořezávání

Technology
12 hours ago
8
4
2
Avatar
Author
Albert Flores

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

5 min read
Share this post:
Like it 8

Leave a Comment

Please, enter your name.
Please, provide a valid email address.
Please, enter your comment.
Enjoy this post? Join Cesko.wiki
Don’t forget to share it
Top