Prořezávání alfa -beta - Alpha–beta pruning

Prořezávání alfa -beta
Třída	Algoritmus vyhledávání
Nejhorší výkon
Nejlepší výkon

Prořezávání alfa -beta je vyhledávací algoritmus, který se snaží snížit počet uzlů, které jsou vyhodnoceny algoritmem minimax ve svém vyhledávacím stromu . Jedná se o kontradiktorní vyhledávací algoritmus běžně používaný pro strojové hraní her pro dva hráče ( Tic-tac-toe , Chess , Go atd.). Přestane se vyhodnocovat tah, když byla nalezena alespoň jedna možnost, která prokáže, že je tah horší než dříve zkoumaný tah. Takové pohyby nemusí být dále hodnoceny. Když je aplikován na standardní strom minimax, vrací stejný pohyb jako minimax, ale prořezává větve, které nemohou ovlivnit konečné rozhodnutí.

Dějiny

Allen Newell a Herbert A. Simon, kteří v roce 1958 použili to, co John McCarthy nazývá „aproximací“, napsali, že alfa -beta „se zdálo, že bylo několikrát znovuobjeveno“. Arthur Samuel měl ranou verzi pro simulaci dámy. Richards, Timothy Hart, Michael Levin a/nebo Daniel Edwards také vynalezli alfa -beta nezávisle ve Spojených státech . McCarthy navrhl podobné myšlenky během workshopu v Dartmouthu v roce 1956 a navrhl to skupině svých studentů, včetně Alana Kotoka na MIT v roce 1961. Alexander Brudno samostatně pojal alfa -beta algoritmus, své výsledky publikoval v roce 1963. Donald Knuth a Ronald W. Moore upřesnil algoritmus v roce 1975. Judea Pearl prokázala svou optimálnost z hlediska očekávané doby chodu stromů s náhodně přiřazenými hodnotami listů ve dvou dokumentech. Optimálnost randomizované verze alfa -beta ukázali Michael Saks a Avi Wigderson v roce 1986.

Základní myšlenka

Hra strom může představovat řadu dvou hráčů s nulovým součtem hry , jako šachy, dáma a Reversi. Každý uzel ve stromu představuje možnou situaci ve hře. Každému koncovému uzlu (výsledku) pobočky je přiřazeno číselné skóre, které určuje hodnotu výsledku hráči s dalším tahem.

Algoritmus udržuje dvě hodnoty, alfa a beta, které představují minimální skóre, o které je maximalizující hráč zajištěn, a maximální skóre, o které je minimalizující hráč zajištěn. Zpočátku je alfa záporné nekonečno a beta kladné nekonečno, tj. Oba hráči začínají se svým nejhorším možným skóre. Kdykoli je maximální skóre, o které je minimalizující hráč (tj. „Beta“ hráč) ujištěn, menší než minimální skóre, které má maximalizující hráč (tj. „Alfa“ hráč) zajištěno (tj. Beta <alpha), maximalizační hráč nemusí brát v úvahu další potomky tohoto uzlu, protože ve skutečné hře nebudou nikdy dosaženi.

Abychom to ilustrovali na skutečném příkladu, předpokládejme, že někdo hraje šachy a je na řadě. Pohyb „A“ zlepší pozici hráče. Hráč pokračuje v hledání tahů, aby se ujistil, že lepší nebyl vynechán. Tah „B“ je také dobrý tah, ale hráč si pak uvědomí, že to umožní soupeři vynutit mat dvěma tahy. Není tedy nutné brát v úvahu další výsledky hraní tahu B, protože soupeř si může vynutit výhru. Maximální skóre, které mohl soupeř vynutit po tahu „B“, je záporná nekonečnost: ztráta pro hráče. To je méně než minimální pozice, která byla dříve nalezena; tah „A“ nevede k vynucené ztrátě dvěma tahy.

Vylepšení oproti naivnímu minimaxu

Ukázka prořezávání alfa – beta. Šedé podstromy není třeba zkoumat (když jsou pohyby hodnoceny zleva doprava), protože je známo, že skupina podstromů jako celek poskytuje hodnotu ekvivalentního podstromu nebo horšího, a jako taková nemůže ovlivnit konečný výsledek. Maximální a minimální úroveň představují obrat hráče a protivníka.

Výhoda prořezávání alfa – beta spočívá ve skutečnosti, že větve vyhledávacího stromu lze eliminovat. Tímto způsobem lze dobu hledání omezit na „slibnější“ podstrom a současně lze provést hlubší vyhledávání. Stejně jako jeho předchůdce patří do větve a vázané třídy algoritmů. Optimalizace snižuje efektivní hloubku na mírně více než polovinu jednoduchého minimaxu, pokud jsou uzly vyhodnoceny v optimálním nebo téměř optimálním pořadí (nejlepší volba pro stranu v pohybu seřazenou nejprve v každém uzlu).

S (průměr nebo konstantní) větvení faktor o b a vyhledávací hloubky d vrstev , je maximální počet uzlových poloh listů vyhodnocena (pokud je krok uspořádání je pessimal ) je O ( b x b x ... x b ) = O ( b ^d ) - stejné jako jednoduché vyhledávání minimaxů. Pokud je pořadí tahů pro vyhledávání optimální (což znamená, že nejlepší tahy jsou vždy prohledávány jako první), počet vyhodnocených pozic listových uzlů je pro lichou hloubku a O přibližně O ( b × 1 × b × 1 × ... × b ). ( b × 1 × b × 1 × ... × 1) pro rovnoměrnou hloubku, popř . V druhém případě, kde je vrstva hledání rovnoměrná, se efektivní faktor větvení sníží na druhou odmocninu , nebo, ekvivalentně, hledání může jít dvakrát hlouběji se stejným množstvím výpočtu. Vysvětlení b × 1 × b × 1 × ... je, že všechny tahy prvního hráče musí být studovány, aby se našel ten nejlepší, ale pro každý je k vyvrácení všech kromě prvního (a nejlepší) tah prvního hráče - alfa – beta zajišťuje, že není třeba brát v úvahu žádné pohyby druhého hráče. Když jsou uzly zvažovány v náhodném pořadí (tj. Algoritmus randomizuje), asymptoticky, očekávaný počet uzlů vyhodnocených v jednotných stromech s binárními hodnotami listů je . U stejných stromů, kdy jsou hodnoty přiřazeny k hodnotám listů nezávisle na sobě a řekněme, že nula a jedna jsou stejně pravděpodobné, je očekávaný počet vyhodnocených uzlů mnohem menší než práce vykonaná zmíněným randomizovaným algoritmem. výše, a je opět optimální pro takové náhodné stromy. Jsou-li hodnoty listové zvoleny nezávisle na sobě, ale z intervalu jednotně náhodně, očekávaný počet uzlů hodnocena zvyšuje se v limitu, který je opět optimální pro tento druh náhodné stromy. Všimněte si, že skutečná práce pro „malé“ hodnoty je lépe aproximována pomocí . ${\ Displaystyle O (b^{d/2}) = O ({\ sqrt {b^{d}}})}$ ${\ Displaystyle \ Theta ((((b-1+{\ sqrt {b^{2}+14b+1}})/4)^{d})}$ ${\ displaystyle \ Theta ((b/2)^{d})}$ ${\ Displaystyle [0,1]}$ ${\ displaystyle \ Theta (b^{d/log (d)})}$ ${\ displaystyle d \ to \ infty}$ ${\ displaystyle d}$ ${\ displaystyle 0,925d^{0,747}}$

Šachový program, který prohledává čtyři vrstvy s průměrem 36 poboček na uzel, vyhodnotí více než jeden milion koncových uzlů. Optimální alfa-beta švestka by odstranila všechny kromě 2 000 koncových uzlů, což je snížení o 99,8%.

Animovaný pedagogický příklad, který se pokouší být přátelský k člověku nahrazením počátečních nekonečných (nebo libovolně velkých) hodnot prázdnotou a vyhýbáním se používání zjednodušování kódování negamax .

Během alfa – beta obvykle na podstromech dočasně převládá výhoda prvního hráče (když je mnoho tahů prvního hráče dobré a v každé hloubce vyhledávání je první tah zkontrolovaný prvním hráčem adekvátní, ale všechny reakce druhého hráče jsou nutné zkuste najít vyvrácení), nebo naopak. Tato výhoda může během vyhledávání mnohokrát přepínat strany, pokud je pořadí přesunutí nesprávné, pokaždé to vede k neúčinnosti. Jelikož počet hledaných pozic exponenciálně klesá každým pohybem blíže k aktuální pozici, stojí za to vynaložit značné úsilí na třídění raných tahů. Vylepšené řazení v jakékoli hloubce exponenciálně sníží celkový počet prohledávaných pozic, ale řazení všech pozic v hloubkách blízko kořenového uzlu je relativně levné, protože jich je tak málo. V praxi je pořadí přesunů často určeno výsledky dřívějších menších vyhledávání, například prostřednictvím iterativního prohlubování .

Tento algoritmus lze navíc triviálně upravit tak, aby kromě skóre vrátil celou hlavní variaci . Některé agresivnější algoritmy, jako je MTD (f) , takovou úpravu nedovolují snadno.

Pseudo kód

Pseudokód pro minimax omezený hloubkou s prořezáváním alfa – beta je následující:

Implementace prořezávání alfa – beta mohou být často vymezeny tím, zda jsou „soft-fail“ nebo „hard-fail“. U alfa-beta s funkcí fail-soft může funkce abecedy vrátit hodnoty (v), které překračují (v <α nebo v> β) hranice α a β nastavené jejími argumenty volání funkce. Ve srovnání, alfa-beta tvrdá pro selhání omezuje návratovou hodnotu funkce na inkluzivní rozsah α a β. Hlavním rozdílem mezi implementacemi soft-fail a hard-fail-hard je, zda jsou α a β aktualizovány před nebo po kontrole cutoff. Pokud jsou aktualizovány před kontrolou, pak mohou překročit počáteční meze a algoritmus je měkký na selhání.

Následující pseudokód ilustruje variantu hard-fail.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then
                break (* α cutoff *)
            β := min(β, value)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Následující pseudokód ilustruje neúspěšnou alfa-beta.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if value ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if value ≤ α then
                break (* α cutoff *)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Heuristická vylepšení

Dalšího zlepšení lze dosáhnout bez obětování přesnosti použitím heuristiky řazení k prohledávání dřívějších částí stromu, u nichž je pravděpodobné, že vynutí omezení alfa -beta. Například v šachu lze tahy, které zachycují figurky, zkoumat před tahy, které ne, a tahy, které dosáhly vysokého skóre v dřívějších průchodech analýzou stromu hry, mohou být vyhodnoceny před ostatními. Další běžnou a velmi levnou heuristikou je zabijácká heuristika , kde je vždy nejprve zkoumán poslední tah, který způsobil beta-cutoff na stejné úrovni stromu při hledání stromu. Tuto myšlenku lze také zobecnit na sadu vyvracecích tabulek .

Hledání alfa -beta může být ještě rychlejší, když vezmeme v úvahu pouze úzké vyhledávací okno (obecně určeno odhadem na základě zkušeností). Toto je známé jako aspirační vyhledávání . V extrémním případě se vyhledávání provádí s alfa a beta rovno; technika známá jako vyhledávání v nulovém okně, vyhledávání v nulovém okně nebo vyhledávání ve skautu . To je zvláště užitečné pro vyhledávání výhra/ztráta blízko konce hry, kde extra hloubka získaná z úzkého okna a jednoduchá funkce vyhodnocení výhry/prohry může vést k přesvědčivému výsledku. Pokud vyhledávání aspirace selže, je snadné zjistit, zda selhal vysoko (vysoký okraj okna byl příliš nízko) nebo nízko (spodní okraj okna byl příliš vysoko). To poskytuje informace o tom, jaké hodnoty okna mohou být užitečné při opětovném hledání pozice.

Časem byla navržena další vylepšení a myšlenka Johna Fishburna na Falphabeta (neúspěšná alfa – beta) je téměř univerzální a je již výše začleněna v mírně upravené podobě. Fishburn také navrhl kombinaci zabijácké heuristiky a hledání v nulovém okně pod názvem Lalphabeta („poslední tah s minimálním hledáním alfa – beta okna“).

Jiné algoritmy

Protože algoritmus minimaxu a jeho varianty jsou ze své podstaty nejprve hloubkové , používá se ve spojení s alfa – beta obvykle taková strategie, jako je iterativní prohlubování , aby bylo možné vrátit přiměřeně dobrý tah, i když je algoritmus přerušen před dokončením provádění. Další výhodou použití iterativního prohlubování je to, že vyhledávání v mělčích hloubkách poskytuje rady k uspořádání tahů, stejně jako mělké odhady alfa a beta, že oba mohou pomoci vytvářet mezní hodnoty pro vyhledávání ve větší hloubce mnohem dříve, než by jinak bylo možné.

Algoritmy jako SSS* naopak používají strategii best-first . To je může potenciálně učinit časově efektivnějšími, ale obvykle s vysokými náklady na prostorovou efektivitu.

Viz také

Reference

Bibliografie

George T. Heineman; Gary Pollice; Stanley Selkow (2008). „Kapitola 7: Hledání cesty v AI“. Algoritmy v kostce . Oreilly Media . s. 217–223. ISBN 978-0-596-51624-6.
Judea Pearl , Heuristika , Addison-Wesley, 1984
John P. Fishburn (1984). „Příloha A: Některé optimalizace vyhledávání α-β“. Analýza zrychlení v distribuovaných algoritmech (revize doktorské práce z roku 1981) . UMI Research Press. s. 107–111. ISBN 0-8357-1527-2.

Languages

In other projects