Hranie strategických hier s algoritmom Minimax

V tejto lekcii preskúmame populárny algoritmus nazývaný minimax . Dozvieme sa tiež niektoré z jeho priateľských doplnkových funkcií v okolí, ako sú heuristické skóre , iteračné prehlbovanie a prerezávanie alfa-beta . Pomocou týchto techník môžeme vytvoriť flexibilnejšieho a výkonnejšieho agenta hrania hier. Bude schopný konkurovať mnohým výzvam, vrátane strategickej hry Isolation.

V mojom predchádzajúcom príspevku Ako vyhrať sudoku sme sa naučili, ako naučiť počítače vyriešiť hádanku Sudoku. Ak ste ju ešte nečítali, dočítajte sa rýchlo. Ale to bol naozaj iba spôsob, ako si namočiť nohy, než sa pustíte do zložitejších metód agentov hrania hier. Najmä tie metódy, ktoré môžu robiť strategické ťahy proti súperovi!

Nenechajte sa uviaznuť

Isolation (alebo Isola) je ťahová strategická stolová hra, kde sa dvaja hráči pokúsia svojho súpera obmedziť na šachovnici podobnej šachovnici 7x7. Nakoniec už nemôžu urobiť ťah (a tým ich izolovať).

Každý hráč má jednu figúrku, s ktorou sa môže pohybovať ako šachová kráľovná - hore-dole, zľava-doprava a diagonálne. Existujú tri podmienky, za ktorých je možné kúsky premiestňovať -

  1. Svoj kúsok nemôžu umiestniť na už navštívené námestie.
  2. Nemôžu prechádzať cez už navštívené námestia (stláčanie cez ne diagonálne je v poriadku).
  3. Nemôžu navzájom prechádzať cez kus.

Na obrázku vyššie vidíte z čiernych štvorcov, že obaja hráči umiestnili svoje figúrky na rôzne časti hracej plochy. Ale ako hra postupovala, ukazuje to, že žltý hráč má ešte tri možné ťahy. Hore a doprava, vpravo jeden štvorec a vpravo dva štvorce. Modrý hráč je však mimo možností. Preto je tu žltý hráč víťazom.

Teraz sa to môže javiť ako jednoduchá hra - a úprimne povedané, je. Nie je to tak, že hráme poker alebo Starcraft. Napriek tomu stále existuje obrovské množstvo možných ťahov, ktoré môže hráč kedykoľvek v priebehu hry vykonať.

V hlavolamoch ako je Sudoku existuje „odpoveď“, ktorú chceme vyriešiť. Pokiaľ však ide o strategické hry, neexistuje žiadna odpoveď.

Hráme proti inému súperovi - ako proti človeku, počítaču alebo mačke. To si vyžaduje stratégiu a premyslenie, ako môže hra dopadnúť, keď sa bude vyvíjať.

Takéto hry sa môžu vyvíjať a produkovať absurdné množstvo možných výsledkov. Musíme si teda premyslieť, ako môžeme zvoliť najlepší možný krok bez toho, aby sme strávili čas potrebný na osídlenie Zeme mačkami.

Dobre, už žiadne mačky!

Mocný Minimax a priatelia

Teraz, keď viete, ako hrať Isolation, sa pozrime na to, ako môžeme použiť algoritmus minimax ; základ v komunite AI. Ďalej sa pozrieme na heuristické skóre , iteratívne prehlbovanie a prerezávanie alfa-beta . Spolu s nimi môžeme vybudovať konkurencieschopného agenta AI.

Minimax

Algoritmus minimax je veľmi populárny na výučbu agentov AI, ako hrať ťahové strategické hry. Dôvod je ten, že zohľadňuje všetky možné ťahy, ktoré môžu hráči kedykoľvek v priebehu hry podniknúť. S touto informáciou sa potom pokúsi minimalizovať výhodu súperovho hráča a maximalizovať agenta na každom kroku, ktorý agent AI dostane do hry.

Ako to teda vyzerá?

Podobne, ako by agent AI hral hru ako Sudoku, môžeme vymodelovať ďalšie možné pohyby, ktoré môže ktorýkoľvek hráč vykonať, pomocou vyhľadávacieho stromu . Budeme však musieť použiť vyhľadávací strom s premenlivými šírkami - alebo inak povedané so šírkou na úrovni stromu. Dôvod je ten, že existuje variabilný počet ťahov, ktoré môže každý hráč kedykoľvek v priebehu hry vykonať.

Strom zobrazený vyššie predstavuje ďalšie ťahy dostupné počas hry Isolation. Má mriežku 2x3, pričom pravý dolný štvorec je nedosiahnuteľný. Ako vidíte, obaja hráči sú modrý kruh a červený kríž.

Horná časť stromu (koreňový uzol) ilustruje ťah červeného hráča. Stredná úroveň zobrazuje ďalšie možné ťahy modrého hráča. A tretia úroveň zobrazuje možné ťahy červeného hráča, vzhľadom na predchádzajúci ťah modrého hráča.

Každý stav hry alebo uzol v strome obsahuje informácie o tom, ktorý hráč má z potenciálneho ťahu najviac.

Teraz by vás mohlo zaujímať, čo to sakra sú tie trojuholníky pod každým pohybom?

Trojuholník nadol predstavuje miesto v strome, kde minimax minimalizuje výhodu súpera. Zatiaľ čo smerom hore sú trojuholníky miestom, kde minimax maximalizuje výhodu agenta.

Ale minimax môže poznať výhodu každého hráča iba vtedy, ak pozná cesty v strome, ktoré vedú k víťazstvu ktoréhokoľvek z hráčov. To znamená, že minimax musí prechádzať na samé dno stromu pri každej možnej sérii pohybov. Ďalej musí priradiť nejaké skóre (napr. +1 za výhru a -1 za prehru) a šíriť tieto čísla hore stromom. Týmto spôsobom má každý stav hry alebo uzol v strome informácie o tom, ktorý hráč môže z potenciálneho ťahu získať najviac.

Na tomto obrázku môžeme urobiť niekoľko postrehov. Prvý minimax priraďuje číslo konečným výsledkom hry v listových uzloch . Potom ich rozšíri nahor cez strom a vykoná minimalizácie a maximalizácie na ceste. Keď minimax dokončí vyplnenie stromu, kedykoľvek bude na rade AI agent, bude vedieť, ktoré ťahy pravdepodobne povedú k výhre alebo prehre.

Druhá úroveň za koreňovým uzlom zobrazuje ďalšie možné ťahy modrého hráča (nášho agenta AI). Náš agent chce počas svojho kola maximalizovať dostupné skóre. Vybral by si teda ťah predstavovaný v uzle úplne vpravo za koreňovým uzlom. Super super!

Má však zmysel jednoducho priradiť k výsledkom hry +1 alebo -1? Nemalo by toto skóre brať do úvahy spôsob výhry alebo prehry v hre?

Varovanie spojlera: odpoveď je áno!

Heuristické skóre

Vo svete strategických hier je heuristické skóre v podstate subjektívnou hodnotou, ktorú pripisujeme určitému stavu hry. Táto hodnota je založená na našom chápaní toho, ako sa v hre vyhráva a prehráva. Zvolením dobre premysleného heuristického skóre dokážeme naučiť nášho agenta AI, ako čo najlepšie zvoliť ďalšie kroky pri hraní hry Isolation.

Teraz existuje pravdepodobne neobmedzený počet heuristických skóre, ktoré by sme mohli vymyslieť. Ale tu sa pozrieme iba na niektoré z nich, okrem naivného skóre (NS) +1 a -1.

Jedným z nápadov by mohlo byť spočítanie všetkých ďalších možných ťahov, ktoré má každý hráč v danom okamihu, pretože viac možných ťahov znamená menšiu šancu na izoláciu. Nazveme to skóre otvoreného ťahu (OMS) .

Ďalším nápadom by mohlo byť použitie hodnoty získanej z OMS a odpočítanie počtu ďalších možných ťahov, ktoré má súper. Dôvodom je, že každý hráč chce zvýšiť počet ťahov a zároveň znížiť počet súperových. Nazveme to vylepšené skóre (IS) .

Vyššie uvedený obrázok zobrazuje mieru výhier mnohých simulovaných izolačných hier hraných medzi agentmi AI s použitím rôznych heuristických skóre. Teraz môžete vidieť, ako odlišné boli naše skóre počas skutočného hrania hry. Ale boli tu nejaké heuristické skóre, ktoré prekonali tie, ktoré sme prišli

Je zaujímavé, že prvé dva sú takmer úplne rovnaké ako vylepšené skóre. Budeme ich nazývať agresívne vylepšené skóre (AIS) a super agresívne vylepšené skóre (SAIS) . Ale medzi týmto skóre a originálom je mierny rozdiel. Prvé dve skóre použijú pri výpočte vylepšeného skóre faktor dva a tri na hodnotu, ktorú odčítate (počet ťahov, ktoré má súper k dispozícii).

Môžete zistiť optimálny „agresívny faktor“, ktorý sa použije pri výpočte tohto skóre!

Ďalšie varovanie spojlera - existujú lepšie hodnoty.

Čo však v prípade, ak prídeme s heuristickým skóre, ktoré je potrebné vypočítať veľa času? Čo ak je strom obrovský? Bude mať náš agent AI dostatok času na nájdenie ďalších najlepších ťahov, zatiaľ čo bude počas hry dostatočne reagovať?

Iteratívne prehlbovanie

Teraz vieme, že náš agent AI môže modelovať všetky možné pohyby pomocou vyhľadávacieho stromu a zodpovedajúceho heuristického skóre jeho uzlov. Ale bohužiaľ, pri hraní Isolation bude náš strom obrovský. Hľadanie v strome a výpočet týchto hodnôt by trvalo viac času, ako je rokov od veľkého tresku!

Zadajte iteratívne prehlbovanie - stratégiu riadenia času pre agentov hrajúcich hry. Pomocou tejto metódy môžeme skrátiť čas výpočtu a vyhľadávania na maximálny čas podľa nášho výberu. Týmto spôsobom môže náš agent umelej inteligencie reagovať minimálne tak rýchlo, ako to dokáže človek.

Ako však funguje iteračné prehlbovanie?

Umožňuje minimaxu pohybovať sa po úrovniach a počítať heuristické skóre do určitého časového limitu. Po dosiahnutí tohto časového limitu je agent AI nútený použiť najlepší pohyb, ktorý objavil, pričom sa pohyboval stále hlbšie a hlbšie dolu stromom.

Teraz to poskytuje určitý náhľad na to, aké ťažké to môže byť. Vytvorenie agenta AI, ktorý je dostatočne inteligentný a reaguje na strategické hry, môže byť dosť zložité, dokonca aj pre čarodejníkov z oblasti AI. Najmä ak takéto hry obsahujú svet možností.

Počet ťahov, ktoré si agent AI dokáže „predstaviť“, bohužiaľ, je v budúcnosti obmedzený. Je teda možné, že by mohlo urobiť rozhodnutie, ktoré povedie k jeho zániku. Toto je známy jav nazývaný efekt horizontu . Stále sa však musíme pozrieť na pravdepodobne najefektívnejší algoritmus časového sekania, ktorý sa používa pri prehľadávaní stromov.

Prerezávanie alfa-beta

Dobre, to sú hrozienka a nie sušené slivky, ale napriek tomu - ako to niekedy bolo? Myslím vážne skupinu hrozienok blues?

Možno ste už uhádli, že prerezávanie alfa-beta nemá nič spoločné so sušenými slivkami a ešte viac o zmenšení veľkosti (prerezávania) nášho vyhľadávacieho stromu. Keď máme veľmi veľký vyhľadávací strom, ukázalo sa, že pri použití minimax nie je vždy potrebné prechádzať každým uzlom.

Musíme nájsť schopnosť minimaxu prestať hľadať konkrétnu oblasť stromu, keď nájde zaručené minimum alebo maximum tejto konkrétnej úrovne.

Ak to dokážeme, môže to výrazne znížiť čas odozvy nášho agenta AI a zlepšiť výkon.

Ako funguje prerezávanie alfa-beta?

Algoritmus minimax sa pohybuje v strome pomocou vyhľadávania podľa hĺbky. To znamená, že prechádza stromom zľava doprava a vždy ide najhlbšie, ako môže ísť. Potom objaví hodnoty, ktoré musia byť priradené uzlom priamo nad ním, bez toho, aby sa niekedy díval na ďalšie vetvy stromu.

Prerezávanie alfa-beta umožňuje minimaxu robiť rovnako dobré rozhodnutia, aké dokáže minimax sám, ale s vyššou úrovňou výkonu.

Uvažujme o nasledujúcom obrázku, na ktorom máme každému uzlu priradený strom s rôznymi skóre. Niektoré uzly sú zvýraznené červenou farbou, čo naznačuje, že ich nie je potrebné kontrolovať.

Vľavo dole na strome sa minimax pozerá na hodnoty 5 a 6 na dolnej maximálnej úrovni. Určuje, že 5 musí byť priradených k minimálnej úrovni priamo nad ňou. Dáva zmysel.

Ale po prezeraní 7 a 4 vetvy maximálnej úrovne vpravo si uvedomuje, že vyššie uvedenému uzlu minimálnej úrovne musí byť priradená maximálna hodnota 4. Pretože druhá maximálna úroveň priamo nad prvou minimálnou úrovňou bude trvať medzi 5 a nanajvýš 4, je jasné, že zvolí 5. Potom by pokračoval v prechádzaní stromom a vykonával rovnakú presnú množinu operácií v rámci ostatných vetiev stromu.

Ďalej je uvedené algoritmické znázornenie minimaxu s prerezávaním alfa-beta.

Použitie tejto metódy poskytuje ľahký spôsob, ako obmedziť vyhľadávací priestor nášho agenta AI. Týmto spôsobom prerezávanie alfa-beta umožňuje spoločnosti minimax robiť dobré rozhodnutia, ktoré by spoločnosť minimax mohla robiť sama, ale s vyššou úrovňou výkonu.

Isola-ter

Preskúmali sme, ako vytvoriť nášho vlastného agenta AI, ktorý dokáže hrať hru Isolation na dosť konkurenčnej úrovni. Pomocou algoritmu minmax sme videli, ako môže agent AI modelovať hru a robiť rozhodnutia na základe heuristického skóre. Tiež sme sa naučili, ako určiť dobre definovanú heuristiku pre našu zadanú úlohu (izolácia).

Ale tiež sme zistili, že by bolo príliš výpočtovo náročné nechať minimax bežať divoko. Museli sme teda použiť techniky ako iteračné prehĺbenie a prerezávanie alfa-beta. To by prinútilo nášho agenta AI, aby v rozumnom čase prišiel s ďalším krokom. Čo však v prípade, ak chceme, aby náš agent AI mal vyššiu mieru výhier a aby bol aspoň taký citlivý ako človek?

Existujú ďalšie techniky, ktoré by sme mohli preskúmať, aby sme zvýšili mieru výhry nášho agenta a čas odozvy. Dotkli sme sa myšlienky vylepšenia parametrov nášho heuristického skóre (pamätáte na „agresívny faktor“?). Mohli by sme dokonca vymyslieť heuristické skóre lepšie prispôsobené na hranie hry Isolation.

Na izolačnej doske existujú aj reflexné vlastnosti spojené s možnými pohybmi. Tieto sa ukážu, keď analyzujeme plne vyplnený vyhľadávací strom, čo by nám umožnilo potenciálne lomieť veľa vetiev z vyhľadávacieho stromu. Keby sme tiež inovovali náš hardvér, náš agent AI by bol rýchlejší - a tak by mohol preskúmať viac možností.

Ak sa chcete dozvedieť viac podrobností o tom, ako to implementovať sami, pozrite sa na kód, ktorý som napísal, aby som vyriešil tento problém pre moju aplikáciu Udacity Artificial Intelligence Nanodegree. Nájdete ho na mojom repozitári GitHub.

Ahoj, som Grant! Som nezávislý vývojár a kvantum. Prezrite si môj web na adrese //freelancequant.com. Na zdravie!