Minimax Algoritmus Alfa-beta prořezávání

od té doby příchodem Umělé Inteligence (AI), hra byla jedna z nejzajímavějších aplikací AI.

první šachové programy napsali Claude Shannon a Alan Turing v roce 1950, téměř jakmile se počítače staly programovatelnými.

hry jako šachy, Tic-tac-toe A Go jsou zajímavé, protože nabízejí čistou abstrakci soutěže mezi oběma armádami.

právě tato abstrakce činí hraní her atraktivní oblastí pro výzkum AI.

v tomto článku projdeme základy algoritmu Minimax spolu s fungováním algoritmu.

podíváme se také na optimalizaci algoritmu minimax, alfa-beta prořezávání.

jaký je algoritmus Minimax?

Minimax je rekurzivní algoritmus, který se používá k vybrat optimální pohyb pro hráče za předpokladu, že druhý hráč je také hrát optimálně.

používá se ve hrách, jako je Tic-tac-toe, go, šachy, Isola, dáma a mnoho dalších her pro dva hráče.

takové hry se nazývají hry dokonalých informací, protože je možné vidět všechny možné pohyby konkrétní hry.

mohou existovat hry pro dva hráče, které nemají dokonalé informace, jako je Scrabble, protože soupeřův pohyb nelze předvídat.

je to podobné tomu, jak si myslíme, když hrajeme hru: „pokud udělám tento krok, pak můj soupeř může udělat pouze tyto pohyby,“ a tak dále.

Minimax se nazývá tak, protože pomáhá minimalizovat ztrátu, když si druhý hráč zvolí strategii s maximální ztrátou.

terminologie

• herní strom: jedná se o strukturu ve formě stromu skládající se ze všech možných tahů, které vám umožňují přejít ze stavu hry do dalšího stavu.

hra může být definována jako vyhledávací problém s následujícími komponenty:

• počáteční stav: zahrnuje polohu desky a ukazuje, čí pohyb je.
• nástupnická funkce: Definuje, jaké jsou právní kroky, které hráč může udělat.
• stav terminálu: je to pozice desky, když hra skončí.
• nástrojová funkce: je to funkce, která přiřadí číselnou hodnotu výsledku hry. Například v šachu nebo Tic-tac-toe je výsledek buď výhra, ztráta nebo remíza, a ty mohou být reprezentovány hodnotami +1, -1 nebo 0. Existují hry, které mají mnohem větší rozsah možných výsledků; například nástroje v backgammonu se pohybují od + 192 do -192. Funkce nástroje může být také nazývána funkcí výplaty.

jak algoritmus funguje?

existují dva hráči zapojeni do hry, s názvem MIN a MAX. Hráč MAX se snaží získat co nejvyšší skóre a MIN se snaží získat co nejnižší skóre, tj.

obecný proces algoritmu Minimax je následující:

Krok 1: Nejprve Vygenerujte celý strom hry počínaje aktuální pozicí hry až do terminálních stavů. Takto vypadá herní strom pro hru tic-tac-toe.

pojďme pochopit definovanou terminologii z hlediska výše uvedeného diagramu.

1. počáteční stav je první vrstva, která definuje, že deska je prázdná, je na řadě MAX.
2. funkce nástupce uvádí všechny možné kroky nástupce. Je definován pro všechny vrstvy ve stromu.
3. terminální stav je poslední vrstva stromu, která zobrazuje konečný stav, tj. zda hráč MAX vyhraje, prohraje nebo se spojí s protivníkem.
4. nástroje v tomto případě pro terminálové stavy jsou 1, 0 a -1, jak bylo uvedeno výše, a mohou být použity také k určení nástrojů ostatních uzlů.

Krok 2: Použijte funkci utility pro získání hodnot utility pro všechny stavy terminálu.
Krok 3: Určete nástroje vyšších uzlů pomocí nástrojů terminálových uzlů. Například v níže uvedeném diagramu máme nástroje pro terminálové stavy napsané na čtvercích.

vypočítejme nástroj pro levý uzel (červený) vrstvy nad terminálem. Vzhledem k tomu, že se jedná o pohyb hráče MIN, vybereme minimum všech nástrojů. Pro tento případ musíme vyhodnotit MIN{3, 5, 10}, což je jistě 3. Takže nástroj pro červený uzel je 3.

podobně pro zelený uzel ve stejné vrstvě budeme muset vyhodnotit MIN{2,2}, což je 2.

Krok 4: Vypočítejte užitné hodnoty pomocí listů s ohledem na jednu vrstvu najednou až do kořene stromu.
Krok 5: Nakonec všechny zálohované hodnoty dosáhnou kořene stromu, tj. V tomto okamžiku musí MAX zvolit nejvyšší hodnotu.

v našem příkladu máme pouze 3 vrstvy, takže jsme okamžitě dosáhli kořene, ale ve skutečných hrách bude mnohem více vrstev a uzlů. Takže musíme vyhodnotit MAX{3,2}, což je 3.

proto je nejlepším otevíracím tahem pro MAX levý uzel(nebo červený). Tento krok se nazývá rozhodnutí minimax, protože maximalizuje nástroj podle předpokladu, že soupeř také hraje optimálně, aby jej minimalizoval.

Abychom to shrnuli,

Minimax Rozhodnutí = MAX{MIN{3,5,10},MIN{2,2}}
= MAX.{3,2}
= 3

Psuedocode:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

Optimalizace

Hra stromy jsou obecně velmi časově náročné vytvořit, a je to jen o jednoduché hry, které to může být vytvořena v krátkém čase.

pokud existují \(b\) právní kroky, tj., \(b\) uzly v každém bodě a maximální hloubku stromu je \(m\), časová složitost algoritmus minimax je řádu \(b^m (O(b^m))\).

Chcete-li tuto situaci omezit, existuje několik optimalizací, které lze do algoritmu přidat.

naštěstí je životaschopné najít skutečné rozhodnutí minimax, aniž byste se dívali na každý uzel herního stromu. Proto odstraňujeme uzly ze stromu bez analýzy a tento proces se nazývá prořezávání.

alfa-beta prořezávání

metoda, kterou budeme hledat v tomto článku, se nazývá alfa-beta prořezávání.

pokud použijeme alfa-beta prořezávání na standardní algoritmus minimax, vrátí stejný tah jako standardní, ale odstraní (švestky) všechny uzly, které pravděpodobně neovlivňují konečné rozhodnutí.

nejprve pochopíme intuici, která za tím stojí, a pak algoritmus formalizujeme. Předpokládejme, že máme následující hru tree:

V tomto případě
Minimax Rozhodnutí = MAX{MIN{3,5,10}, MIN{2,a,b}, MIN{2,7,3}}
= MAX{3,c,2}
= 3

Ty by být překvapen!

jak bychom mohli vypočítat maximum s chybějící hodnotou? Tady je trik. MIN{2, a, B} by určitě byla menší nebo rovna 2, tj. c<=2 a proto MAX{3, C, 2} musí být 3.

otázkou nyní je, zda opravdu potřebujeme vypočítat c? Jistěže ne.

mohli jsme dospět k závěru, aniž bychom se podívali na tyto uzly. A to je místo, kde alfa-beta prořezávání přichází do obrazu.

několik definic:

Alpha: je to zatím nejlepší volba pro hráče MAX. Chceme zde získat co nejvyšší hodnotu.
Beta: Je to zatím nejlepší volba pro MIN, a musí to být nejnižší možná hodnota.

Poznámka: každý uzel musí sledovat své hodnoty alfa a beta. Alfa lze aktualizovat pouze tehdy, když je na řadě MAX, a podobně beta lze aktualizovat pouze tehdy, když je to Minova šance.

jak funguje alfa-beta prořezávání?

1. inicializujte alfa = – Nekonečno a beta = nekonečno jako nejhorší možné případy. Podmínkou prořezání uzlu je, když se alfa stane větší nebo rovna beta.
2. Začít s přiřazením počáteční hodnoty alfa a beta root a protože alfa je menší než beta nemusíme prořezávat.
3. přenese tyto hodnoty alfa a beta do podřízeného uzlu vlevo. A nyní z užitné hodnoty stavu terminálu aktualizujeme hodnoty alpha a be, takže nemusíme aktualizovat hodnotu beta. Opět nebudeme stříhat, protože stav zůstává stejný. Podobně třetí podřízený uzel také. A pak ustupovala do kořenového adresáře nastavíme alfa=3, protože to je minimální hodnota, že alfa může mít.
   
4. ALFA=3 a beta = nekonečno v kořenovém adresáři. Takže neřežeme. Přenesením do středového uzlu a výpočtem MIN{2, nekonečno} dostaneme ALFA=3 a beta=2.
5. Prořezávat druhé a třetí dítě uzly, protože alfa je nyní větší než beta.
6. Alfa v kořenu zůstává 3, protože je větší než 2. Přenesením do nejvzdálenějšího podřízeného uzlu vyhodnoťte MIN{infinity, 2}=2. Aktualizujte beta na 2 a alpha zůstává 3.
7. Prořezávat druhé a třetí dítě uzly, protože alfa je nyní větší než beta.
8. proto dostaneme 3, 2, 2 v levém, středovém a pravém min uzlu. A při výpočtu max{3,2,2} dostaneme 3. Proto, aniž bychom se podívali na čtyři listy, mohli bychom správně najít rozhodnutí minimax.

Pseudokódu (Zdroj: NPTEL Kurz):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

Závěr

Hry jsou velmi atraktivní a psaní hra-přehrávání programů je možná ještě více vzrušující. Co je Grand Prix racing pro automobilový průmysl, hraní her je pro AI.

stejně jako bychom neměli očekávat, že závodní auto, aby dokonale běžet na hrbolaté silnici, neměli bychom očekávat, že hru hraje algoritmů být ideální pro každou situaci.

stejně tak algoritmus minimax. Nemusí to být nejlepší řešení pro všechny druhy počítačových her, které potřebují mít AI.

ale vzhledem k dobré implementaci může vytvořit tvrdého konkurenta.