Kombinatorická teorie her, ZS 10/11

Přednáška se koná každou středu od 12:20 v učebně S3. Cvičení (ve formě vzorového řešení domácích úkolů) se koná každou středu od 11:20 do 12:10 na chodbě KAMu ve 3. patře.

Přednášejícími jsou Robert Šámal a Tomáš Valla.

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.
• Na vyřešení úkolu je týden (tedy je třeba vypracovat ho do příště).
• Úkoly 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.
• Maximální získatelný počet bodů za celý semestr bude okolo 140 (tj. okolo 10 bodů na každou sérii úkolů).
• Zkušený TeXař může získat zápočet za průběžné TeXování poznámek/skriptíček.

Požadavky ke zkoušce

• Za 100 bodů za vyřešené domácí úkoly je automaticky známka výborně (namísto skládané zkoušky).
• Přesné požadavky upřesníme koncem semestru, bude to ale velmi pravděpodobně zčásti teoretická otázka a zčásti řešení příkladu (analýza hry aplikací teorie).

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

Seznam studentů

• Výsledky domácích úkolů

Obsah přednášky

Pan Tomáš Masařík sepisuje z přednášek zápisky do TeXu. Z některých přednášek jsou již zápisky vystaveny, jsou však zatím v "alfaverzi" a je v nich dost chyb a nepřesností. Zápisky lze najít také na těchto stránkách. Bugreporty (nejlépe přímo autorovi) jsou vítány.

1. díl (6.10.2010, RŠ+TV)

• 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í)
• hladová strategie a kdy nefunguje
  • hra Dots and Boxes
  • vzorová sehrávka hry
  • použití hladové strategie
  • proč hladová strategie nedává optimální výsledek a hodí se občas něco obětovat
• využití symetrií
  • jak vyhrát alespoň jednu partii šachu nad Karpovem či Kasparovem - simultánní partie a kopírování tahů
  • lámání čokolády 10x20, nesmí se vytvořit čtvereček 1x1 - hraní osově symetricky
  • piškvorky na 5x5 jsou remíza - rafinováné párování ve vyhrávajících liniích
• 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 3x3 - konstrukcí magického čtverce 3x3 se součtem 15
  • hra piškvorek na něm je tedy ekvivalentní s původní hrou
• je to skrytá parita
  • Na začátku hromádka N žetonů. V každém tahu hráč jednu hromádku rozdělí na dvě neprázdné hromádky.
  • Je to ekvivalentní strkání přepážek mezi N předmětů, výsledek tedy závisí jen na paritě.
• kradení strategií
  • nedokončeno
• Domácí úkol
• Zápisky z přednášky

2. díl (13.10.2010, RŠ+TV)

• kradení strategií (znovu a lépe) - demonstrace na hře Chomp
• Věta (hlavní o kombinatorických hrách): Nechť G je kombinatorická hra bez remízy. Potom buďto první, anebo druhý hráč mají vyhrávající strategii.
  • důkaz pomocní zpětného labelování herního stromu
  • algoritmus Minimax
  • existují (nekonečné) hry, kde ani jeden z hráčů nemá vyhrávající strategii -- např. hráči staví postupně binární kód reálného čísla, cílem je vyrobit číslo které patří do zadané podmnožiny A reálných čísel. Pro vhodnou množinu A a při axiomu výběru neexistuje vyhr. strat.
• formální zápis her pomocí notace { G^L | G^R }
• třídy her:
  • psací V (fuzzy): vyhrané pro začínajícího
  • psací L: vyhrané pro levého
  • psací R: vyhrané pro pravého
  • psací P: prohrané pro začínajícího
• zpětné labelování herního stromu pomocí V,L,R,P ve hře Dominování
• analýza hry Maze a Maize
• Domácí úkol
• Zápisky z přednášky

3. díl (27.10.2010, TV)

• Pomocná věta: když lze rozdělit pozice konečné nestranné hry na množiny A,B, kde všechny tahy z A vedou do B, a z každé pozice z B lze táhnout do A, potom A jsou prohrávající pozice a B jsou vyhrávající pozice.
• hra Star Wars a její analýza pomocí přechozí věty
• povídání o historii teorie her
• jaké druhy rovnosti her mohu zavést (identita, stejný výsledek, záměnnost v podpozicích/součtech, izomorfismus herního stromu)
• neformální povídání o tom, co chci po axiomech teorie her
• porovnávání her (neformálně), příklady s Dominováním
• Věta: přičtení hry H ze třídy P ke hře G, tj hra G+H, patří do stejné třídy, jako hra G
• Důsledek: hry ze třídy P jsou právě ty hry (a žádné další), jejichž přičtení nemění hodnotu původní hry
• tabulka, jak dopadne součet her z různých výsledkových tříd - některá políčka jsou nejasná, takové součty chceme obzvlášť studovat
• Konvence/značení: G=0 pro G\in P, G>0 pro G\in L, G<0 pro G\in R, G||0 pro G\in V
• nepřesná definice (zatím) pro hru, sčítání, negaci, rovnost, >=, izomorfismus
• induktivní konstrukce množiny her "po dnech"
• pozorování: her narozených do n-tého dne je konečné mnoho a mají konečné mnoho pozic
• Domácí úkol (a obrázky 1 a 2)
• Zápisky z přednášky

4. díl (3.11.2010, RŠ)

• sčítání her poctivě, přičtení 0, komutativita
• pořádná definice negace hry, příklad negování reálné hry, vlastnosti "mínusu"
• pořádná definice "rovná se", je to ekvivalence, G=0 právě když G\in P, a několik důsledků
• Domácí úkol (a obrázek)
• Zápisky z přednášky

5. díl (17.11.2010, RŠ)

• další vlastnosti +, -, a =. Hry tvoří Abelovu grupu.
• relace <= na hrách a její vlastnosti
• zavedení celočíselných her a obecně her s číslem m/2^k
• Domácí úkol (a obrázky 1 a 2)
• Zápisky z přednášky

6. díl (24.11.2010, RŠ)

• korektnost sčítání čísel a sčítání her
• simplicity rule
• aplikace
• Domácí úkol (a obrázek)
• Zápisky z přednášky

7. díl (8.12.2010, RŠ)

• simplicity rule -- další aplikace a důkaz
• zjednodušování her (dominované a reverzibilní tahy)
• Domácí úkol
• Zápisky z přednášky

8. díl (15.12.2010, RŠ)

• infinitezimalne velke hry
• teplomery

9. díl (22.12.2010, TV)

• teorie her prakticky, aneb vánoční hraní deskových her a pozorování jejich zákonitostí
• software pro operace v herní algebře
• Vánoční nadílka domácích úkolů

10. díl (5.1.2011, TV)

• poziční hra, různé varianty
• analýza hry n^2
• n^d a vyhrávající linie, jejich počet
• Strategy stealing a důsledek pro ramseyovsky velké hypergrafy
• Hales-Jewettova věta, Ramseyova věta
• hra n v řadě
• Domácí úkol

11. díl (12.1.2011, TV)

• klasifikace hypergrafů dle her
• Hallova věta a její důsledek pro existenci párovací remízy
• Solitaire army a Conwayovo řešení
• Erdös-Selfridgeova věta
• Domácí úkol

12. díl (19.1.2011, TV)

• Weak win criterion
• asymptotika hry n^d
• aplikace ES a WWC na n^d a na klikovou hru

---

Poslední změna: 19. 01. 2011