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.
| Property | Value |
|---|
| dbpedia-owl:abstract
|
- 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í.
|
| dbpedia-owl:thumbnail
| |
| dbpedia-owl:wikiPageID
| |
| dbpedia-owl:wikiPageLength
| |
| dbpedia-owl:wikiPageOutDegree
| |
| dbpedia-owl:wikiPageRevisionID
| |
| dbpedia-owl:wikiPageWikiLink
| |
| dbpedia-owl:wikiPageWikiLinkText
|
- alfa-beta ořezávání
- Alfa-beta ořezávání
|
| dcterms:subject
| |
| rdfs:comment
|
- 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.
|
| rdfs:label
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is dbpedia-owl:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
