Hry-a-herni-strom.md

# Hry a prohledávání herního stromu Deep Blue porazil Kasparova v roce 1997 a novinové titulky psaly o počítači, který se naučil hrát šachy. Nenaučil. Deep Blue neuměl nic, co by neuměl program napsaný v roce 1960 - jen to dělal osmdesátkrát rychleji a měl lepší ohodnocovací funkci. Algoritmus za tím se jmenuje **minimax**, je z roku 1944 a vejde se na deset řádků. Jeho jediný problém je, že v šachách potřebuje prohledat `35^100 ≈ 10^154` uzlů, což je víc, než je ve vesmíru atomů. Celý obor počítačových her je pak osmdesát let hledání toho, jak z toho stromu ubrat, aniž by se změnil výsledek. Tahle stránka je o dvou algoritmech: minimaxu a alfa-beta prořezávání. Předpokládá to [stavový prostor](Stavovy-prostor) a [prohledávání](Neinformovane-prohledavani) - hlavně smysl parametrů `b` a `m`. O [strojovém učení](MLP-a-backpropagation) v moderních herních systémech se tu mluví jen na konci; AlphaGo je jiná stránka příběhu. ## Osmdesát let historie na sedmi řádcích | Rok | Kdo | Co ||---|---|---|| 1846 | Babbage | počítač porovnává přínos různých herních tahů || 1944 | von Neumann | algoritmy perfektní hry || 1945-50 | Zuse, Wiener, Shannon | přibližné vyhodnocování pozice || 1951 | Turing | první šachový program - jen na papíře, počítač na něj nestačil || 1952-57 | Samuel | strojové učení pro zpřesnění vyhodnocování || 1956 | McCarthy | prořezávání, a tím možnost hlubšího prohledávání | Za pozornost stojí, že **všechny podstatné nápady jsou z padesátých let**. Turingův šachový program z roku 1951 se počítal tužkou na papíře, protože žádný stroj tehdy nebyl dost rychlý. Samuel dělal strojové učení na hraní dámy v roce 1952, což je čtyřicet let před tím, než se strojovému učení začalo tak říkat. A jak to dopadlo: - **Othello** - od roku 1980 světoví šampioni odmítají hrát s počítači, protože jsou stroje příliš dobré.- **Dáma** - 1994, program Chinook porazil světovou šampionku.- **Šachy** - 1997, Deep Blue porazil Kasparova 3½ : 2½.- **Go** - do roku 2008 byly stroje příliš slabé, od roku 2016 AlphaGo poráží mistry. ## Čtyři typy her a proč jen jeden z nich umíme | | Deterministické | S náhodou ||---|---|---|| **Perfektní znalosti** | šachy, dáma, go, othello | backgammon, monopoly || **Nepřesné znalosti** | - | bridž, poker, scrabble | **Minimax a alfa-beta řeší jen levý horní roh té tabulky.** Hry s náhodou vyžadují expectimax (průměrování přes možné hody), hry s neúplnou informací vyžadují modelování soupeřova přesvědčení a jsou o řád těžší. Poker padl mnohem později než šachy právě proto. Prázdné políčko vlevo dole není chyba. Deterministická hra s nepřesnými znalostmi je vzácnost - když je hra deterministická a oba vidí všechno, informace nemá kam zmizet. ## Formulace hry jako prohledávání Dva hráči, **MAX** a **MIN**, se střídají. MAX chce co nejvyšší hodnotu, MIN co nejnižší. Úloha se formuluje čtyřmi věcmi: - **Počáteční stav** - herní situace a informace o tom, kdo je na tahu.- **Přechodová funkce** - vrací dvojice (legální tah, výsledný stav).- **Ukončovací podmínka** - určuje, kdy hra končí, tedy které stavy jsou koncové.- **Utilitární funkce** - numerické ohodnocení koncových stavů. Rozdíl oproti [běžnému prohledávání](Neinformovane-prohledavani) je jediný, ale zásadní: **v každé druhé vrstvě si tah nevybíráš ty**. Nemůžeš předpokládat, že se stane to nejlepší. Musíš předpokládat, že se stane to nejhorší. ## Minimax Hodnota uzlu se definuje rekurzivně: ```minimax(n) =    utility(n),                        pro koncový stav n    max nad s∈moves(n) z minimax(s),   pro MAX uzel n    min nad s∈moves(n) z minimax(s),   pro MIN uzel n``` Slovy: **v koncovém stavu je hodnota daná, jinde je to nejlepší (nebo nejhorší) z hodnot následníků**, podle toho, kdo je na tahu. ### Spočítej si to Strom hloubky 2, listy zleva: `3, 12, 8 | 2, 4, 6 | 14, 5, 2`. MIN vybírá minimum ze svých trojic: ```min(3, 12, 8) = 3min(2, 4, 6)  = 2min(14, 5, 2) = 2``` MAX vybírá maximum z výsledků MIN: ```max(3, 2, 2) = 3``` **Výsledek je 3 a MAX zahraje první tah.** Všimni si, že ta dvanáctka a čtrnáctka v listech na nic nemají vliv - MIN by tam nikdy nešel. To je první náznak toho, že se velká část stromu prohledávat nemusí. ### Vlastnosti | Vlastnost | Hodnota ||---|---|| Úplnost | ano, ale jen pro **konečné** stromy || Optimalita | **proti optimálnímu oponentovi** || Čas | `O(b^m)` || Prostor | `O(b·m)` - prohledávání do hloubky | Ta optimalita má háček, na který se snadno zapomene. **Minimax je optimální proti optimálnímu soupeři.** Proti soupeři, který dělá chyby, je jen bezpečný - najde tah, který nejhůř dopadne co nejlíp, ale nevyužije toho, že by protihráč mohl chybovat. Proti slabému soupeři existují lepší strategie a minimax je nezná. Pro šachy: `b ≈ 35`, `m ≈ 100`, takže `35^100 ≈ 10^154` uzlů. **Přesné řešení není možné a nikdy nebude.** ### Pseudokód ```function minimax(pozice, hloubka):    if pozice je koncová or hloubka = 0 then        return heuristické ohodnocení pozice    else        ohod ← −∞        for all potomek pozice do            ohod ← max(ohod, −minimax(potomek, hloubka−1))        end for        return ohod    end if``` Všimni si toho **minusu** před rekurzivním voláním. Tomuhle triku se říká **negamax** a je to důvod, proč se nemusí psát dvě větve pro MAX a MIN. Funguje jen za předpokladu, že je ohodnocení hry nulový součet - co je dobré pro mě, je stejně špatné pro soupeře. ## Ohodnocovací funkce Vstupem je pozice, výstupem **celé číslo**. Funkce se vytváří z pohledu jednoho hráče a ohodnocení z pohledu druhého je totéž se záporným znaménkem. Co se v šachách hodnotí: - **Materiální složka** - rozdíl v počtu a hodnotě figur. Nejsilnější jednotlivá složka.- **Statická poziční složka** - bonusy za umístění figur (kůň uprostřed, věž na otevřeném sloupci).- **Dynamická poziční složka** - bloky figur, osamělé pěšce, struktura. **Kvalita ohodnocovací funkce rozhoduje víc než hloubka prohledávání** a je to ta část, kterou nikdo neumí odvodit - ladí se ručně nebo se učí z partií, což dělal Samuel už v roce 1952. ## Alfa-beta prořezávání V řadě situací nemusí minimax zkoumat další pozice, protože je **už teď jasné, že na volbu tahu nebudou mít vliv**. - **Alfa ořezávání** - nalezena příliš malá hodnota, tuhle větev hráč na tahu nezvolí.- **Beta ořezávání** - nalezená hodnota je příliš velká, soupeř tuhle větev nezvolí. Vrať se k příkladu výš. Když MAX ví, že první větev dá 3, a v druhé větvi hned narazí na list s hodnotou 2, může **zbytek druhé větve zahodit**. MIN v ní totiž nikdy nevrátí víc než 2, a to už je horší než jistá trojka. Ať je pod tou větví cokoliv, na výsledek to nemá vliv. ```function alfabeta(pozice, hloubka, alfa, beta):    if je_prohra(pozice) then return −MAX    if je_výhra(pozice) then return MAX    if je_remíza(pozice) then return 0    if hloubka = 0 then        return ohodnocovaci_funkce(pozice)    end if    tahy ← generuj_tahy(pozice)    for all tah v kolekci tahy do        pot ← zahraj(pozice, tah)        ohod ← −alfabeta(pot, hloubka−1, −beta, −alfa)        if ohod > alfa then            alfa ← ohod            if ohod ≥ beta then return beta        end if    end for    return alfa``` Prohození a znegování `alfa` a `beta` v rekurzivním volání je opět negamax - z pohledu soupeře se role obou mezí vymění. ### Vlastnosti prořezávání **Prořezávání neovlivní výsledek.** Vrací přesně to, co by vrátil minimax. To je nejdůležitější vlastnost celého algoritmu - není to aproximace, je to zrychlení. **Uspořádání tahů rozhoduje o efektivitě.** Když prohlédneš dobré tahy první, meze se rychle utáhnou a ořeže se hodně. Při náhodném pořadí se ořeže málo. **Při nejlepším uspořádání je čas `O(b^(m/2))`.** To je odmocnina původního počtu uzlů, tedy **zdvojnásobení dosažitelné hloubky za stejný čas**. **V šachách to znamená hloubku 8**, což je už použitelná úroveň hry. Ta jedna odmocnina je celý rozdíl mezi programem, který hraje jako začátečník, a programem, který porazí většinu lidí. Praktický důsledek: **do generátoru tahů se vyplatí investovat.** Zkoušet nejdřív brát figury, pak šachy, pak tahy, které se osvědčily v jiných větvích - to všechno zlepšuje uspořádání a tím i hloubku. ## Časové omezení a minimax cutoff Předpokládej sto sekund na tah a `10^4` uzlů za sekundu, tedy `10^6` uzlů na jeden tah. Do `35^100` to má daleko a hra musí být odehrána. Řešením je **minimax cutoff**: nahradí se dvě věci ze základní formulace. | Původně | Nahrazeno | Proč ||---|---|---|| Utilitární funkce (jen koncové stavy) | **Ohodnocovací funkce** (jakákoliv pozice) | musíš umět ohodnotit i nedohranou pozici || Koncový test | **Ořezávací test** (cutoff test) | typicky hloubka, nebo hodnota ohodnocovací funkce | Tím se z algoritmu, který hraje perfektně, stane algoritmus, který hraje dobře. **Cena za to je, že se program dá napálit na hranici horizontu** - špatnou věc, která se stane o jeden tah za limitem, prostě neuvidí a bude ji odsouvat. Tomu se říká *horizon effect* a řeší se prohlubováním v „neklidných" pozicích, kde se právě berou figury. ## Kdy tohle přestává stačit **Faktor větvení je moc velký.** V go je `b ≈ 250` proti šachovým 35. Alfa-beta tam nepomůže dost a dobrou ohodnocovací funkci nikdo neuměl napsat - pozice v go se nedá rozložit na materiál a strukturu. Proto go padlo až v roce 2016, a to úplně jinou metodou: **Monte Carlo Tree Search plus [neuronová síť](Konvolucni-site)**, která ohodnocovací funkci nahradila naučeným modelem. **Ve hře je náhoda.** Backgammon potřebuje expectimax, kde se v uzlu s hodem kostkou počítá vážený průměr přes možné výsledky. Prořezávání tam funguje mnohem hůř, protože průměr nemá tvrdé meze. **Hráči nevidí totéž.** V pokeru a bridži se nedá postavit jeden herní strom, protože každý hráč prohledává jiný. Řeší se to teorií her a hledáním rovnováhy, ne minimaxem. ## Co se na tom nejčastěji rozbije | Příznak | Kde je problém ||---|---|| Program hraje sebevražedně | znaménko - ohodnocení počítáš z pohledu špatného hráče || Alfa-beta dává jiný výsledek než minimax | chybně předávané meze v rekurzi, typicky neprohozené `−beta, −alfa` || Prořezává skoro nic | špatné uspořádání tahů, generátor vrací tahy v pořadí polí || Program odsouvá nevyhnutelnou ztrátu | horizon effect - chybí prohlubování v neklidných pozicích || Hraje dobře v otevření, blbě v koncovce | ohodnocovací funkce laděná na střední hru, koncovka má jiná pravidla || Přeteče zásobník | chybí ořezávací test na hloubku, rekurze nemá dno | ## Co si odnést **Minimax předpokládá nejlepšího možného soupeře.** Proti chybujícímu je bezpečný, ne optimální. **Alfa-beta nemění výsledek.** Je to čisté zrychlení, ne aproximace. **Dobré uspořádání tahů zdvojnásobí hloubku.** `O(b^(m/2))` místo `O(b^m)`. **Ohodnocovací funkce rozhoduje víc než hloubka.** A je to ta část, kterou musíš vymyslet ty. **Cutoff dělá z perfektní hry hru dobrou.** A vyrábí horizon effect. **Go padlo jinou metodou.** Když je `b` moc velké a ohodnocení se nedá napsat, alfa-beta nestačí. ## Kam dál - **[Informované prohledávání](Informovane-prohledavani)** - odhad hodnoty stavu bez protihráče- **[Dekompozice a AND/OR grafy](Dekompozice-a-AND-OR-grafy)** - herní strom je AND/OR graf, kde AND uzly patří soupeři- **[Konvoluční sítě](Konvolucni-site)** - čím se v AlphaGo nahradila ohodnocovací funkce- **[Genetické algoritmy](Geneticke-algoritmy)** - druhý způsob, jak si poradit s prostorem, který se nedá projít