AdamátorZápiskyHlášky

Teorie her

Webová stránka předmětu

Známka je za řešení domácích úloh. Budou tři série, z každé máme vyřešit alespoň jednu úlohu, za čtyři úlohy celkem je A.

Část o kombinatorické teorii her přednáší Mgr. Jan Volec, Ph.D. Část o klasické teorii her nejspíš bude přednášet Mgr. Jan Hladký, Ph.D.

Motivační příklady

Hra sirky Na stole leží n sirek. Střídají se dva hráči. Každý může ve svém tahu odebrat jednu, dvě, nebo tři sirky. Vyhraje ten, kdo odebere poslední sirku.
Věta Je-li n=4k, potom vyhraje hráč, který nezačíná.
Důkaz Indukcí. Odebere-li první hráč j sirek, může jich druhý hráč odebrat 4−j, čímž na stole zbyde 4(k−1) sirek.
Důsledek Pro počet sirek nedělitelný 4 vyhraje začínající hráč.
Hra vlajka/Chop Mějme vlajku ve tvaru mřížky s m sloupci a n řádky. Levý dolní čtvereček je připevněný ke stožáru. Hráč na tahu může ustřihnout libovolný počet řádků nebo sloupců. Vyhraje ten, kdo vlajku zredukuje na jediný čtvereček.
Věta Je-li m=n, vyhraje hráč, který nezačíná.
Důkaz Indukcí. Ustřihne-li první hrač několik sloupců, resp. řádků, druhý ustřihne stejný počet řádků, resp. sloupců. Tím vznikne opět pozice, kde je stejný počet sloupců a řádků.
Důsledek Pro m≠n vyhraje začínající hráč.
Hra čokoláda/Chomp Máme tabulku čokolády s m sloupci a n řádky. Čtvereček vlevo dole je otrávený. Hráč na tahu ukáže na libovolný čtvereček a sní ho společně se všemi, co jsou od něj napravo a/nebo nahoře. Vyhraje překvapivě ten, kdo nesní otrávený čtvereček.

U této hry pro obecný tvar čokolády není známá obecná výherní strategie. Ale pro obdélníkovou čokoládu máme větu:

Věta Pro obdélníkovou cokoládu s více než jedním čtverečkem vyhraje první hráč.
Důkaz Předpokládejme pro spor, že pro nějaké m,n existuje výherní strategie pro druhého hráče. Potom ale první hráč může provést tah, který by druhý hráč podle výherní strategie měl provést, kdyby první hráč ukousnul pravý horní čtvereček. Tím první hráč vyhraje, což je spor.
Poznámka Technika použitá v tomto důkazu se nazývá kradení strategie.
Hra piškvorky Hrajme piškvorky na n×n mřížce (n2-škvorky). Vyhraje ten, kdo zaplní celý řádek, sloupec nebo diagonálu.
Věta První hráč má neprohrávající strategii.
Důkaz Předpokládejme pro spor, že existuje výherní strategie pro druhého hráče. Potom jako první hráč můžeme prostě zahrát libovolný tah a následně předstírat, že jsme druhý hráč. Pokud nás výherní strategie přinutí hrát na „mrtvé“ políčko, místo toho zahrajeme na nějaké jiné, které bude odteď „mrtvé“.
Hra Hex Máme šestiúhelníkovou mřížku ve tvaru kosočtverce, kam hráčí umísťují svoje kameny. Vyhraje ten, kdo propojí dvě protější strany (pro každého hráče jiné).
Věta První hráč má neprohrávající strategii.
Důkaz Stejný jako u piškvorek.

Pojmy

Definice Normální hra je hra, kde prohrává hráč, který nemůže táhnout.
Definice Kombinatorická hra s úplnou informací pro dva hráče je hra pro dva hráče 𝖫,𝖱 (Lízu a Richarda) charakterizovaná:
Definice Herní strom pro dva hráče je zakořeněný strom, určený hrou pro dva hřáče, počáteční pozicí a začínajícím hráčem. Počáteční pozice je kořen. Z pozice s vedou hrany do všech pozic f(s,h), kde h je hráč na řadě (obvykle se střídají).
Poznámka Budeme uvažovat jen takové hry, kde herní strom má konečnou velikost.
Definice Strategie pro hráče h je funkce Sh, která pro každý vrchol v herním stromě, kde je h na tahu, vybere jednoho potomka.
Poznámka Výsledek pro daný herní strom je jednoznačně určen dvojicí strategií S𝖫,S𝖱.
Definice Strategie S𝖱 (bez újmy na obecnosti pro Richarda) je vyhrávající, pokud pro každou strategii S𝖫 pro Lízu je výsledek −+.
Definice Herní strom je výherní (W), pokud existuje vyhrávající strategie pro začínajícího hráče.
Definice Herní strom je proherní (L), pokud existuje vyhrávající strategie pro nezačínajícího hráče.
Definice Herní strom je remízový (D), pokud existuje neprohrávající strategie pro oba hráče.
Definice Hloubka herního stromu je délka nejdelší možné cesty z počátečního do koncového stavu.
Věta Zermelova Každý herní strom pro dva hráče je právě jednoho z typů W, L, D.
Důkaz Indukcí podle hloubky stromu. Je-li hloubka 0, máme jen jeden uzel, takže je jednoznačně určeno, jak hra dopadne. V indukčním kroku mějme bez újmy na obecnosti herní strom, kde začíná Richard.
  • Pokud alespoň jedem podstrom je proherní, potom původní strom je výherní.
  • Pokud každý podstrom je výherní, potom původní strom je proherní.
  • V jiném případě je původní strom remízový.

Hex

Věta Nashova V každé vyplněné mřížce Hexu vyhraje právě jeden hráč.
Důkaz Představme si pro jednoduchost, že stěny, které má každý hráč propojit, obarvíme barvou tohoto hráče. Začneme v levém dolním rohu, kde vlevo je modrá a dole červená, a budeme postupně chodit po hranách tak, abychom vždy měli nalevo modrou barvu a napravo červenou barvu. Jelikož každý vrchol je stupně 3, vždy máme jednoznačně určeno, kam jít, a taky není těžké dokázat, že se nezacyklíme. Dorazíme až do nějakého jiného rohu, čímž jsme propojili nějaké stěny.
Poznámka Dá se také dokázat pomocí Brouwerovy věty o pevném bodě.
Důsledek První hráč má v Hexu výherní strategii.

Piškvorky

Definice Nechť a,d∈ℕ. Potom d-rozměrná hyperkrychle velikosti a je množina [a]d≕Ad.
Definice Dále budeme značit A∗≔A∪{∗}, kde ∗ je žolík. Vzor je slovo τ∈A∗d∖Ad. Kombinatorická přímka Lτ je množina bodů hyperkrychle, kde za žolíky postupně dosazujeme čísla 1,…,a (za všechny žolíky stejné číslo).
Příklad Máme-li klasické 3×3 piškvorky, tedy s a=3 a d=2, potom 1∗ je první sloupec, ∗2 je druhý řádek a ∗∗ je hlavní diagonála. Všimněme si, že antidiagonála se nedá vyjádřit jako kombinatorická přímka.
Definice Obarvení krychle pomocí r barev je zobrazení χ:Ad→[r]. Přímka L je monochromatická, pokud pro všechny x,y∈L je χ(x)=χ(y).
Věta Hales-Jewett Pro všechna r,a∈ℕ existuje D=HJ(r,a)∈ℕ takové, že pro všechna obarvení χ:[a]D→[r] existuje monochromatická přímka.
Důsledek Při hraní piškvorek v dostatečném počtu dimenzí existuje výherní strategie pro prvního hráče.
Důkaz Shelah, 1988 Indukcí podle a při pevném r. Pro a=1 triviální (stačí D=1). Pro indukční krok použijeme následující pomocné tvrzení.
Definice Body x,y∈Ad jsou S-sousední, pokud se liší v jen jedné složce, přičemž jeden z nich tam má a−1 a druhý a.
Lemma Nechť r∈ℕ,a≥2 a d≔HJ(r,a−1). Potom existuje D∈ℕ takové, že pro každé obarvení AD→[r] existují vzory ν1,…,νd s ∑i=1d|νi| takové, že pro libovolné S-sousední body x,y∈Ad platí
χ(ν1(x1),…,νd(xd))=χ(ν1(y1),…,νd(yd)).
Poznámka Vzory ν1,…,νd určují nějakou d-rozměrnou podkrychli/podrovnoběžnostěn.
Důkaz Budeme iterativně konstruovat νd,…,ν1. νi bude mít délku Ni≔rad+Mi, kde Mi≔∑k=1i−1Nk. Pro dané c=0,…,d−1 uvažme funkce f0,…,fNd−c:AMd−c+c−1→[r] definované jako
ft(x)≔χ(x1,…,xMd−c,a−1,…,a−1⏟t×,a,…,a⏟(Nd−c−t)×,νd−c+1(x−c),…,νd(x−1))
(kde používáme „pythonovské značení“ pro indexování odzadu). Podle 🐦holubníkového principu🐦 musí nějaké dvě z těchto funkcí být identické. Označme je fα,fβ,α<β. Potom definujme
νd−c≔a−1,…,a−1⏟α×,∗,…,∗⏟(β−α)×,a,…,a⏟(Nd−c−β)×.
Nyní vezměme D, ν1,…,νd z lemmatu. Definujme obarvení χ¯:Ad→[r],
χ¯(x1,…,xd)≔χ(ν1(x1),…,νd(xd)).
Snadno si rozmyslíme, že monochromatická přímka pro χ¯ je monochromatická i pro χ. Teď na podkrychli [a−1]d použijeme indukční předpoklad. Existuje tedy χ¯-monochromatická přímka Lτ={τ(1),…,τ(a−1)}. Zároveň z S-sousednosti plyne χ¯(τ(a−1))=χ¯(τ(a)). (Pokud τ obsahuje více žolíků, nahrazujeme je postupně). Z toho již plyne tvrzení věty.

Herní čísla

Hra koláč Máme koláč s m řádky a n sloupci. Líza v každém tahu rozřízne koláč svisle, Richard vodorovně. Je-li již víc kusů koláče, rozříznou jen jeden z nich. Prohraje ten, kdo nemůže táhnout.
Věta Každá pozice v normální hře je jednoho z následujících typů:
ℒ
vyhrává Líza, ať začne kdokoliv;
ℛ
vyhrává Richard, ať začne kdokoliv;
𝒩
vyhrává ten, kdo začne (následující hráč);
𝒫
vyhrává ten, kdo nezačne (přechozí hráč).
Důkaz Přímý důsledek Zermelovy věty.
Definice Nechť γ je pozice ve hře, α1,…,αn jsou pozice, kam ji může přesunout Líza, a β1,…,βm jsou pozice, kam ji může přesunout Richard. Potom značíme
γ={α1,…,αn|β1,…,βm}.
Věta Pozice γ={α1,…,αn|β1,…,βm} je
Důkaz Triviální.
Definice Nechť γ1,γ2 jsou pozice v nějakých hrách. Potom jejich součet je pozice γ1+γ2 odpovídající hře, kde si hráč na tahu vybere jednu z původních her a provede v ní tah.
Příklad Označíme-li γm,n pozici ve hře řezání koláče obsahující jeden koláč s m řádky a n sloupci, potom
γm,n={γ1,n+γm−1,n,…,γm−1,n+γ1,n|γm,1+γm,n−1,…,γm,n−1+γm,1}.
Hra Domineering Máme mřížku, do které Líza pokládá svislé dílky domina a Richard vodorovné dílky domina . Prohraje ten, kdo nemůže táhnout.
Věta Typ součtu dvou pozic jde určit z jejich typů podle následující tabulky:
+𝓛𝓡𝓝𝓟
𝓛ℒ?ℒ|𝒩ℒ
𝓡?ℛℛ|𝒩ℛ
𝓝ℒ|𝒩ℛ|𝒩?𝒩
𝓟ℒℛ𝒩𝒫
Přitom varianty označené otazníkem mohou dopadnout jakkoli.
Důkaz otazníků To, že u pozic označených otazníkem je možné všechno, demonstrujeme na hře Domineering.
𝓝+𝓝𝓛+𝓡
𝓛 + +
𝓡 + +
𝓝 + +
𝓟 + +
Definice Pozice α,β jsou ekvivalentní, pokud pro všechny pozice γ jsou α+γ,β+γ stejného typu.
Věta Pokud β je typu 𝒫, potom pro všechny α je α+β≡α.
Důkaz Pro všechny γ je α+γ stejného typu jako (α+γ)+β=(α+β)+γ.
Věta Pokud α,β jsou typu 𝒫, potom α≡β.
Důkaz Plyne přímo z definice a tabulky.
Věta Pokud α+β a α′+β jsou typu 𝒫, potom α≡α′.
Důkaz
α≡α+(α′+β)=(α+β)+α′≡α′.
Definice Hra je nestranná, pokud pro všechny pozice γ={α1,…,αn|β1,…,βm} platí {α1,…,αn}={β1,…,βm}.
Věta Každá pozice v nestranné hře je typu 𝒩 nebo 𝒫.
Důkaz Kradení strategie.

Nim

Hra Nim Na stole leží k hromádek s lentilkami, kde i-tá hromádka obsahuje ni lentilek. Hráč ve svém tahu může sníst libovolný počet lentilek z jedné hromádky. Vyhraje ten, kdo sní poslední lentilku.
Věta Pozice (n1,…,nk) v Nimu je typu 𝒫, právě když ⨁i=1kni=0, kde ⊕︎ značí binární XOR.
Důkaz Pozici splňující rovnost nazveme vyvážená. Je zřejmé, že jakýkoli tah z vyvážené pozice vede do nevyvážené pozice. Naopak je-li pozice nevyvážená, můžeme vzít jakoukoli pozici obsahující jedničku na stejné pozici, kde má ⨁i=1kni nejvýznamnější jedničku, a sežráním z této hromádky dosáhnout vyvážené pozice.
Definice Pro n∈ℕ označíme ∗n jednohromádkový Nim s n kameny.
Poznámka Pro m,n∈ℕ platí ∗m+∗n=∗(m⊕︎n).
Věta Pro každou pozici α v Nimu existuje n∈ℕ takové, že α≡∗n.
Důkaz Nechť velikosti hromádek v α jsou n1,…,nk. Označme n≔⨁i=1kni. Jelikož α+∗n je typu 𝒫 a ∗n+∗n je typu 𝒫, musí být α≡∗n.
Lemma MEX princip Nechť β={α1,…,αn|α1,…,αn} je pozice v nestranné hře a pro všechna i∈[n] existuje takové ai∈ℕ, že αi≡∗αi. Potom existuje b∈ℕ takové, že β≡∗b.
Důkaz Vezměme
b≔min(ℕ∖{a1,…,an}).
Dokážeme, že β+∗b je typu 𝒫, z čehož už plyne tvrzení. A to tak, že najdeme výherní strategii pro druhého hráče.
  • Zahraje-li první hráč do pozice β+∗c, kde c<b, potom z konstrukce je ∗c≡αi pro nějaké i. Stačí tedy zahrát do pozice αi+∗c.
  • Zahraje-li první hráč do pozice αj+∗b, potom
    αj+∗b≡(∗a)j+∗b≡∗(aj⊕︎b).
    Jelikož aj≠b, tato hra je typu 𝒩.
Poznámka Název MEX plyne z toho, že b je minimální vyloučené (minimal excluded) číslo z a1,…,an.
Věta Každá pozice α v nestranné normální hře je ekvivalentní ∗k pro nějaké k∈ℕ.
Důkaz Indukcí přes hloubku hry, kde jako indukční krok použijeme MEX princip.
Cvičení Nechť γn je hra s n sirkami. Pro jaké ☼ je γn≡∗☼?
ŘešeníZjevně pro n≤3 je γn≡∗n, protože jde o identickou hru. Podle MEX principu dostáváme
γ4={γ1,γ2,γ3}≡{∗1,∗2,∗3}=∗0,
γ5={γ2,γ3,γ4}≡{∗2,∗3,∗0}=∗1,
γ6={γ3,γ4,γ5}≡{∗3,∗0,∗1}=∗2
a tak dále. Obecně
γn≡∗(nmod4).
Cvičení Nechť γm,n je hra Chop velikosti m×n. Pro jaké ⚘ je γn≡∗⚘?
ŘešeníV podstatě jde o Nim s hromádkami velikosti m−1 a n−1, takže γm,n≡∗(m−1)+∗(n−1)≡∗((m−1)⊕︎(n−1)).