|
|
Pravděpodobnostní sémantika pro logiky podporující nezávislost
Seidl, Julian ; Majer, Ondrej (vedoucí práce) ; Švarný, Petr (oponent)
(česky) Práce je čistě teoretického charakteru a zabývá se teorií her z pohledu matematické logiky a pravděpodobnosti. Dělí se na dvě části, úvodní, která shrnuje základní definice, uvádí do tématu teorie her a základů syntaxe a sémantiky matematické logiky a jejích rozšíření vhodných k práci v teorii her. V úvodní části se vysvětlují pojmy extenzivních a strategických her, Nashova equilibria, čistá a smíšená strategie, vítězná strategie či logika podporující nezávislost. Dále se představují netriviální problémy řešené v druhé části práce, kterými jsou například otázka existence Nashových equilibrií u nekonečných her, nebo problematika uniformní pravděpodobnostní distribuce u stejné třídy her. Druhá část práce pokračuje rozborem strategických her s neúplnou informací, směřujíc tak k řešení již zmíněných netriviálních problémů. V druhé části se také zavádí základní pojmy a definice z oblasti teorie pravděpodobnosti, napomáhající v orientaci a uchopení výše nastíněných problémů. Poslední částí práce před samotným pokusem o řešení vyvstávajících problémů u nekonečných her, je zkoumání možnosti převodů mezi jednotlivými typy her. Závěrem druhé části je návrh řešení problémů způsobených rozšířením třídy zkoumaných her z konečných na nekonečné. První z problémů, existence Nashových equilibrií pro...
|
|
|
Multiplatformní karetní hra s umělou inteligencí
Trejtnar, Martin ; Chlubna, Tomáš (oponent) ; Matýšek, Michal (vedoucí práce)
Tato práce se zabývá umělou inteligencí v karetních hrách. Cílem je implementovat multiplatformní hru tohoto žánru v herním enginu Unity, shrnout možné přístupy vytváření inteligentních protihráčů a pro zvolenou hru navrhnout a popsat metodu nejvhodnější, případně kombinaci několika. Provedený výzkum ukázal, že problémová doména je u karetních her většinou dosti specifická a to znesnadňuje užití univerzálních algoritmů. Zvolený problém je vyřešen formou rule-based umělé inteligence. Podařilo se vytvořit inteligentního hráče pro zástupce z kategorie imperfect information games, což je jeden z hlavních přínosů této práce. Ačkoli se dopouští drobných taktických prohřešků, jeho chování většinou blízce připomíná smýšlení středně zkušených hráčů.
|
|
|
Model Trhu s náhodnými vstupy
Krch, Ivan ; Lachout, Petr (vedoucí práce) ; Branda, Martin (oponent)
V této práci se věnujeme modelu trhu s náhodnými vstupy reprezentovaného úlohou prodavače novin, kde je náhodná složka promítnuta skrze náhodný počet zákazníků. Práce je členěna do tří kapitol. V první kapitole uvádíme základní problém prodavače novin jako úlohu stochastického programování s kompenzací. V druhé kapitole vyložíme teorii her pro více hráčů uzpůsobenou pro problém prodavačů novin. Dále ve druhé kapitole úlohu rozšiřujeme o druhého prodavače na trhu a ve třetí kapitole úlohu ještě více zobecníme na n prodavačů novin na trhu. Situace vzniklé v kapitole dva a tři řešíme z pohledu teorie her a zkou- máme zde vlastnosti Nashových ekvilibrií. Vyložená teorie je demonstrována na ilustrativních příkladech v závěru dvou posledních kapitol. 1
|
|
|
Model trhu s náhodnými vstupy
Krch, Ivan ; Lachout, Petr (vedoucí práce) ; Večeř, Jan (oponent)
V této práci se věnujeme modelu trhu s náhodnými vstupy reprezentovaného úlohou prodavače novin, kde je náhodná složka promítnuta skrze náhodný počet zákazníků. Práce je členěna do tří kapitol. V první kapitole uvádíme základní problém prodavače novin jako úlohu stochastického programování s kompenzací. V druhé kapitole vyložíme teorii her pro více hráčů uzpůsobenou pro problém prodavačů novin. Dále ve druhé kapitole úlohu rozšiřujeme o druhého prodavače na trhu a ve třetí kapitole úlohu ještě více zobecníme na n prodavačů novin na trhu. Situace vzniklé v kapitole dva a tři řešíme z pohledu teorie her a zkou- máme zde vlastnosti Nashových ekvilibrií. Vyložená teorie je demonstrována na ilustrativních příkladech v závěru dvou posledních kapitol. 1
|
|
|
Trh prodavačů novin
Bureček, Tomáš ; Lachout, Petr (vedoucí práce) ; Kopa, Miloš (oponent)
Tato práce řeší úlohu prodavače novin, která zapadá do klasických úloh sto- chastického programování. Práce obsahuje rozšíření na trh prodejců novin a uva- žuje také různé vlivy, které prodavače můžou postihnout. Je uvažována spojitá verze úlohy. Úkolem je najít optimální množství produktu, které má prodejce nakoupit, aby maximalizoval svůj výdělek. V práci je diskutována problematika řešení tohoto problému. Nejprve je problém demonstrován na jednodušší verzi a později je tento problém rozvinut. Nakonec je nalezen iterační algoritmus, který spočte aproximované řešení a jeho funkčnost je demonstrována na příkladu. 1
|
|
|
Algoritmická složitost řešení ve vybraných třídách nekooperativních her
Wichera, Adam ; Majer, Ondřej (vedoucí práce) ; Kroupa, Tomáš (oponent)
Název práce: Algoritmická složitost řešení ve vybraných třídách nekooperativních her Autor: Adam Wichera Katedra (ústav): Katedra logiky Vedoucí bakalářské práce: RNDr. Ondřej Majer, CSc. e-mail vedoucího: majer@ u.cas.cz Abstrakt V předložené práci studujeme přirozené algoritmické problémy vyvstávající z pojmu Nashova equilibria. Problém jeho existence je triviální, protože plyne z Nashova důkazu úplnosti. Ani příslušný vyhledávací problém se tedy nezdá být NP-úplný a to právě proto, že existence ře- šení je zaručena. Zajímavé ale je, že jakékoli přirozené rozšíření tohoto problému už se zdá být NP-úplné. U mnohých už byla NP-úplnost pro konečné nekooperativní hry s obecným součtem dávno dokázána, většinou redukcí problému SAT, Klikového problému, nebo množinového pro- blému hledajícího podpokrytí. Ovšem zda se k ostatním řadí i problém existence asymetrického equilibria pro symetrické hry, byl otevřený problém. Zde ukážeme, jak zobecnit důkaz z [? ] tak, aby dokázal postihnout i problém asymetrických Equilibrií a dokážeme tak jeho NP-kompletnost. Klíčová slova: Nashovo equilibrium, Algoritmická složitost, Nekooperativní hry, Teorie her, Asymetrické equilibrium, 1
|
|
|
Solving Endgames in Large Imperfect-Information Games such as Poker
Ha, Karel ; Hladík, Milan (vedoucí práce) ; Bošanský, Branislav (oponent)
Název práce: Řešení koncovek ve velkých hrách s neúplnou informací jako je např. Poker Autor: Bc. Karel Ha Katedra: Katedra aplikované matematiky Vedoucí diplomové práce: doc. Mgr. Milan Hladík, Ph.D., Katedra aplikované matematiky Abstrakt: Koncovky mají významnou roli pro hráče. V pozdních fázích hry je mnoho aspektů již jasně definováno, což mnohdy umožňuje rozebrat všechny možnosti. Speciální zacházení s koncovkami je obzvláště účinné pro hry s úplnou informací, např. databáze šachových koncovek předvyřešené pro celé třídy typů zakončení, anebo v Go rozdělení desky do samostatných nezávislých podher. Je lákavé rozšířit tento přístup i na hry s neúplnou informací, jakým je např. známý Poker. Zahrát počáteční fáze hry, a jakmile podhry začnou být zvládnu- telné, vypočítat pro ně koncové řešení zvlášť. Ovšem situace je mnohem komp- likovanější pro hry s neúplnou informací. Podhry je potřeba zobecnit pro neúplnou informaci kvůli informačním množinám. Bohužel takové zobecnění nelze hned řešit přímo, neboť by nebyla zachována optimalita. V důsledku toho můžeme skončit s mnohem ovlivnitelnější strategií (co se týče zneužitelnosti). V současnosti jsou tři přístupy, jak se s touto...
|
|
|
Spatial agent-based models of common pool resources
Vach, Dominik ; Gregor, Martin (vedoucí práce) ; Červinka, Michal (oponent)
Tato práce pojednává převážně o aplikování prostorového aspektu v kom- petitivních modelech v kontextu ekonomie přírodních zdrojů. Tyto modely jsou nejprve detailně odvozeny a jsou hledány jejich obecné vlastnosti pro různé distribuce jako je volba strategie jednotlivých hráčů, případně jejich výplatní funkce v závislosti na parametrech použitých distribucí. V druhé části práce jsou tyto kompetitivní modely testovány numerickými simulacemi v jednodimenzionálním prostoru, ale také v dvojdimenzionálním prostoru. V těchto simulacích je kromě hledání Nashovy rovnováhy zkoumán také kon- cept podmínek lokální stability. Jako jeden z výsledků simulací bylo mimo jiné také zjištěno, že ve hře, kde hráči disponují kompletní informací i zdroji, může být za určitých podmínek nevýhodné pro hráče táhnout jako první. V průběhu celé práce je také rozsáhle zkoumán vliv existence okrajů prostoru na rozhodování jednotlivých hráčů, kdy v některých případech tento efekt podnítil vznik soutěže, která by na otevřeném prostoru bez okrajů nevznikla. Klasifikace JEL Q20, Q22, C62, C68, C72 Klíčová slova prostorové modely, využití přírodních zdrojů, Nashova rovnováha, rybolov, počítačové simulace E-mail...
|
|
|
(Ne)racionalita při sázení
Hamáček, Filip ; Hlaváček, Jiří (vedoucí práce) ; Cahlík, Tomáš (oponent)
Tato bakalářská práce se zabývá neracionalitou při sázení. V první části práce pojednává o různých instrumentech vyhodnocování rizika. Ve druhé části práci najdeme diskuzi ohledně Petrohradského paradoxu. Práce hledá alternativní řešení Petrohradského paradoxu dvěma metodami, první metoda je založena na odehrávání velkého množství her Petrohradského paradoxu. Druhou metodou je metoda maximalizace pravděpodobnosti ekonomického přežití, jež pojednává o rozhodování hráče petrohradské hry na základě aktuálního stavu bohatství a minimální hranici ekonomického přežití. Ve třetí části práce je srovnáváno hraní Sportky s hraním specálního turnaje pokeru, cílem této části práce je porovnat očekávanou návratnost finančních prostředků při hraní Sporky a při hraní pokeru bez jakékoliv znalosti pravidel této hry. Pro odhad očekávané hodnoty hry pokeru je využíváno zkoumání různých scénářů hry, kdy pravděpodobnost těchto scénářů je založena na chování hráčů dle Nashovy rovnováhy. Klíčová slova: Sázení, očekávaná hodnota, Petrohradský paradox, loterie, poker, Nashova rovnováha
|
|
|
Evaluating public state space abstractions in extensive form games with an application in poker
Moravčík, Matej ; Hladík, Milan (vedoucí práce) ; Zimmermann, Karel (oponent)
Poznáme efektívne techniky na výpočet optimálnej stratégie pre hry v rozšírenej forme. Niektoré problémy, napríklad poker, sú stále omnoho väčšie, ako sú tieto techniky schopné zvládnuť. Riešením je vytvoriť abstrakciu hry, ktorá je menšia ako pôvodná hra. V tejto abstrakcii už dokážeme nájsť optimálnu stratégiu. Túto stratégiu môžeme potom využiť v originálnej hre. V tejto práci opisujeme techniky, ktoré sa na tvorbu abstrakcií aktuálne používajú. Väčšina z nich neberie osobite v úvahu informácie, ktoré sú viditeľné pre všetkých hráčov v hre. My sme na tento účel vyvinuli vlastnú techniku a otestovali sme ju v pokeri. Naše experimentálne výsledky ukázali, že nová technika priniesla značné zlepšenie oproti doteraz používaným technikám. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.