Kombinatorická teorie her

Garant předmětu:

Tomáš Valla

Přednášející:

Tomáš Valla

Cvičící:

Jan Matyáš Křišťan

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Klasická teorie her je oblastí matematiky, která má široké aplikace ve společenských vědách, zejména ekonomii, biologii, politice a informatice. Tato teorie se snaží podchytit chování účastníků (hráčů) určité kompetitivní činnosti zavedením matematického modelu a studiem strategií hráčů. Tradiční úkolem klasické teorie her je nalézání rovnovážných bodů, tzv. ekvilibrií. To jsou stavy hry, ve kterých všichni hráči zaujali takovou strategii, kterou se jim již nevyplatí měnit.

Historicky druhým průlomovým krokem ve studiu her, tentokráte již kombinatorických her dvou hráčů s plnou informací, byl přístup J. Conwaye, E. Berlekampa a R. Guye. Ti rozvinuli teorii, původně určenou pro řešení složitých koncovek v Go, na plnohodnotný obor, založený na myšlence ohodnocení her takovým způsobem, aby šly jinak zcela nekompatibilní hry tzv. sčítat, neboli hrát simultánně. Obor brzy vyspěl v kompletní algebraický přístup ke studiu kombinatorických her.

Třetím nejvýznamnějším počinem je přístup J. Becka, který založil a vybudoval teorii pozičních her (ke kterým patří například piškvorky či hex). Když analyzujeme pozici v těchto hrách, neubráníme se v mnoha případech procházení herního stromu hrubou silou, a to ani při použití Conwayovy teorie. Řešení hrubou silou je však nepraktické. J. Beck zavádí tzv. „falešnou pravděpodobnostní metodu“, pomocí níž se lze tomuto problému vyhnout.

V rámci tohoto předmětu vybudujeme základy teorie kombinatorických her a pozičních her.

Předmět je zaměřen na teoretickou analýzu her a budováni jejich teorie, nikoli na praktické programování herních algoritmů, zabývá se tedy čistě matematickým aspektem věci. Předmět vyžaduje samostatnou práci studentů, jejich schopnost matematicky myslet, analyzovat a dokazovat.

Předmět je vhodný i pro bakalářské studenty ve třeťáku, kteří za sebou mají nějaký úvod do teorie grafů, i pro doktorské studenty, kteří z něj mohou čerpat výzkumná témata.

Požadavky:

* nebát se obtížné matematiky

* základy teorie grafů a kombinatoriky a algebry

Osnova přednášek:

1) úvod do teorie her

2) formáľní zavedení kombinatorických her, třídy her, věta o strategiích

3) porovnávání her, budování herní algebry (sčítání, negace, izomorfismus)

4) zavedení neceločíselných her, sčítaní čísel a sčítání her

5) simplicity rule, dominované a reverzibilní tahy

6) infinitezimálně velké hry, teploměry

7) silné a slabé poziční hry, věta o kradení strategií, zobecněné piškvorky

8) Hallova věta a párovací remíza, potenciálová metoda

9) Erdös-Selfridgeova věta, aplikace

10) souvislosti s ramseyovskými větami, hry typu Picker-Chooser, Avoider-Enforcer

Osnova cvičení:

Tématické příklady zaměřené na hlubší pochopení látky probírané na přednáškách a na analýzu jednodušších her.

Cíle studia:

Seznámit se s základy algebraické teorie her podle Conwaye.

* Seznámit se s základy teorie pozičních her (neboli odvozenin piškvorek) podle Becka.

* Naučit se aplikovat Conwayovu a Beckovu teorii pro analýzu jednodušších her.

Studijní materiály:

Berlekamp, Conway, Guy: Winning Ways

J. Beck: Combinatorial Games, Tic-Tac-Toe Theory

Conway: On Numbers and Games

Albert, Nowakowski, Wolfe: Lessons in Play

Nisan, Roughgarden, Tardos, Vazirani: Algorithmic Game Theory

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (volitelný předmět)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (volitelný předmět)