Kombinatorická teorie her

• Stránka cvičení

Přednáška se koná každé úterý od 14:30 do 17:45 v učebně A1242. Cvičení spolu s přednáškou tvoří jednolitý blok.

Jak se dostat do učebny: adresa je Thákurova 7, nějak se dostat skrz vrátnici, zahnout doprava a po malých schodech dojít k výtahům budovy A. Zde vyjeďte do 12tého patra, místnost 1242.

Cvičení (ve formě vzorového řešení domácích úkolů a diskuzí) se koná v rámci přednášky. Přednáška a cvičení nejsou tedy striktně odděleny.

kontakt: tomas.valla@fit.cvut.cz

Cíle přednášky

• Seznámit se s základy algebraické teorie her podle Conwaye.
• Naučit se aplikovat Conwayovu teorii pro analýzu jednodušších her.
• Seznámit se s základy teorie pozičních her (neboli odvozenin piškvorek).

Podmínky získání zápočtu

• Na každé přednášce budeme zadávat domácí úkoly zábavu.
• Na vyřešení úkolu zábavy je týden (tedy je třeba vypracovat ho do příště).
• Úkoly Zábavu odevzdávejte nejlépe na papíře na začátku přednášky/cvičení.
• Zápočet dostane ten, kdo získá alespoň 30 bodů za vyřešené domácí úkoly zábavy.
• Maximální získatelný počet bodů za celý semestr bude okolo 130 (tj. okolo 10 bodů na každou sérii).
• Zkušený TeXař může získat zápočet za průběžné TeXování poznámek.

Požadavky ke zkoušce

• Zkouška bude ústní, bude se skládat z několika otázek z teorie (typicky formulovat a dokázat nějakou větu) a z analýzy jednodušší hry.
• Za 60 bodů za vyřešené domácí úkoly zábavy je prominuta u zkoušky analýza hry.
• Za 100 bodů za vyřešené domácí úkoly zábavy je automaticky známka výborně (namísto skládané zkoušky).
• Body z domácích úkolů zábav se však do zkoušky nezapočítávají.

Literatura

• Berlekamp, Conway, Guy: Winning Ways
• J. Beck: Combinatorial Games, Tic-Tac-Toe Theory
• Conway: On Numbers and Games
• Albert, Nowakowski, Wolfe: Lessons in Play

Předběžný obsah

• úvod do teorie her
• formální zavedení kombinatorických her, třídy her, věta o strategiích
• porovnávání her, budování herní algebry (sčítání, negace, izomorfismus)
• zavedení neceločíselných her, sčítaní čísel a sčítání her
• simplicity rule, dominované a reverzibilní tahy
• infinitezimálně velké hry, teploměry
• silné a slabé poziční hry, věta o kradení strategií, zobecněné piškvorky
• Hallova věta a párovací remíza, potenciálová metoda
• Erdös-Selfridgeova věta, aplikace
• souvislosti s ramseyovskými větami, hry typu Picker-Chooser, Avoider-Enforcer
• další témata, např. online ramsey theory

Obsah přednášky

1. díl (20.2.2018)

• organizační: termíny, podmínky zápočtu hrubý obsah celé přednášky
• hra Domineering – Dominování: vzorová sehrávka, analýza hry rozkladem na podhry/podpozice
• jakými hrami se budeme zabývat (a jakými nebudeme): 2 hráči, bez náhody, konečné, normální a misère hry, hráči Levý a pRavý, pozice a podpozice, nestranné a zaujaté hry, hra Cram (Dláždění)
• využití symetrií
  • jak vyhrát alespoň jednu partii šachu nad Kasparovem – simultánní partie a kopírování tahů
  • lámání čokolády 100×50, nesmí se vytvořit čtvereček 1×1 – hraní osově symetricky
  • doutníky – využití středové symetrie
• je to jiná hra!
  • čísla 1,2,...,9, hráči je zabírají, cílem je shromáždit trojici se součtem 15
  • tato hra jsou vlastně piškvorky 3×3 – konstrukcí magického čtverce 3×3 se součtem 15
  • hra piškvorek na něm je tedy ekvivalentní s původní hrou
• je to skrytá parita
  • lámání čokolády č.2: kdo nemá tah, prohrál
• kradení strategií
  • hra Chomp (otrávený koláč)
  • Věta (kradení strategií v Chomp): 1. hráč vždy vyhraje
  • důkaz je nekonstruktivní
• formální definice her, diskuze konečnosti, strom hry, strategie, značení, příklady
• Základní věta o kombinatorických hrách
• Souvislost s algoritmem Minimax.
• Existuje nedeterminovaná hra (bez důkazu).
• rozdělení her do výsledkových tříd ℒ,ℛ,𝒫,𝒩
• Tvrzení o výsledku hry
• hry Maze, Maize, jejich analýza
• hra Odčítání, její analýza
• Domácí zábava

2. díl (27.2.2018)

• nestranné hry, Věta o třídách nestranných her
• Tvrzení o rozdělení pozic nestranné hry
• analýza lehké verze nestranného Odčítání, analýza hry Star Wars
• motivace zavedení operací sčítání, negace a porovnávání
• Věta o přidání prohrané hry: G hraná souběžně s prohranou hrou je ve stejné třídě jako G
• přehledová tabulka výsledkové třídy, když hrajeme souběžně hry z různých tříd
• analýza dominování 2×(4k) (patří do ℛ)
• KOMPLETNÍ AXIOMATIKA HER
• definice narozenin, definice her 0,1,−1,∗
• zavedení konečnosti pomocí konečných narozenin
• příklady na sčítání her

3. díl (6.3.2018)

• přednášel Vašek Blažej
• G+0≡G
• Tvrzení: sčítání je komutativní a asociativní (důkaz za DZ)
• definice odčítání her, příklady
• Tvrzení: -(-G) ≡ G
• Tvrzení: odčítání je distributivní (důkaz za DZ)
• co to znamená, že dvě hry "dopadnou stejně"
• Tvrzení: Relace = je ekvivalence na hrách.
• Věta (charakterizace nuly): G = 0 právě když G je 𝒫 pozice.
• Věta (rozdíl stejných her): G - G = 0
• Tvrzení (úprava rovnic): G = H právě tehdy, když G + J = H + J.
• Tvrzení (záměnnost v součtu): Když G = G' a H = H', potom G + H = G' + H'. (důkaz za DZ)
• Zásadní Důsledek: G = H právě tehdy, když G - H = 0.
• Věta: Struktura (hry,+,-,0,=) tvoří Abelovu grupu.
• dopady na algoritmické zacházení s hrami a testování rovnosti
• G ≥ H právě když H ≤ G
• Lemma: NTJE
  • G ≥ 0
  • L vyhraje jako 2. na G
  • Pro každou hru X: L vyhraje jako 2. na X implikuje L vyhraje jako 2. na G+X
  • Pro každou hru X: L vyhraje jako 1. na X implikuje L vyhraje jako 1. na G+X
• G ≥ H právě když L vyhraje jako 2. G−H
• porovnávání her algoritmicky analýzou rozdílu, symbolické značení
• Věta: relace ≤ je částečné uspořádání na hrách.
• pár příkladů, hry Clobber a Hackenbush

4. díl (13.3.2018)

• úprava nerovnic: G ≥ H právě když G+J ≥ H+J
• Věta o dominovaných tazích: má-li hra dominovanou pozici jinou pozicí (dle relace ≤), lze ji vynechat
• Věta o reverzibilních tazích: existuje-li pro pozici P výrazně lepší odpověď X oponenta, pak ji udělá a lze P nahradit příslušnými podpozicemi X
• definice kanonického tvaru hry
• Věta (o kanon.tvaru): Dvě rovné hry v kanonickém tvaru jsou izomorfní.
• zavedení celočíselných her
• celý modrý hackenbush je číselná hra "počet hran v pozici"
• sčítání/porovnávání celočíselných her funguje stejně jako sčítání/porovnávání příslušných integerů
• definice (diadických) číselných her
• sčítání/porovnávání číselných her funguje stejně jako sčítání/porovnávání příslušných diadických racionálních čísel

5. díl (20.3.2018)

• definice zobecněného čísla
• zmínka o zavádění reálných čísel
• definice nejjednoduššího čísla
• Lemma 1: Narozeniny hry n+i/2ʲ jsou n+j+1.
• Lemma 2: Mezi dvěma čísly x₁<x₂ se stejnými narozeninami leží číslo s menšími narozeninami.
• Tvrzení: Nejjednoduššího číslo je unikátní (a definice je tedy korektní).
• Věta (simplicity rule): Každá hra {x₁|x₂}, kde x₁<x₂ jsou čísla, je číslo, konkrétně nejjednodušší číslo mezi x₁ a x₂.
• hra PUSH a pár příkladů
• definice infinitezimálních her
• hra ∗ je infinitezimální
• Tvrzení: ∗ není číslo
• definice hry šipka (↑ a ↓)
• Tvrzení: hry ↑ a ↓ jsou infinitezimální
• Tvrzení: vztahy 0, ∗, ↑ a ↓, ⇓ a ⇑
• definice switche a hry ∓G
• Věta: Kanonický tvar hry n.↑ je {0|(n-1).↑∗} a n.↑∗ = {0|(n-1).↑}. (důkaz za DZ)
• zavedení her ✚_G a ━_G
• Tvrzení: ✚_x pro číslo x>0 je infinitezimál
• zavedení infinitezimality vzhledem k jiné hře
• Věta: ✚_x je infinitezimál vzhledem k ↑ pro každé číslo x>0. (důkaz za DZ)

6. díl (27.3.2018)

• Věta (weak number avoidance): x číslo, G není číslo. Pak L vyhraje jako 1. G+x implikuje L vyhraje tahem do G.
• definice all-small her
• Věta: all-small hra je infinitezimální
• Tvrzení: G nestranná, potom G+G=0
• hra NIM(a₁,…,aₖ)
• definice nimbers ∗n
• Tvrzení: kanonický tvar ∗n = {0,∗,∗2,…,∗(n−1)|0,∗,∗2,…,∗(n−1)}
• operátor MEX(M) .. nejmenší nezáporné celé číslo, které v množiné M chybí
• Věta (mex rule): Pro G={∗l₁,…,∗lₖ|∗r₁,…,∗rⱼ} takovou, že mex(l₁,…,lₖ) = mex(r₁,…,rⱼ) = n, platí G = ∗n.
• Důsledek: pro každou nestrannou G tedy existuje přirozené n že G = ∗n
• zavedení nim-součtu ⊕ (xor)
• Věta (analýza nimu): G = NIM(a₁,…,aₖ), potom G je 𝒫-pozice právě když a₁ ⊕ a₂ ⊕ … ⊕ aₖ = 0.
• Věta: ∗a₁+…+∗aₖ = ∗(a₁⊕…⊕a­k)
• dva příklady loopy games: varianty NIMu s přidáváním
• definice nim-posloupnosti a její periodicity
• Věta: Nim-posloupnost Odčítání(a₁,…,aₖ;n) je periodická.

7. díl (3.4.2018)

• představení nástroje CGSuite
• 𝒢ₙ=hry narozené do n-tého dne
• Věta: Z 𝒢ₙ je největší hra n, nejmenší kladné číslo 1/2^n-1 a nejmenší kladná hra ✚_n-2.
• Věta: 𝒢ₙ tvoří svaz.
• motivace pro porovnávání nečíselných her s čísly
• definice left-stop, right-stop hry
• Lemma 1: LS(G)≥RS(G)
• Lemma 2: charakterizace fuzzy intervalu hry na základě LS a RS (zatím bez důkazu)
• fuzzy interval her

8. díl (10.4.2018)

• důkaz Lemma 2 z minulé přednášky
• chladné, vlažné a horké hry, motivace pro zkoumání "střední hodnoty" horkých her, idea ochlazování her a teploměrů
• Věta (o středu hry): G konečná, pak existuje číslo m(G) a číslo t tak, že pro každé přirozené n platí n.m(G)-t ≤ n.G ≤ n.m(G)+t.
• Důsledek: m(G+H) = m(G)+m(H)
• ochlazování her a teplota hry
• formální definice teploměru
• kuchařka pro konstrukci teploměru
• vlastnosti teploměru, vrchol teploměru, teplota, a souvislost s m(G) (bez dk)
• Věta (Number Avoidance): x číslo, G není číslo, x^L≠∅, potom existuje tah G^L že G^L+x > G+x^L. (a symetricky pro pravého) - bez důkazu
• Věta (Number Translation): x číslo, G není číslo, Pak G+x={𝒢^L+x|𝒢^R+x}. - bez důkazu

9. díl (17.4.2018)

• rozdali jsme seznam otevřených problémů
• zavedení pozičních her a motivace, opakování pojmů jako strategie, apod.
• hypergrafy, k-uniformita
• definice silné a slabé (maker-breaker) poziční hry
• další varianty: inverzní silná hra, breaker-maker, Picker-Chooser, inverzní Picker-Chooser, Avoider-Enforcer, Enforcer-Avoider
• hra n^d, vyhrávající linie
• Tvrzení: n² je remíza
• Tvrzení: hra n^d má ((n+2)^d − n^d) ⁄ 2 vyhrávajících linií
• pár openproblémů
• Věta (Strategy stealing): V silné poziční hře má 1. hráč neprohrávající strategii.
• Důsledek: Když v silné hře neexistuje remíza, 1. vyhraje
• silná hra K₆: 1. vyhraje
• hra Hex: neexistuje remíza

10. díl (27.4.2018)

• hra Connectivity na grafu
• Věta: G multigraf, který ma dvě hranově disjunktní kostry. Potom Connector vyhraje jako 1. i jako 2.
• definice systému různých reprezentantů (SRR)
• Věta (Hall): množinový systém (V,E) má SRR právě když ∀J⊆E je |∪_A∈J A| ≥ |J|. (idea důkazu)
• Tvrzení: množinový systém (V,E) má 2-SRR právě když ∀J⊆E je |∪_A∈J A| ≥ 2|J|.
• pár openproblémů
• Věta (Ramseyova): ∀n∈ℕ ∃N∈ℕ tak, že pro každý K_N s červenými a modrými hranami obsahuje jednobarevný podgraf Kₙ.
• Věta (Ramseyova pro víc barev): ∀n,r∈ℕ ∃N∈ℕ tak, že pro každý K_N s hranami r barev obsahuje jednobarevný podgraf Kₙ.
• Kliková hra
• Věta (Ramseyova pro p-tice): ∀n,r,p∈ℕ ∃N∈ℕ tak, že pro každý p-uniformní hypergraf (X,E), |X|≥N, s hranami r barev existuje Y⊆X, |Y|≥n, jejiž všechny hyperhrany mají stejnou barvu.
• definice kombinatorické úsečky
• Věta (Hales-Jewett): ∀n,r∈ℕ ∃D∈ℕ že v krychli n^D s políčky obarvenými r barvami existuje monochromatická kombinatorická úsečka. (bez důkazu)
• důsledek pro hru n^d
• zmínka o van der Waerdenově věta, Tao-Greenově větě a Fieldsových medailích
• Klasifikace hypergrafů podle pozičních her

11. díl (10.5.2018)

• definice 2-obarvitelnosti hypergrafu
• Věta(Erdős): H=(V,E) k-uniformní hypergraf, |E|< 2^k-1. Potom H je 2-obarvitelný.
• Solitairy army, kolik žetonů je potřeba pro malé n
• Věta(Conway): Neexistuje konečná počáteční konfigurace žetonů v Solitairy army, se kterou lze doskákat do výšky 5 nad bariéru.
• Věta(Erdős,Selfridge): H=(V,E) k-uniformní hypergraf, |E|<2^k-1. Potom 2. hráč má blokovací remízu silné/slabé poziční hře nad H.
• Tvrzení: Nerovnost v E.-S. větě je těsná, tj. kontrukce k-uniformního hypergrafu (V,E) kde platí |E|=2^k-1 a 1. hráč vyhraje.
• konstrukce 2-obarvení v polynomiálním čase aplikací E-S věty
• Věta (Weak Win Criterion): Nechť H=(V,E) je k-uniformní hypergraf a |E|>2^k-3Δ₂|V|. Potom 1. hráč (Maker) vyhraje slabou hru na H (a má explicitně popsanou strategii).
• důsledky WWC pro piškvorky n^d
• par openproblémů týkajících se remízových pozic

12. díl (15.5.2018)

• definice online Ramsey hry, size-Ramsey čísel, zobecněného Ramseyova čísla
• Věta: Builder vyhraje online Ramsey hru pro libovolný strom na třídě lesů
• Důsledek: Builder vyhraje ORH pro libovolnou kružnici na třídě rovinných grafů
• Věta: Painter vyhraje ORH pro trojúhelník na třídě vnějškově rovinných grafů
• různé strategie pro cesty, cykly, pár openproblémů