Hry a protivník: minimax, alfa-beta orezávanie a Monte Carlo tree search

Hra ako úloha prehľadávania, herný strom, minimax, alfa-beta orezávanie, hodnotiaca funkcia a MCTS — na piškvorkách, kde sa dá spočítať všetko, a s cestou od Deep Blue k AlphaZero.

14 minút Matěj Žalmánek 2026-10-15

Séria Základy AI Diel 22 z 52

Celá osnova série Hotovo: 52 z 83 tém

Čo si odnesiete

Ako sa hra dvoch hráčov zapíše ako úloha prehľadávania a prečo je riešením stratégia, nie cesta.
Ako minimax vypočíta zaručenú hodnotu pozície a prečo alfa-beta dospeje k rovnakému výsledku oveľa rýchlejšie.
Ako Monte Carlo tree search nájde dobrý ťah bez hodnotiacej funkcie a čo z neho urobil AlphaGo.

Čo sa hodí vedieť vopred: Prehľadávanie stavového priestoru: BFS, DFS, UCS a A* s animáciami, Grafy a stromy: štruktúra, na ktorej stojí hľadanie aj neurónové siete

V bludisku z minulého dielu stál panáčik sám. Svet sa nehýbal a každý ťah viedol tam, kam mal. V hre však sedí oproti vám niekto, kto chce presný opak — a na každý váš ťah odpovie tým, ktorý vás bolí najviac. Hľadať cestu k cieľu už nestačí: musíte hľadať stratégiu, ktorá obstojí proti každej odpovedi. Šach, dáma aj go boli desiatky rokov meradlom umelej inteligencie a algoritmy z tohto dielu stoja za Deep Blue aj za AlphaGo.

Nadväzuje na diely Prehľadávanie stavového priestoru a Grafy a stromy.

1. Hra ako úloha prehľadávania

Definícia — hra dvoch hráčov

Hra dvoch hráčov (deterministická, s úplnou informáciou a nulovým súčtom) je sedmica

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

ktorá spĺňa:

S je neprázdna množina stavov (pozícií) a s₀ ∈ S je počiatočný stav;
K ⊆ S je množina koncových stavov — v nich sa hra skončí;
hráč : S ∖ K → {MAX, MIN} určuje, kto je v stave na ťahu;
A priraďuje každému stavu s ∈ S ∖ K konečnú neprázdnu množinu A(s) ťahov (akcií) a v koncových stavoch A(s) = ∅;
T je prechodová funkcia: pre s ∈ S ∖ K a a ∈ A(s) je T(s, a) ∈ S stav po ťahu a (ťahy sú deterministické);
hráči sa striedajú: ak je s ∈ S ∖ K, a ∈ A(s) a T(s, a) ∉ K, potom hráč(T(s, a)) ≠ hráč(s);
U : K → ℝ je úžitok koncového stavu z pohľadu hráča MAX; úžitok hráča MIN je −U (nulový súčet: U(s) + (−U(s)) = 0 pre každé s ∈ K).

Obaja hráči poznajú celú sedmicu a v každom okamihu vidia aktuálny stav (úplná informácia). Hra je konečná práve vtedy, keď neexistuje nekonečná postupnosť s₀, s₁, s₂, … s s_i = T(s_i−1, a_i) pre nejaké a_i ∈ A(s_i−1) — každá partia teda po konečne mnohých ťahoch skončí v K. Všetky hry v tomto diele sú konečné.

Stratégia hráča MAX je funkcia σ, ktorá každému stavu s ∈ S ∖ K s hráč(s) = MAX priradí ťah σ(s) ∈ A(s); stratégia τ hráča MIN je definovaná rovnako pre stavy s hráč(s) = MIN. Dvojica stratégií (σ, τ) jednoznačne určí partiu zo stavu s₀ a tým aj jej úžitok.

Laicky povedané

Hra je bludisko, v ktorom sa o ťahy delíte so súperom. Na konci sa spočíta skóre — v piškvorkách +1, keď vyhrá MAX, −1, keď vyhrá MIN, a 0 za remízu. MAX chce skóre čo najvyššie, MIN čo najnižšie. „Nulový súčet“ znamená, že sa nedá vyhrať spoločne: čo jeden získa, druhý stratí.

Rozdiel oproti prehľadávaniu je zásadný. Riešením už nie je cesta — tú si nevyberiete, pretože každý druhý ťah robí súper. Riešením je stratégia: predpis, ako odpovedať na každý ťah, ktorý súper môže zahrať.

2. Herný strom

Definícia — herný strom

Nech Γ = (S, s₀, hráč, A, T, K, U) je konečná hra dvoch hráčov. Herný strom hry Γ je koreňový strom (pozri diel Grafy a stromy), pre ktorý platí:

uzly sú všetky postupnosti ťahov (a₁, …, a_k), k ≥ 0, ktoré sa dajú zo s₀ zahrať, t. j. s_i−1 ∉ K, a_i ∈ A(s_i−1) a s_i = T(s_i−1, a_i) pre i = 1, …, k; uzlu prislúcha stav s_k;
koreň je prázdna postupnosť () so stavom s₀;
deti uzla (a₁, …, a_k) so stavom s_k ∉ K sú uzly (a₁, …, a_k, a) pre všetky a ∈ A(s_k) so stavmi T(s_k, a);
listy sú práve uzly, ktorých stav je koncový (s_k ∈ K).

Uzol teda nie je pozícia, ale história, ktorá k nej viedla — do rovnakého stavu sa dá dostať rôznymi postupnosťami ťahov a v strome sa potom objaví viackrát. Uzly, kde je na ťahu MAX, kreslíme ako trojuholník špičkou nahor, uzly MIN špičkou nadol.

Nech b = max_{s ∈ S ∖ K} |A(s)| je faktor vetvenia a m najväčšia dĺžka partie (počet ťahov). Potom má strom najviac b^m listov.

Laicky povedané

Všetky partie, ktoré sa dajú odohrať, nakreslené ako rozvetvený strom: z koreňa vedie jedna vetva pre každý prvý ťah, z každej z nich vetva pre každú odpoveď a tak ďalej, až po koniec hry. Jeden list = jedna dohraná partia.

Piškvorky na hracom poli 3 × 3 sú malá hra, a predsa má ich strom 549 946 uzlov a 255 168 listov — toľko rôznych partií sa dá odohrať. Rôznych pozícií je pritom len 5 478: do rovnakej pozície sa dostanete mnohými poradiami ťahov. Šach má faktor vetvenia okolo 35 a partia trvá desiatky ťahov; Claude Shannon v roku 1950 odhadol jeho strom na 10¹²⁰ partií. Go s faktorom vetvenia okolo 250 je ešte o mnoho rádov ďalej. Celý strom teda prejdeme len pri malých hrách — pri veľkých sa musíme naučiť, ktoré vetvy vynechať.

Príklad — horný odhad stromu piškvoriek a Shannonovo číslo

Keby sa piškvorky hrali vždy až do zaplnenia poľa, mal by strom v hĺbke k práve 9 · 8 · … · (9 − k + 1) = 9!/(9 − k)! uzlov (k = 0, …, 9). Spolu

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

Skutočný strom má 549 946 uzlov a 255 168 listov, pretože partia, v ktorej niekto zloží tri v rade, končí skôr a jej vetva sa ďalej nevetví. Odhad b^m je teda horná hranica; tu s b klesajúcim od 9 k 1.

Shannon (Programming a Computer for Playing Chess, 1950) počítal pre šach s asi 10³ možnosťami na jednu dvojicu ťahov (biely a čierny) a typickou partiou so 40 dvojicami ťahov: (10³)⁴⁰ = 10¹²⁰. Je to hrubý rádový odhad, nie presné číslo.

3. Minimax

Definícia — minimaxová hodnota

Nech Γ = (S, s₀, hráč, A, T, K, U) je konečná hra dvoch hráčov. Minimaxová hodnota je funkcia MM : S → ℝ definovaná rekurzívne pre každé s ∈ S:

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

Rekurzia je dobre definovaná: hra je konečná, takže každý reťazec rekurzívnych volaní skončí v koncovom stave, a A(s) je konečná neprázdna, takže maximum aj minimum existujú.

Ťah a* ∈ A(s) je optimálny ťah hráča MAX v stave s s hráč(s) = MAX práve vtedy, keď

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

optimálny ťah hráča MIN je obdobne prvok argmin. Stratégia, ktorá v každom stave volí optimálny ťah, je minimaxová stratégia.

Laicky povedané

Hodnotu pozície vypočítate odzadu. Na konci hry ju poznáte — je to skóre. O ťah skôr: keď hrá MAX, vyberie si to najlepšie z toho, čo ho čaká; keď hrá MIN, vyberie to najhoršie pre MAX. Takto sa hodnoty prelievajú poschodie po poschodí nahor až ku koreňu. Je to presne úvaha „keď pôjdem sem, on pôjde tam, a potom ja…“, len dotiahnutá do konca.

Minimax: hodnoty prebublávajú od listov ku koreňu

Uzol MIN vľavo si z listov 4, 6 a 9 vyberie 4, prostredný z 2, 7 a 8 vyberie 2, pravý z 5, 3 a 9 vyberie 3. MAX v koreni potom volí medzi 4, 2 a 3 a zahrá ľavý ťah s hodnotou 4. Všimnite si, že pravá vetva skrýva deviatku — lenže na ňu MAX nikdy nedosiahne, pretože MIN by namiesto nej zahral trojku.

Veta — čo minimax zaručuje

Nech Γ je konečná hra dvoch hráčov a σ* minimaxová stratégia hráča MAX. Potom

pre každú stratégiu τ hráča MIN má partia hraná dvojicou (σ*, τ) úžitok ≥ MM(s₀);
ak je aj τ* minimaxová stratégia hráča MIN, má partia hraná dvojicou (σ*, τ*) úžitok práve MM(s₀).

Dôkaz (náčrt), indukciou podľa výšky uzla: v liste MAX získa presne U(s) = MM(s). V uzle MAX zahrá ťah do dieťaťa s najväčšou hodnotou a podľa indukčného predpokladu si v ňom ubráni aspoň túto hodnotu, teda aspoň MM(s). V uzle MIN si súper vyberie ľubovoľné dieťa, ale každé má hodnotu ≥ min = MM(s), a v každom si MAX podľa predpokladu ubráni aspoň jeho hodnotu. Pre s = s₀ je to bod 1. Rovnakou úvahou s vymenenými rolami si MIN minimaxovou stratégiou τ* zaistí úžitok najviac MM(s₀) proti každej stratégii MAX; obe nerovnosti spolu dávajú bod 2. ∎

Minimax prechádza strom do hĺbky: čas O(b^m), pamäť O(b · m).

Laicky povedané

Minimax počíta s najhorším: predpokladá, že súper nikdy neurobí chybu. Keď ju urobí, dopadnete len lepšie. Preto je minimaxová hodnota zaručená — to, čo si ubránite, nech súper hrá akokoľvek.

4. Minimax na piškvorkách

Piškvorky 3 × 3 sú dosť malé na to, aby minimax prešiel celý strom. Výsledok pozná každý, kto ich hral dlhšie než pár minút: minimaxová hodnota prázdneho poľa je 0 — keď obaja hrajú bez chyby, je to vždy remíza. Zaujímavejšie je, čo minimax povie o konkrétnej pozícii. Na ťahu je X (MAX) a v každom voľnom políčku je hodnota ťahu naň:

Hodnota každého ťahu X podľa minimaxu +1 výhra0 remíza−1 prehra

Vyhráva jediný ťah — stred. X tým postaví vidličku: hrozí dokončiť prostredný riadok aj uhlopriečku a O nemôže zablokovať oboje. Ťah dole do stredu drží remízu. Zvyšné tri ťahy vyzerajú nevinne, ale prehrávajú: O na ne odpovie vlastnou vidličkou. Človek by to musel premyslieť; minimax to jednoducho vypočíta.

def minimax(deska):
    konec = vitez(deska)                 # "X", "O", "remiza" alebo 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 orezávanie

Minimax prejde celý strom, aj keď je z polovice zbytočný. Pozrite sa znova na prostrednú vetvu: prvý list ukázal 2. MIN teda v tej vetve dosiahne 2 alebo menej — a MAX už má ľavú vetvu s hodnotou 4 istú. Nech sú zvyšné dva listy akékoľvek, MAX do prostrednej vetvy nepôjde. Nemusí sa na ne ani pozerať.

Definícia — alfa-beta

Nech Γ je konečná hra dvoch hráčov. Alfa-beta je prehľadávanie do hĺbky, ktoré si so sebou nesie dve hranice α, β ∈ ℝ ∪ {−∞, +∞}:

α — najvyššia hodnota, ktorú si MAX už zaistil niekde na ceste od koreňa (na začiatku −∞);
β — najnižšia hodnota, ktorú si už zaistil MIN (na začiatku +∞).

Funkcia AB(s, α, β) pre stav s ∈ S:

Ak je s ∈ K, vráť U(s).
Ak je hráč(s) = MAX, polož v ← −∞; inak v ← +∞.
Pre ťahy a ∈ A(s) postupne (v pevnom poradí) vypočítaj h ← AB(T(s, a), α, β) a
- v uzle MAX polož v ← max(v, h) a α ← max(α, v),
- v uzle MIN polož v ← min(v, h) a β ← min(β, v);
hneď ako α ≥ β, zvyšné ťahy sa orežú — neprehľadávajú sa — a pokračuje sa krokom 4.
Vráť v.

Alfa-beta v koreni je volanie AB(s₀, −∞, +∞).

Veta. Nech Γ je konečná hra dvoch hráčov. Potom AB(s₀, −∞, +∞) = MM(s₀) — alfa-beta vráti v koreni rovnakú hodnotu ako minimax (vo vnútorných uzloch, kde došlo k orezu, vracia len hranicu, nie presnú hodnotu). Ak má strom faktor vetvenia b a hĺbku m a ak sú ťahy zoradené v najlepšom možnom poradí, preskúma alfa-beta len O(b^m/2) uzlov.

Laicky povedané

α je „toto už mám vo vrecku“, β je „viac mi súper aj tak nedovolí“. Keď v nejakej vetve zistíte, že súper vás v nej môže zraziť pod to, čo už máte isté inde, nemá zmysel ju skúmať ďalej — stačí jediný vyvracajúci ťah. Hodnota v koreni zostane rovnaká, len ju nájdete rýchlejšie.

orež, keď α ≥ β

α: to najlepšie, čo si MAX už zaistil inde na ceste od koreňa. Do vetvy, ktorá dá menej, nikdy nepôjde — má lepšiu voľbu
β: to najhoršie pre MAX, čo mu MIN v tejto vetve už môže vnútiť. Viac než β odtiaľto MAX nedostane, nech zvyšné deti vyjdú akokoľvek
≥: okno [α, β] je prázdne: hodnota, o ktorú by sa tu ešte dalo hrať, by musela byť zároveň aspoň α a najviac β. Taká neexistuje (pri rovnosti by nebola lepšia, než čo MAX už má), takže zvyšok vetvy koreň nemôže ovplyvniť

V prostrednej vetve stromu: α = 4 (ľavá vetva), po prvom liste β = 2. Keďže 4 ≥ 2, listy 7 a 8 sa neskúmajú.

Alfa-beta na rovnakom strome: čísla sú poradie návštev pri uzloch okno α, β; oranžovo, keď α ≥ β a zvyšok vetvy sa orežeorezaných listov: 3 / 9

Alfa-beta dospela k rovnakému výsledku — MAX hrá vľavo a získa 4 — ale ohodnotila len 6 listov z 9. V prostrednej vetve orezala dva listy hneď po dvojke, v pravej jeden po trojke. Pri orezanom uzle MIN je preto len hranica „≤ 2“ a „≤ 3“: presnú hodnotu nepoznáme, a nepotrebujeme ju.

To isté, čo animácia ukazuje pri uzloch, krok po kroku v tabuľke. Riadok zachytáva okno uzla pri vstupe doň a potom po každom dieťati, ktoré vrátilo hodnotu:

krok	uzol	čo sa 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 vracia 4
6	A (MAX)	B vrátil 4	4	+∞
7	C (MIN)	vstup	4	+∞
8	C (MIN)	c1 vrátil 2	4	2	α ≥ β: orez c2, c3; C vracia len hranicu ≤ 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	α ≥ β: orez d3; D vracia len hranicu ≤ 3
13	A (MAX)	D vrátil 3	4	+∞	A vracia 4

Uzol MIN dostane od rodiča α = 4 a mení len svoje β; uzol MAX naopak mení len α. Okno každého uzla sa tak len zužuje. V pravej vetve prvý list (5) orez nevyvolá — 5 je viac než 4, MIN by tu MAXovi mohol dať viac než vľavo —, až druhý list (3) stiahne β pod α.

Na piškvorkách je rozdiel dramatickejší. Úplný minimax z prázdneho poľa navštívi 549 946 pozícií, alfa-beta s rovnakým poradím ťahov len 18 297 — asi tridsaťkrát menej — a vráti rovnakú nulu. Exponent m/2 vo vete znamená, že za rovnaký čas dovidíte dvakrát hlbšie. Preto na poradí ťahov toľko záleží: šachové programy skúšajú ako prvé brania a ťahy, ktoré boli dobré minule.

Príklad — koľko listov ušetrí alfa-beta pri najlepšom poradí

Presnú hranicu dokázali D. E. Knuth a R. W. Moore (An Analysis of Alpha-Beta Pruning, 1975): v strome s faktorom vetvenia b a hĺbkou d ohodnotí alfa-beta pri najlepšom poradí ťahov

b^⌈d/2⌉ + b^⌊d/2⌋ − 1 listov namiesto b^d.

Šach, b = 35, hĺbka d = 6 polťahov: minimax 35⁶ = 1 838 265 625 listov, alfa-beta 35³ + 35³ − 1 = 42 875 + 42 875 − 1 = 85 749 listov — asi 21 000-krát menej. A naopak: 12 polťahov prejde alfa-beta s 35⁶ + 35⁶ − 1 ≈ 3,7 · 10⁹ listami, teda len za dvojnásobok práce, ktorú minimax potrebuje na 6 polťahov.

Malý strom z obrázka (b = 3, d = 2): hranica je 3 + 3 − 1 = 5 listov. Alfa-beta ich ohodnotila 6, pretože poradie listov nie je najlepšie možné — v pravej vetve stojí trojka až na druhom mieste.

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                          # orez: zvyšok vetvy nič nezmení
    return v

6. Obmedzená hĺbka a hodnotiaca funkcia

Ani alfa-beta neprejde šachový strom do konca partie. Skutočné programy preto hľadajú len do pevnej hĺbky a pozíciu, v ktorej skončia, odhadnú.

Definícia — minimax s obmedzenou hĺbkou

Nech Γ = (S, s₀, hráč, A, T, K, U) je hra dvoch hráčov. Hodnotiaca funkcia je funkcia E : S → ℝ taká, že E(s) = U(s) pre všetky s ∈ K; pre s ∉ K je E(s) odhad MM(s). Zvyčajne je to vážený súčet n ≥ 1 príznakov pozície f₁, …, f_n : S → ℝ s váhami w₁, …, w_n ∈ ℝ:

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

Minimax s obmedzenou hĺbkou je pre každé d ∈ ℕ₀ funkcia MM_d : S → ℝ definovaná rekurzívne podľa d:

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

Hodnota MM_d(s) teda počíta minimax len d polťahov dopredu a pozície, v ktorých skončí, nahradí odhadom E. Ak je d aspoň dĺžka najdlhšej partie zo s, je MM_d(s) = MM(s).

Laicky povedané

Neviete domyslieť partiu do konca, tak sa pozriete pár ťahov dopredu a spýtate sa: „Ako dobre to tu vyzerá?“ V šachu je najjednoduchšia odpoveď spočítať materiál — pešiak 1, jazdec a strelec 3, veža 5, dáma 9 — a odčítať súperov. Lepšie funkcie pridajú aktivitu figúr, bezpečnosť kráľa alebo štruktúru pešiakov.

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

E(s): odhad hodnoty pozície z pohľadu MAX (bieleho) — dosadí sa tam, kde hľadanie skončí, namiesto skutočnej minimaxovej hodnoty
∑_i: cez druhy figúr: pešiak, jazdec, strelec, veža, dáma. Súčet, pretože materiál rôznych figúr sa v najjednoduchšom modeli jednoducho sčíta
w_i: cena figúry: 1, 3, 3, 5, 9. Váha prevádza „kusy“ na spoločnú menu, aby sa dala porovnať veža s dvoma jazdcami
p_i − p′_i: koľko figúr daného druhu má biely viac než čierny. Rozdiel, nie počet, pretože hra má nulový súčet: čo má súper navyše, je strata

Biely má o jazdca viac, čierny o dvoch pešiakov viac: E = 3 · (+1) + 1 · (−2) = +1, teda mierna výhoda bieleho. Ceny figúr sú tradičná šachová konvencia, nie výsledok výpočtu.

def minimax_d(s, d):
    if je_konec(s) or d == 0:
        return E(s)                        # ďalej nevidíme: odhad namiesto skutočnej 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 ťahu MAX
    d, nejlepsi = 1, None
    while zbyva(cas):
        nejlepsi = max(akce(s), key=lambda a: minimax_d(T(s, a), d - 1))
        d += 1                             # ďalšie kolo o polťah hlbšie
    return nejlepsi

Obmedzená hĺbka má svoju pascu: efekt horizontu. Keď hľadanie skončí uprostred výmeny figúr — vy ste práve vzali dámu, súper ju o ťah vezme späť —, hodnotiaca funkcia vidí len prvú polovicu a pozíciu precení. Programy sa bránia tým, že „nepokojné“ pozície prehľadávajú ďalej, kým sa neupokoja. A pretože nikdy nevedia, koľko majú času, hľadajú iteratívnym prehlbovaním z minulého dielu: hĺbka 1, 2, 3, … kým nedôjde čas. Výsledky plytkých prechodov navyše poslúžia ako poradie ťahov pre hlbšie — a alfa-beta potom orezáva oveľa viac.

7. Monte Carlo tree search

Hodnotiacu funkciu pre šach ľudia ladili desiatky rokov. Pre go sa ju napísať nedarilo — pozícia, ktorá vyzerá pokojne, môže byť o dvadsať ťahov neskôr prehraná. Monte Carlo tree search (MCTS) na hodnotiacu funkciu úplne rezignuje. Namiesto odhadu pozíciu dohrá: náhodne, mnohokrát, a pozrie sa, ako často to dopadlo dobre.

Definícia — jedna iterácia MCTS

Nech Γ = (S, s₀, hráč, A, T, K, U) je konečná hra dvoch hráčov, v ktorej má každá partia výsledok výhra, remíza, alebo prehra. Vstup: stav s₀ ∉ K (koreň) a počet iterácií (alebo časový limit). Výstup: ťah a ∈ A(s₀).

MCTS buduje prehľadávací strom — časť herného stromu, ktorá začína len koreňom a v každej iterácii sa o jeden uzol rozrastie. Každý uzol i stromu si pamätá:

počet návštev n_i ∈ ℕ₀ — koľko simulácií prešlo uzlom;
súčet výsledkov w_i ∈ [0, n_i] z pohľadu hráča, ktorý do uzla ťahal, pričom výsledok jednej partie je 1 za výhru, ½ za remízu a 0 za prehru.

Uzol je plne rozšírený práve vtedy, keď má v strome dieťa pre každý ťah a ∈ A(s) svojho stavu s. Jedna iterácia MCTS má štyri kroky:

Výber — začni v koreni; kým je aktuálny uzol plne rozšírený a jeho stav nie je koncový, prejdi do dieťaťa s najvyššou hodnotou UCT (definícia nižšie).
Rozšírenie — ak stav aktuálneho uzla nie je koncový, vyber doteraz neskúšaný ťah a, pridaj dieťa so stavom T(s, a) a n = w = 0 a prejdi doň.
Simulácia — zo stavu aktuálneho uzla dohraj partiu náhodnými ťahmi (každý z A(s) s rovnakou pravdepodobnosťou) až do koncového stavu s_K ∈ K.
Spätné šírenie — každému uzlu i na ceste od aktuálneho uzla späť ku koreňu (vrátane oboch) polož n_i ← n_i + 1 a w_i ← w_i + výsledok partie s_K z pohľadu hráča, ktorý do uzla i ťahal.

Iterácie sa opakujú, kým nevyprší počet iterácií alebo čas. Potom sa zahrá ťah z koreňa do dieťaťa s najväčším n_i.

Laicky povedané

Ako keď sa rozhodujete medzi reštauráciami: chodíte tam, kde vám zatiaľ chutilo najviac, ale občas skúsite aj inú. Každý ťah dostane šancu, sľubné ťahy dostanú viac pokusov a strom rastie práve tam, kde sa hrá o veľa. Náhodné dohrávky sú hlúpe, lenže keď ich je tisíc, priemer už niečo hovorí.

Štyri kroky jednej iterácie MCTS

def mcts(koren, iteraci):
    for _ in range(iteraci):
        u = koren
        while u.vsechny_deti() and u.deti:         # 1. výber
            u = max(u.deti, key=uct)
        if u.nezkusene and not je_konec(u.stav):   # 2. rozšírenie
            u = u.pridej_dite(nahodny(u.nezkusene))
        s = u.stav
        while not je_konec(s):                     # 3. simulácia
            s = T(s, nahodny(akce(s)))
        while u is not None:                       # 4. spätné šírenie
            u.n += 1
            u.w += vysledek(s, pro=u.kdo_tahl)     # 1, ½ alebo 0
            u = u.rodic
    return max(koren.deti, key=lambda d: d.n).tah

Definícia — UCT

Nech uzol prehľadávacieho stromu MCTS má N ≥ 1 návštev a deti i = 1, …, k, každé s n_i ≥ 1 návštevami a súčtom výsledkov w_i ∈ [0, n_i] (značenie z definície MCTS vyššie). Nech c > 0 je pevná konštanta prieskumu, zvyčajne c = √2. Hodnota UCT (Upper Confidence bounds applied to Trees) dieťaťa i je

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

V kroku výberu sa volí dieťa i* ∈ argmax_{i ∈ {1, …, k}} UCT(i). Kocsis a Szepesvári (2006) dokázali, že s rastúcim počtom iterácií pravdepodobnosť, že MCTS s UCT odporučí iný než minimaxovo optimálny ťah, klesá k nule.

Laicky povedané

Prvý člen je „ako dobre to zatiaľ dopadalo“, druhý „ako málo to poznám“. Ťah, ktorý ste dlho neskúsili, dostáva bonus, ktorý s každou návštevou iného ťahu pomaly rastie. Je to rovnaká dilema ako pri učení posilňovaním: využívať to, čo funguje, alebo preskúmavať, čo by mohlo fungovať lepšie?

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

UCT(i): skóre dieťaťa i vo výbere; vyhrá najväčšie. Nie je to odhad hodnoty ťahu, ale „ako veľmi sa oplatí ho skúsiť znova“
w_i/n_i: priemerný výsledok ťahu (0 až 1) — využívanie: ťahy, ktoré zatiaľ vychádzali dobre, dostanú prednosť
c: konštanta prieskumu — koľko váži zvedavosť oproti doterajším výsledkom. Hodnota √2 pochádza z pravidla UCB1 pre mnohorukých banditov (Auer, Cesa-Bianchi a Fischer, 2002) pre výsledky v ⟨0, 1⟩; na stromy ho preniesli Kocsis a Szepesvári (2006). V praxi sa ladí
ln N: rastie s počtom návštev rodiča, ale len pomaly. Vďaka nemu bonus málo skúšaných ťahov pomaly rastie: každý ťah sa skôr či neskôr skúsi znova
n_i: koľkokrát už bol ťah skúšaný — v menovateli, takže čím menej ho poznáme, tým väčší bonus. Odmocnina zodpovedá (zjednodušene) tomu, ako rýchlo sa spresňuje priemer: jeho neistota klesá ako 1/√n

Druhý člen dohromady je preskúmavanie. Jeho vplyv slabne, ako ťah zbiera návštevy, ale pretože ln N rastie, nespadne nikdy na nulu.

Pustime MCTS na pozíciu, ktorú minimax rozlúštil vyššie. Čísla v políčkach sú návštevy po 100, 300 a 1000 iteráciách, pod nimi priemerný výsledok pre X:

MCTS v tej istej pozícii: koľkokrát ktorý ťah navštívil hore návštevy, dole priemerný výsledok pre X

Po 100 iteráciách má stred 47 návštev a ostatné ťahy dohromady viac. Po tisícke ich má 856 a priemerný výsledok 0,94; remízový ťah dole v strede dostal 52 návštev, prehrávajúce ťahy ešte menej. MCTS pritom nepozná ani pojem vidlička, ani žiadnu hodnotiacu funkciu — len pravidlá a náhodu. A predsa našiel rovnaký ťah ako minimax, ktorý musel prejsť celý zvyšok stromu.

Prečo práve také rozloženie návštev? Vypočítajme UCT ťahov z koreňa po 1000 iteráciách (N = 1000, ln N ≈ 6,908, c = √2; farby podľa vzorca vyššie):

ťah	`n`_i	`w`_i/`n`_i	bonus `c` · √ln `N`/`n`_i	`UCT`
vpravo hore (2)	27	0,333	0,715	1,049
stred (4)	856	0,941	0,127	1,068
vpravo v strede (5)	30	0,383	0,679	1,062
dole v strede (7)	52	0,548	0,515	1,064
vpravo dole (8)	35	0,429	0,628	1,057

Hodnoty UCT sú skoro rovnaké — v rozmedzí 1,049 až 1,068. Nie je to náhoda: výber zakaždým navštívi ťah s najvyšším UCT, a tým mu zníži bonus (priemer sa pritom zmení len málo), takže sa hodnoty postupne vyrovnajú. Stred má najlepší priemer, a preto mu na vyrovnanie stačí malý bonus — teda veľa návštev. Ostatné ťahy majú horší priemer a dorovnávajú ho veľkým bonusom, na ktorý stačí málo návštev. (Súčty v tabuľke počítame z nezaokrúhlených hodnôt, na poslednom mieste sa preto môžu líšiť o 1.)

8. Od Deep Blue k AlphaZero

Deep Blue (1997) porazil majstra sveta Garriho Kasparova. Vnútri bola alfa-beta s ručne písanou hodnotiacou funkciou a špecializovaný hardvér, ktorý zvládol okolo 200 miliónov pozícií za sekundu.
Chinook hral dámu proti majstrom sveta už v 90. rokoch a v roku 2007 jeho autori hru vyriešili: prešli toľko pozícií, že dokázali, že bezchybná partia končí remízou — rovnako ako piškvorky 3 × 3.
AlphaGo (2016) porazil Lee Se-dola 4 : 1. Spojil MCTS s neurónovými sieťami: jedna sieť navrhovala sľubné ťahy (namiesto náhodného výberu), druhá odhadovala hodnotu pozície (namiesto celej náhodnej dohrávky).
AlphaZero (2017) zahodil aj ľudské partie. Naučil sa šach, šogi a go len hraním sám proti sebe — učením posilňovaním — a v každej z hier porazil najlepší dovtedajší program.
Hry s náhodou a skrytou informáciou potrebujú viac. V backgammone rozhoduje kocka, takže sa do stromu pridávajú uzly náhody so strednou hodnotou (expectiminimax). V pokri nevidíte súperove karty; program Libratus (2017) napriek tomu porazil profesionálov v pokri dvoch hráčov.

Definícia — expectiminimax

Nech Γ = (S, s₀, hráč, A, T, K, U) je konečná hra ako v definícii hry dvoch hráčov, len k hráčom MAX a MIN pribudne „hráč“ NÁHODA: hráč : S ∖ K → {MAX, MIN, NÁHODA} a podmienka striedania sa nevyžaduje. Pre každý stav s s hráč(s) = NÁHODA je A(s) konečná neprázdna množina možných výsledkov náhody r (napríklad čísel na kocke) a je dané rozdelenie pravdepodobnosti P_s : A(s) → [0, 1] s ∑_{r ∈ A(s)} P_s(r) = 1 (pozri diel o pravdepodobnosti); výsledok r nastane s pravdepodobnosťou P_s(r) a vedie do stavu T(s, r).

Expectiminimaxová hodnota je funkcia EMM : S → ℝ definovaná rekurzívne:

EMM(s) = U(s), ak s ∈ K;
EMM(s) = max_{a ∈ A(s)} EMM(T(s, a)), ak hráč(s) = MAX;
EMM(s) = min_{a ∈ A(s)} EMM(T(s, a)), ak hráč(s) = MIN;
ak hráč(s) = NÁHODA, je EMM(s) stredná hodnota hodnôt nasledovníkov: EMM(s) = ∑_{r ∈ A(s)} P_s(r) · EMM(T(s, r)).

V uzloch MAX a MIN sa teda hodnota počíta ako pri minimaxe a v uzloch náhody ako priemer vážený pravdepodobnosťami výsledkov. Rozbor posledného vzorca (P_s skrátene ako P):

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

EMM(s): hodnota uzla náhody — čo môže MAX od pozície čakať v priemere, pretože výsledok hodu neovplyvní ani on, ani súper
∑_r: cez všetky možné výsledky náhody; namiesto výberu najlepšieho (max) alebo najhoršieho (min) sa tu nevyberá nič — započíta sa každý
P(r): pravdepodobnosť výsledku ako váha: častý výsledok ovplyvní hodnotu viac než zriedkavý
EMM(T(s, r)): hodnota pozície po danom výsledku, vypočítaná rekurzívne rovnakým pravidlom

Hod mincou: hlava (s pravdepodobnosťou 1/2) vedie do pozície s hodnotou 4, znak (1/2) do pozície s hodnotou −2. EMM = 1/2 · 4 + 1/2 · (−2) = 2 − 1 = 1. Ťah do istej pozície s hodnotou 0,5 je teda horší, aj keď nehrozí strata.

Myšlienka „pozri sa dopredu, než niečo urobíš“ zo šachovníc nezmizla. Plánujúci jazykoví agenti skúšajú niekoľko variantov postupu, ohodnotia ich a pokračujú tým najsľubnejším — len namiesto ťahov figúr volia kroky riešenia.

9. Zhrnutie

Hra dvoch hráčov s nulovým súčtom je úloha prehľadávania, v ktorej sa o ťahy delíte so súperom; riešením je stratégia, nie cesta.
Minimax počíta hodnotu odzadu: MAX berie maximum, MIN minimum. Výsledok je zaručený proti akémukoľvek súperovi.
Alfa-beta vráti rovnakú hodnotu, ale oreže vetvy, ktoré výsledok nemôžu zmeniť; s dobrým poradím ťahov dovidí dvakrát hlbšie.
Veľké hry sa prehľadávajú do obmedzenej hĺbky s hodnotiacou funkciou — a pozor na efekt horizontu.
MCTS namiesto ohodnotenia pozíciu mnohokrát náhodne dohrá a strom rozvíja tam, kde je to sľubné; s neurónovými sieťami z neho vznikol AlphaGo.

Chcete si to vyskúšať? Nechajte AI agenta napísať piškvorky s minimaxom a potom spočítajte, koľko pozícií ušetrí alfa-beta, keď ťahy zoradíte od stredu k okrajom.

Máte na to iný názor? Napíšte na support@coden-app.com.

Hry a protivník: minimax, alfa-beta orezávanie a Monte Carlo tree search

1. Hra ako úloha prehľadávania

2. Herný strom

3. Minimax

4. Minimax na piškvorkách

5. Alfa-beta orezávanie

6. Obmedzená hĺbka a hodnotiaca funkcia

7. Monte Carlo tree search

8. Od Deep Blue k AlphaZero

9. Zhrnutie

Agent na vašom počítači, ovládaný z telefónu