Hry a protivník: minimax, alfa-beta ořezávání a Monte Carlo tree search

Hra jako úloha prohledávání, herní strom, minimax, alfa-beta ořezávání, ohodnocovací funkce a MCTS — na piškvorkách, kde se dá spočítat všechno, a s cestou od Deep Blue k AlphaZero.

14 minut Matěj Žalmánek 2026-10-15

Série Základy AI Díl 22 z 83

Celá osnova série 83 z 83 témat hotovo

Co si odnesete

Jak se hra dvou hráčů zapíše jako úloha prohledávání a proč je řešením strategie, ne cesta.
Jak minimax spočítá zaručenou hodnotu pozice a proč alfa-beta dojde ke stejnému výsledku mnohem rychleji.
Jak Monte Carlo tree search najde dobrý tah bez ohodnocovací funkce a co z něj udělalo AlphaGo.

Co se hodí znát předem: Prohledávání stavového prostoru: BFS, DFS, UCS a A* s animacemi, Grafy a stromy: struktura, na které stojí hledání i neuronové sítě

V bludišti z minulého dílu stál panáček sám. Svět se nehýbal a každý tah vedl tam, kam měl. Ve hře ale sedí naproti vám někdo, kdo chce přesný opak — a na každý váš tah odpoví tím, který vás bolí nejvíc. Hledat cestu k cíli už nestačí: musíte hledat strategii, která obstojí proti každé odpovědi. Šachy, dáma i go byly desítky let měřítkem umělé inteligence a algoritmy z tohohle dílu stojí za Deep Blue i za AlphaGo.

Navazuje na díly Prohledávání stavového prostoru a Grafy a stromy.

1. Hra jako úloha prohledávání

Definice — hra dvou hráčů

Hra dvou hráčů (deterministická, s úplnou informací a nulovým součtem) je sedmice

Γ = (S, s₀, hráč, A, T, K, U),

která splňuje:

S je neprázdná množina stavů (pozic) a s₀ ∈ S je počáteční stav;
K ⊆ S je množina koncových stavů — v nich hra skončí;
hráč : S ∖ K → {MAX, MIN} určuje, kdo je ve stavu na tahu;
A přiřazuje každému stavu s ∈ S ∖ K konečnou neprázdnou množinu A(s) tahů (akcí) a v koncových stavech A(s) = ∅;
T je přechodová funkce: pro s ∈ S ∖ K a a ∈ A(s) je T(s, a) ∈ S stav po tahu a (tahy jsou deterministické);
hráči se střídají: je-li s ∈ S ∖ K, a ∈ A(s) a T(s, a) ∉ K, pak hráč(T(s, a)) ≠ hráč(s);
U : K → ℝ je užitek koncového stavu z pohledu hráče MAX; užitek hráče MIN je −U (nulový součet: U(s) + (−U(s)) = 0 pro každé s ∈ K).

Oba hráči znají celou sedmici a v každém okamžiku vidí aktuální stav (úplná informace). Hra je konečná, právě když neexistuje nekonečná posloupnost s₀, s₁, s₂, … s s_i = T(s_i−1, a_i) pro nějaká a_i ∈ A(s_i−1) — každá partie tedy po konečně mnoha tazích skončí v K. Všechny hry v tomto díle jsou konečné.

Strategie hráče MAX je funkce σ, která každému stavu s ∈ S ∖ K s hráč(s) = MAX přiřadí tah σ(s) ∈ A(s); strategie τ hráče MIN je definovaná stejně pro stavy s hráč(s) = MIN. Dvojice strategií (σ, τ) jednoznačně určí partii ze stavu s₀ a tím i její užitek.

Laicky řečeno

Hra je bludiště, ve kterém se o tahy dělíte s protivníkem. Na konci se sečte skóre — v piškvorkách +1, když vyhraje MAX, −1, když vyhraje MIN, a 0 za remízu. MAX chce skóre co nejvyšší, MIN co nejnižší. „Nulový součet“ znamená, že se nedá vyhrát společně: co jeden získá, druhý ztratí.

Rozdíl proti prohledávání je zásadní. Řešením už není cesta — tu si nevyberete, protože každý druhý tah dělá soupeř. Řešením je strategie: předpis, jak odpovědět na každý tah, který soupeř může zahrát.

2. Herní strom

Definice — herní strom

Nechť Γ = (S, s₀, hráč, A, T, K, U) je konečná hra dvou hráčů. Herní strom hry Γ je kořenový strom (viz díl Grafy a stromy), pro který platí:

uzly jsou všechny posloupnosti tahů (a₁, …, a_k), k ≥ 0, které lze ze s₀ zahrát, tj. s_i−1 ∉ K, a_i ∈ A(s_i−1) a s_i = T(s_i−1, a_i) pro i = 1, …, k; uzlu přísluší stav s_k;
kořen je prázdná posloupnost () se stavem s₀;
děti uzlu (a₁, …, a_k) se stavem s_k ∉ K jsou uzly (a₁, …, a_k, a) pro všechna a ∈ A(s_k) se stavy T(s_k, a);
listy jsou právě uzly, jejichž stav je koncový (s_k ∈ K).

Uzel tedy není pozice, ale historie, která k ní vedla — do stejného stavu se lze dostat různými posloupnostmi tahů a ve stromu se pak objeví víckrát. Uzly, kde je na tahu MAX, kreslíme jako trojúhelník špičkou nahoru, uzly MIN špičkou dolů.

Nechť b = max_{s ∈ S ∖ K} |A(s)| je větvicí faktor a m největší délka partie (počet tahů). Pak má strom nejvýš b^m listů.

Laicky řečeno

Všechny partie, které se dají odehrát, nakreslené jako rozvětvený strom: z kořene vede jedna větev pro každý první tah, z každé z nich větev pro každou odpověď a tak dál, až ke konci hry. Jeden list = jedna dohraná partie.

Piškvorky na hracím poli 3 × 3 jsou malá hra, a přesto má jejich strom 549 946 uzlů a 255 168 listů — tolik různých partií se dá odehrát. Různých pozic je přitom jen 5 478: do stejné pozice se dostanete mnoha pořadími tahů. Šachy mají větvicí faktor kolem 35 a partie trvá desítky tahů; Claude Shannon v roce 1950 odhadl jejich strom na 10¹²⁰ partií. Go s větvicím faktorem kolem 250 je ještě o mnoho řádů dál. Celý strom tedy projdeme jen u malých her — u velkých se musíme naučit, které větve vynechat.

Příklad — horní odhad stromu piškvorek a Shannonovo číslo

Kdyby se piškvorky hrály vždy až do zaplnění pole, měl by strom v hloubce k právě 9 · 8 · … · (9 − k + 1) = 9!/(9 − k)! uzlů (k = 0, …, 9). Celkem

∑_k=0⁹ 9!/(9 − k)! = 1 + 9 + 72 + 504 + 3 024 + 15 120 + 60 480 + 181 440 + 362 880 + 362 880 = 986 410 uzlů a 9! = 362 880 listů.

Skutečný strom má 549 946 uzlů a 255 168 listů, protože partie, ve které někdo složí tři v řadě, končí dřív a její větev se dál nevětví. Odhad b^m je tedy horní mez; tady s b klesajícím od 9 k 1.

Shannon (Programming a Computer for Playing Chess, 1950) počítal pro šachy s asi 10³ možnostmi na jednu dvojici tahů (bílý a černý) a typickou partií o 40 dvojicích tahů: (10³)⁴⁰ = 10¹²⁰. Je to hrubý řádový odhad, ne přesné číslo.

3. Minimax

Definice — minimaxová hodnota

Nechť Γ = (S, s₀, hráč, A, T, K, U) je konečná hra dvou hráčů. Minimaxová hodnota je funkce MM : S → ℝ definovaná rekurzivně pro každé s ∈ S:

MM(s) = U(s), je-li s ∈ K;
MM(s) = max_{a ∈ A(s)} MM(T(s, a)), je-li s ∉ K a hráč(s) = MAX;
MM(s) = min_{a ∈ A(s)} MM(T(s, a)), je-li s ∉ K a hráč(s) = MIN.

Rekurze je dobře definovaná: hra je konečná, takže každý řetězec rekurzivních volání skončí v koncovém stavu, a A(s) je konečná neprázdná, takže maximum i minimum existují.

Tah a* ∈ A(s) je optimální tah hráče MAX ve stavu s s hráč(s) = MAX, právě když

a* ∈ argmax_{a ∈ A(s)} MM(T(s, a)), tj. MM(T(s, a*)) = MM(s);

optimální tah hráče MIN je obdobně prvek argmin. Strategie, která v každém stavu volí optimální tah, je minimaxová strategie.

Laicky řečeno

Hodnotu pozice spočítáte odzadu. Na konci hry ji znáte — je to skóre. O tah dřív: když hraje MAX, vybere si to nejlepší z toho, co ho čeká; když hraje MIN, vybere to nejhorší pro MAX. Takhle se hodnoty přelévají patro po patru nahoru až ke kořeni. Je to přesně úvaha „když půjdu sem, on půjde tam, a pak já…“, jen dotažená do konce.

Minimax: hodnoty probublávají od listů ke kořeni

Uzel MIN vlevo si z listů 4, 6 a 9 vybere 4, prostřední z 2, 7 a 8 vybere 2, pravý z 5, 3 a 9 vybere 3. MAX v kořeni pak volí mezi 4, 2 a 3 a zahraje levý tah s hodnotou 4. Všimněte si, že pravá větev skrývá devítku — jenže na ni MAX nikdy nedosáhne, protože MIN by místo ní zahrál trojku.

Věta — co minimax zaručuje

Nechť Γ je konečná hra dvou hráčů a σ* minimaxová strategie hráče MAX. Pak

pro každou strategii τ hráče MIN má partie hraná dvojicí (σ*, τ) užitek ≥ MM(s₀);
je-li i τ* minimaxová strategie hráče MIN, má partie hraná dvojicí (σ*, τ*) užitek právě MM(s₀).

Důkaz (náčrt), indukcí podle výšky uzlu: v listu MAX získá přesně U(s) = MM(s). V uzlu MAX zahraje tah do dítěte s největší hodnotou a podle indukčního předpokladu si v něm uhájí aspoň tuto hodnotu, tedy aspoň MM(s). V uzlu MIN si soupeř vybere libovolné dítě, ale každé má hodnotu ≥ min = MM(s), a v každém si MAX podle předpokladu uhájí aspoň jeho hodnotu. Pro s = s₀ to je bod 1. Stejnou úvahou s prohozenými rolemi si MIN minimaxovou strategií τ* zajistí užitek nejvýš MM(s₀) proti každé strategii MAX; obě nerovnosti dohromady dávají bod 2. ∎

Minimax prochází strom do hloubky: čas O(b^m), paměť O(b · m).

Laicky řečeno

Minimax počítá s nejhorším: předpokládá, že soupeř nikdy neudělá chybu. Když ji udělá, dopadnete jen lépe. Proto je minimax hodnota zaručená — to, co si uhájíte, ať soupeř hraje jakkoli.

4. Minimax na piškvorkách

Piškvorky 3 × 3 jsou dost malé, aby minimax prošel celý strom. Výsledek zná každý, kdo je hrál déle než pár minut: minimaxová hodnota prázdného pole je 0 — když oba hrají bez chyby, je to vždycky remíza. Zajímavější je, co minimax řekne o konkrétní pozici. Na tahu je X (MAX) a v každém volném políčku je hodnota tahu na něj:

Hodnota každého tahu X podle minimaxu +1 výhra0 remíza−1 prohra

Vyhrává jediný tah — střed. X tím postaví vidličku: hrozí dokončit prostřední řádek i úhlopříčku a O nemůže zablokovat obojí. Tah dolů doprostřed drží remízu. Zbylé tři tahy vypadají nevinně, ale prohrávají: O na ně odpoví vlastní vidličkou. Člověk by to musel promyslet; minimax to prostě spočítá.

def minimax(deska):
    konec = vitez(deska)                 # "X", "O", "remiza", nebo None
    if konec:
        return {"X": 1, "O": -1, "remiza": 0}[konec]
    hodnoty = [minimax(zahraj(deska, tah)) for tah in volna_pole(deska)]
    return max(hodnoty) if na_tahu(deska) == "X" else min(hodnoty)

5. Alfa-beta ořezávání

Minimax projde celý strom, i když je z poloviny zbytečný. Podívejte se znovu na prostřední větev: první list ukázal 2. MIN tedy v té větvi dosáhne 2 nebo méně — a MAX už má levou větev s hodnotou 4 jistou. Ať jsou zbylé dva listy jakékoli, MAX do prostřední větve nepůjde. Nemusí se na ně ani dívat.

Definice — alfa-beta

Nechť Γ je konečná hra dvou hráčů. Alfa-beta je prohledávání do hloubky, které si s sebou nese dvě meze α, β ∈ ℝ ∪ {−∞, +∞}:

α — nejvyšší hodnota, kterou si MAX už zajistil někde na cestě od kořene (na začátku −∞);
β — nejnižší hodnota, kterou si už zajistil MIN (na začátku +∞).

Funkce AB(s, α, β) pro stav s ∈ S:

Je-li s ∈ K, vrať U(s).
Je-li hráč(s) = MAX, polož v ← −∞; jinak v ← +∞.
Pro tahy a ∈ A(s) postupně (v pevném pořadí) spočítej h ← AB(T(s, a), α, β) a
- v uzlu MAX polož v ← max(v, h) a α ← max(α, v),
- v uzlu MIN polož v ← min(v, h) a β ← min(β, v);
jakmile α ≥ β, zbylé tahy se ořežou — neprohledávají se — a pokračuje se krokem 4.
Vrať v.

Alfa-beta v kořeni je volání AB(s₀, −∞, +∞).

Věta. Nechť Γ je konečná hra dvou hráčů. Pak AB(s₀, −∞, +∞) = MM(s₀) — alfa-beta vrátí v kořeni stejnou hodnotu jako minimax (ve vnitřních uzlech, kde došlo k ořezu, vrací jen mez, ne přesnou hodnotu). Má-li strom větvicí faktor b a hloubku m a jsou-li tahy seřazené v nejlepším možném pořadí, prozkoumá alfa-beta jen O(b^m/2) uzlů.

Laicky řečeno

α je „tohle už mám v kapse“, β je „víc mi soupeř stejně nedovolí“. Když v nějaké větvi zjistíte, že soupeř vás v ní může srazit pod to, co už máte jistého jinde, nemá smysl ji zkoumat dál — stačí jediný vyvracející tah. Hodnota v kořeni zůstane stejná, jen ji najdete rychleji.

ořízni, když α ≥ β

α: to nejlepší, co si MAX už zajistil jinde na cestě od kořene. Do větve, která dá méně, nikdy nepůjde — má lepší volbu
β: to nejhorší pro MAX, co mu MIN v téhle větvi už může vnutit. Víc než β odsud MAX nedostane, ať zbylé děti vyjdou jakkoli
≥: okno [α, β] je prázdné: hodnota, o kterou by se tu ještě dalo hrát, by musela být zároveň aspoň α a nejvýš β. Taková neexistuje (při rovnosti by nebyla lepší, než co MAX už má), takže zbytek větve kořen nemůže ovlivnit

V prostřední větvi stromu: α = 4 (levá větev), po prvním listu β = 2. Protože 4 ≥ 2, listy 7 a 8 se nezkoumají.

Alfa-beta na stejném stromu: čísla jsou pořadí návštěv u uzlů okno α, β; oranžově, když α ≥ β a zbytek větve se ořízneořezáno listů: 3 / 9

Alfa-beta došla ke stejnému výsledku — MAX hraje vlevo a získá 4 — ale ohodnotila jen 6 listů z 9. V prostřední větvi ořízla dva listy hned po dvojce, v pravé jeden po trojce. U ořezaného uzlu MIN je proto jen mez „≤ 2“ a „≤ 3“: přesnou hodnotu neznáme, a nepotřebujeme ji.

Totéž, co animace ukazuje u uzlů, krok po kroku v tabulce. Řádek zachycuje okno uzlu při vstupu do něj a pak po každém dítěti, které vrátilo hodnotu:

krok	uzel	co se stalo	`α`	`β`	poznámka
1	A (MAX)	vstup	−∞	+∞
2	B (MIN)	vstup	−∞	+∞
3	B (MIN)	b1 vrátil 4	−∞	4
4	B (MIN)	b2 vrátil 6	−∞	4
5	B (MIN)	b3 vrátil 9	−∞	4	B vrací 4
6	A (MAX)	B vrátil 4	4	+∞
7	C (MIN)	vstup	4	+∞
8	C (MIN)	c1 vrátil 2	4	2	α ≥ β: ořez c2, c3; C vrací jen mez ≤ 2
9	A (MAX)	C vrátil 2	4	+∞
10	D (MIN)	vstup	4	+∞
11	D (MIN)	d1 vrátil 5	4	5
12	D (MIN)	d2 vrátil 3	4	3	α ≥ β: ořez d3; D vrací jen mez ≤ 3
13	A (MAX)	D vrátil 3	4	+∞	A vrací 4

Uzel MIN dostane od rodiče α = 4 a mění jen svoje β; uzel MAX naopak mění jen α. Okno každého uzlu se tak jen zužuje. V pravé větvi první list (5) ořez nevyvolá — 5 je víc než 4, MIN by tu MAXovi mohl dát víc než vlevo —, až druhý list (3) stáhne β pod α.

Na piškvorkách je rozdíl dramatičtější. Úplný minimax z prázdného pole navštíví 549 946 pozic, alfa-beta se stejným pořadím tahů jen 18 297 — asi třicetkrát méně — a vrátí stejnou nulu. Exponent m/2 ve větě znamená, že za stejný čas dohlédnete dvakrát hlouběji. Proto na pořadí tahů tolik záleží: šachové programy zkoušejí jako první braní a tahy, které byly dobré minule.

Příklad — kolik listů ušetří alfa-beta při nejlepším pořadí

Přesnou mez dokázali D. E. Knuth a R. W. Moore (An Analysis of Alpha-Beta Pruning, 1975): ve stromu s větvicím faktorem b a hloubkou d ohodnotí alfa-beta při nejlepším pořadí tahů

b^⌈d/2⌉ + b^⌊d/2⌋ − 1 listů místo b^d.

Šachy, b = 35, hloubka d = 6 půltahů: minimax 35⁶ = 1 838 265 625 listů, alfa-beta 35³ + 35³ − 1 = 42 875 + 42 875 − 1 = 85 749 listů — asi 21 000krát méně. A obráceně: 12 půltahů projde alfa-beta s 35⁶ + 35⁶ − 1 ≈ 3,7 · 10⁹ listy, tedy jen za dvojnásobek práce, kterou minimax potřebuje na 6 půltahů.

Malý strom z obrázku (b = 3, d = 2): mez je 3 + 3 − 1 = 5 listů. Alfa-beta jich ohodnotila 6, protože pořadí listů není nejlepší možné — v pravé větvi stojí trojka až na druhém místě.

def alfabeta(deska, alfa=-inf, beta=inf):
    konec = vitez(deska)
    if konec:
        return {"X": 1, "O": -1, "remiza": 0}[konec]
    maximalizuje = na_tahu(deska) == "X"
    v = -inf if maximalizuje else inf
    for tah in volna_pole(deska):
        h = alfabeta(zahraj(deska, tah), alfa, beta)
        if maximalizuje:
            v = max(v, h); alfa = max(alfa, v)
        else:
            v = min(v, h); beta = min(beta, v)
        if alfa >= beta:
            break                          # ořez: zbytek větve nic nezmění
    return v

6. Omezená hloubka a ohodnocovací funkce

Ani alfa-beta neprojde šachový strom do konce partie. Skutečné programy proto hledají jen do pevné hloubky a pozici, ve které skončí, odhadnou.

Definice — minimax s omezenou hloubkou

Nechť Γ = (S, s₀, hráč, A, T, K, U) je hra dvou hráčů. Ohodnocovací funkce je funkce E : S → ℝ taková, že E(s) = U(s) pro všechna s ∈ K; pro s ∉ K je E(s) odhad MM(s). Obvykle je to vážený součet n ≥ 1 příznaků pozice f₁, …, f_n : S → ℝ s vahami w₁, …, w_n ∈ ℝ:

E(s) = w₁f₁(s) + … + w_nf_n(s).

Minimax s omezenou hloubkou je pro každé d ∈ ℕ₀ funkce MM_d : S → ℝ definovaná rekurzivně podle d:

MM_d(s) = E(s), je-li s ∈ K nebo d = 0;
MM_d(s) = max_{a ∈ A(s)} MM_d−1(T(s, a)), je-li s ∉ K, d ≥ 1 a hráč(s) = MAX;
MM_d(s) = min_{a ∈ A(s)} MM_d−1(T(s, a)), je-li s ∉ K, d ≥ 1 a hráč(s) = MIN.

Hodnota MM_d(s) tedy počítá minimax jen d půltahů dopředu a pozice, ve kterých skončí, nahradí odhadem E. Je-li d aspoň délka nejdelší partie ze s, je MM_d(s) = MM(s).

Laicky řečeno

Neumíte domyslet partii do konce, tak se podíváte pár tahů dopředu a zeptáte se: „Jak dobře to tu vypadá?“ V šachu je nejjednodušší odpověď spočítat materiál — pěšec 1, jezdec a střelec 3, věž 5, dáma 9 — a odečíst soupeřův. Lepší funkce přidají aktivitu figur, bezpečnost krále nebo strukturu pěšců.

E(s) = ∑_i w_i · (p_i(s) − p′_i(s))

E(s): odhad hodnoty pozice z pohledu MAX (bílého) — dosadí se tam, kde hledání skončí, místo skutečné minimaxové hodnoty
∑_i: přes druhy figur: pěšec, jezdec, střelec, věž, dáma. Součet, protože materiál různých figur se v nejjednodušším modelu prostě sčítá
w_i: cena figury: 1, 3, 3, 5, 9. Váha převádí „kusy“ na společnou měnu, aby šlo porovnat věž s dvěma jezdci
p_i − p′_i: kolik figur daného druhu má bílý víc než černý. Rozdíl, ne počet, protože hra má nulový součet: co má soupeř navíc, je ztráta

Bílý má o jezdce víc, černý o dva pěšce víc: E = 3 · (+1) + 1 · (−2) = +1, tedy mírná výhoda bílého. Ceny figur jsou tradiční šachová konvence, ne výsledek výpočtu.

def minimax_d(s, d):
    if je_konec(s) or d == 0:
        return E(s)                        # dál nevidíme: odhad místo skutečné hodnoty
    hodnoty = [minimax_d(T(s, a), d - 1) for a in akce(s)]
    return max(hodnoty) if hrac(s) == "MAX" else min(hodnoty)

def iterativni_prohlubovani(s, cas):      # v s je na tahu MAX
    d, nejlepsi = 1, None
    while zbyva(cas):
        nejlepsi = max(akce(s), key=lambda a: minimax_d(T(s, a), d - 1))
        d += 1                             # další kolo o půltah hlouběji
    return nejlepsi

Omezená hloubka má svou past: efekt horizontu. Když hledání skončí uprostřed výměny figur — vy jste právě vzali dámu, soupeř ji za tah vezme zpátky —, ohodnocovací funkce vidí jen první polovinu a pozici přecení. Programy se brání tím, že „neklidné“ pozice prohledávají dál, dokud se neuklidní. A protože nikdy nevědí, kolik mají času, hledají iterativním prohlubováním z minulého dílu: hloubka 1, 2, 3, … dokud nedojde čas. Výsledky mělkých průchodů navíc poslouží jako pořadí tahů pro hlubší — a alfa-beta pak ořezává mnohem víc.

7. Monte Carlo tree search

Ohodnocovací funkci pro šachy lidé ladili desítky let. Pro go se ji napsat nedařilo — pozice, která vypadá klidně, může být o dvacet tahů později prohraná. Monte Carlo tree search (MCTS) na ohodnocovací funkci úplně rezignuje. Místo odhadu pozici dohraje: náhodně, mnohokrát, a podívá se, jak často to dopadlo dobře.

Definice — jedna iterace MCTS

Nechť Γ = (S, s₀, hráč, A, T, K, U) je konečná hra dvou hráčů, ve které má každá partie výsledek výhra, remíza, nebo prohra. Vstup: stav s₀ ∉ K (kořen) a počet iterací (nebo časový limit). Výstup: tah a ∈ A(s₀).

MCTS buduje prohledávací strom — část herního stromu, která začíná jen kořenem a v každé iteraci se o jeden uzel rozroste. Každý uzel i stromu si pamatuje:

počet návštěv n_i ∈ ℕ₀ — kolik simulací prošlo uzlem;
součet výsledků w_i ∈ [0, n_i] z pohledu hráče, který do uzlu táhl, přičemž výsledek jedné partie je 1 za výhru, ½ za remízu a 0 za prohru.

Uzel je plně rozšířený, právě když má ve stromu dítě pro každý tah a ∈ A(s) svého stavu s. Jedna iterace MCTS má čtyři kroky:

Výběr — začni v kořeni; dokud je aktuální uzel plně rozšířený a jeho stav není koncový, přejdi do dítěte s nejvyšší hodnotou UCT (definice níže).
Rozšíření — není-li stav aktuálního uzlu koncový, vyber dosud nezkoušený tah a, přidej dítě se stavem T(s, a) a n = w = 0 a přejdi do něj.
Simulace — ze stavu aktuálního uzlu dohraj partii náhodnými tahy (každý z A(s) se stejnou pravděpodobností) až do koncového stavu s_K ∈ K.
Zpětné šíření — každému uzlu i na cestě od aktuálního uzlu zpět ke kořeni (včetně obou) polož n_i ← n_i + 1 a w_i ← w_i + výsledek partie s_K z pohledu hráče, který do uzlu i táhl.

Iterace se opakují, dokud nevyprší počet iterací nebo čas. Pak se zahraje tah z kořene do dítěte s největším n_i.

Laicky řečeno

Jako když se rozhodujete mezi restauracemi: chodíte tam, kde vám zatím chutnalo nejvíc, ale občas zkusíte i jinou. Každý tah dostane šanci, slibné tahy dostanou víc pokusů, a strom roste právě tam, kde se hraje o hodně. Náhodné dohrávky jsou hloupé, jenže když jich je tisíc, průměr už něco říká.

Čtyři kroky jedné iterace MCTS

def mcts(koren, iteraci):
    for _ in range(iteraci):
        u = koren
        while u.vsechny_deti() and u.deti:         # 1. výběr
            u = max(u.deti, key=uct)
        if u.nezkusene and not je_konec(u.stav):   # 2. rozšíření
            u = u.pridej_dite(nahodny(u.nezkusene))
        s = u.stav
        while not je_konec(s):                     # 3. simulace
            s = T(s, nahodny(akce(s)))
        while u is not None:                       # 4. zpětné šíření
            u.n += 1
            u.w += vysledek(s, pro=u.kdo_tahl)     # 1, ½ nebo 0
            u = u.rodic
    return max(koren.deti, key=lambda d: d.n).tah

Definice — UCT

Nechť uzel prohledávacího stromu MCTS má N ≥ 1 návštěv a děti i = 1, …, k, každé s n_i ≥ 1 návštěvami a součtem výsledků w_i ∈ [0, n_i] (značení z definice MCTS výše). Nechť c > 0 je pevná konstanta průzkumu, obvykle c = √2. Hodnota UCT (Upper Confidence bounds applied to Trees) dítěte i je

UCT(i) = w_i/n_i + c · √ln N/n_i.

Ve kroku výběru se volí dítě i* ∈ argmax_{i ∈ {1, …, k}} UCT(i). Kocsis a Szepesvári (2006) dokázali, že s rostoucím počtem iterací pravděpodobnost, že MCTS s UCT doporučí jiný než minimaxově optimální tah, klesá k nule.

Laicky řečeno

První člen je „jak dobře to zatím dopadalo“, druhý „jak málo to znám“. Tah, který jste dlouho nezkusili, dostává bonus, který s každou návštěvou jiného tahu pomalu roste. Je to stejné dilema jako u zpětnovazebního učení: využívat to, co funguje, nebo prozkoumávat, co by mohlo fungovat líp?

UCT(i) = w_i/n_i + c · √ln N/n_i

UCT(i): skóre dítěte i ve výběru; vyhraje největší. Není to odhad hodnoty tahu, ale „jak moc se vyplatí ho zkusit znovu“
w_i/n_i: průměrný výsledek tahu (0 až 1) — využívání: tahy, které zatím vycházely dobře, dostanou přednost
c: konstanta průzkumu — kolik váží zvědavost proti dosavadním výsledkům. Hodnota √2 pochází z pravidla UCB1 pro mnohoruké bandity (Auer, Cesa-Bianchi a Fischer, 2002) pro výsledky v ⟨0, 1⟩; na stromy ho přenesli Kocsis a Szepesvári (2006). V praxi se ladí
ln N: roste s počtem návštěv rodiče, ale jen pomalu. Díky němu bonus málo zkoušených tahů pomalu roste: každý tah se dřív nebo později zkusí znovu
n_i: kolikrát už byl tah zkoušen — ve jmenovateli, takže čím méně ho známe, tím větší bonus. Odmocnina odpovídá (zjednodušeně) tomu, jak rychle se zpřesňuje průměr: jeho nejistota klesá jako 1/√n

Druhý člen dohromady je prozkoumávání. Jeho vliv slábne, jak tah sbírá návštěvy, ale protože ln N roste, nespadne nikdy na nulu.

Pusťme MCTS na pozici, kterou minimax rozluštil výše. Čísla v políčkách jsou návštěvy po 100, 300 a 1000 iteracích, pod nimi průměrný výsledek pro X:

MCTS v téže pozici: kolikrát který tah navštívil nahoře návštěvy, dole průměrný výsledek pro X

Po 100 iteracích má střed 47 návštěv a ostatní tahy dohromady víc. Po tisíci jich má 856 a průměrný výsledek 0,94; remízový tah dole uprostřed dostal 52 návštěv, prohrávající tahy ještě méně. MCTS přitom nezná ani pojem vidlička, ani žádnou ohodnocovací funkci — jen pravidla a náhodu. A přesto našel stejný tah jako minimax, který musel projít celý zbytek stromu.

Proč zrovna takové rozložení návštěv? Spočítejme UCT tahů z kořene po 1000 iteracích (N = 1000, ln N ≈ 6,908, c = √2; barvy podle vzorce výše):

tah	`n`_i	`w`_i/`n`_i	bonus `c` · √ln `N`/`n`_i	`UCT`
vpravo nahoře (2)	27	0,333	0,715	1,049
střed (4)	856	0,941	0,127	1,068
vpravo uprostřed (5)	30	0,383	0,679	1,062
dole uprostřed (7)	52	0,548	0,515	1,064
vpravo dole (8)	35	0,429	0,628	1,057

Hodnoty UCT jsou skoro stejné — v rozmezí 1,049 až 1,068. Není to náhoda: výběr pokaždé navštíví tah s nejvyšším UCT, a tím mu sníží bonus (průměr se přitom změní jen málo), takže se hodnoty postupně vyrovnají. Střed má nejlepší průměr, a proto mu na vyrovnání stačí malý bonus — tedy hodně návštěv. Ostatní tahy mají horší průměr a dorovnávají ho velkým bonusem, na který stačí málo návštěv. (Součty v tabulce počítáme z nezaokrouhlených hodnot, v posledním místě se proto mohou lišit o 1.)

8. Od Deep Blue k AlphaZero

Deep Blue (1997) porazil mistra světa Garriho Kasparova. Uvnitř byla alfa-beta s ručně psanou ohodnocovací funkcí a specializovaný hardware, který zvládl kolem 200 milionů pozic za sekundu.
Chinook hrál dámu proti mistrům světa už v 90. letech a v roce 2007 jeho autoři hru vyřešili: prošli tolik pozic, že dokázali, že bezchybná partie končí remízou — stejně jako piškvorky 3 × 3.
AlphaGo (2016) porazil Lee Se-dola 4 : 1. Spojil MCTS s neuronovými sítěmi: jedna síť navrhovala slibné tahy (místo náhodného výběru), druhá odhadovala hodnotu pozice (místo celé náhodné dohrávky).
AlphaZero (2017) zahodil i lidské partie. Naučil se šachy, šogi a go jen hraním sám proti sobě — zpětnovazebním učením — a v každé z her porazil nejlepší dosavadní program.
Hry s náhodou a skrytou informací potřebují víc. V backgammonu rozhoduje kostka, takže se do stromu přidávají uzly náhody se střední hodnotou (expectiminimax). V pokeru nevidíte soupeřovy karty; program Libratus (2017) přesto porazil profesionály v pokeru dvou hráčů.

Definice — expectiminimax

Nechť Γ = (S, s₀, hráč, A, T, K, U) je konečná hra jako v definici hry dvou hráčů, jen ke hráčům MAX a MIN přibude „hráč“ NÁHODA: hráč : S ∖ K → {MAX, MIN, NÁHODA} a podmínka střídání se nevyžaduje. Pro každý stav s s hráč(s) = NÁHODA je A(s) konečná neprázdná množina možných výsledků náhody r (třeba čísel na kostce) a je dáno rozdělení pravděpodobnosti P_s : A(s) → [0, 1] s ∑_{r ∈ A(s)} P_s(r) = 1 (viz díl o pravděpodobnosti); výsledek r nastane s pravděpodobností P_s(r) a vede do stavu T(s, r).

Expectiminimaxová hodnota je funkce EMM : S → ℝ definovaná rekurzivně:

EMM(s) = U(s), je-li s ∈ K;
EMM(s) = max_{a ∈ A(s)} EMM(T(s, a)), je-li hráč(s) = MAX;
EMM(s) = min_{a ∈ A(s)} EMM(T(s, a)), je-li hráč(s) = MIN;
je-li hráč(s) = NÁHODA, je EMM(s) střední hodnota hodnot následníků: EMM(s) = ∑_{r ∈ A(s)} P_s(r) · EMM(T(s, r)).

V uzlech MAX a MIN se tedy hodnota počítá jako u minimaxu a v uzlech náhody jako průměr vážený pravděpodobnostmi výsledků. Rozbor posledního vzorce (P_s zkráceně jako P):

EMM(s) = ∑_r P(r) · EMM(T(s, r))

EMM(s): hodnota uzlu náhody — co může MAX od pozice čekat v průměru, protože výsledek hodu neovlivní ani on, ani soupeř
∑_r: přes všechny možné výsledky náhody; místo výběru nejlepšího (max) nebo nejhoršího (min) se tu nevybírá nic — započítá se každý
P(r): pravděpodobnost výsledku jako váha: častý výsledek ovlivní hodnotu víc než vzácný
EMM(T(s, r)): hodnota pozice po daném výsledku, spočítaná rekurzivně stejným pravidlem

Hod mincí: panna (s pravděpodobností 1/2) vede do pozice s hodnotou 4, orel (1/2) do pozice s hodnotou −2. EMM = 1/2 · 4 + 1/2 · (−2) = 2 − 1 = 1. Tah do jisté pozice s hodnotou 0,5 je tedy horší, i když nehrozí ztráta.

Myšlenka „podívej se dopředu, než něco uděláš“ ze šachovnic nezmizela. Plánující jazykoví agenti zkoušejí několik variant postupu, ohodnotí je a pokračují tou nejslibnější — jen místo tahů figur volí kroky řešení.

9. Shrnutí

Hra dvou hráčů s nulovým součtem je úloha prohledávání, ve které se o tahy dělíte se soupeřem; řešením je strategie, ne cesta.
Minimax počítá hodnotu odzadu: MAX bere maximum, MIN minimum. Výsledek je zaručený proti jakémukoli soupeři.
Alfa-beta vrátí stejnou hodnotu, ale ořízne větve, které výsledek nemůžou změnit; s dobrým pořadím tahů dohlédne dvakrát hlouběji.
Velké hry se prohledávají do omezené hloubky s ohodnocovací funkcí — a pozor na efekt horizontu.
MCTS místo ohodnocení pozici mnohokrát náhodně dohraje a strom rozvíjí tam, kde je to slibné; s neuronovými sítěmi z něj vznikl AlphaGo.

Chcete si to osahat? Nechte AI agenta napsat piškvorky s minimaxem a pak spočítejte, kolik pozic ušetří alfa-beta, když tahy seřadíte od středu k okrajům.

Máte na to jiný názor? Napište na support@coden-app.com.

Hry a protivník: minimax, alfa-beta ořezávání a Monte Carlo tree search

1. Hra jako úloha prohledávání

2. Herní strom

3. Minimax

4. Minimax na piškvorkách

5. Alfa-beta ořezávání

6. Omezená hloubka a ohodnocovací funkce

7. Monte Carlo tree search

8. Od Deep Blue k AlphaZero

9. Shrnutí

Agent na vašem počítači, ovládaný z telefonu