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 a prohledávání - hlavně smysl parametrů b a m. O strojovém učení 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

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

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í 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) = 3
min(2, 4, 6)  = 2
min(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

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.

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íť, 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

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í - odhad hodnoty stavu bez protihráče
• Dekompozice a AND/OR grafy - herní strom je AND/OR graf, kde AND uzly patří soupeři
• Konvoluční sítě - čím se v AlphaGo nahradila ohodnocovací funkce
• Genetické algoritmy - druhý způsob, jak si poradit s prostorem, který se nedá projít