# 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) = 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

| 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