|
|
PNS for the game Arimaa
Majerech, Ondřej ; Hric, Jan (vedoucí práce) ; Valla, Tomáš (oponent)
Arimaa je strategická desková hra, kterou se stále počítačům nepovedlo pokořit. Problematický je zejména velký větvící faktor stromu hry a celková její charakteristika, díky které je obtížné sestrojit vhodnou ohodnocovací heuristiku pro alfa-beta prohledávání. Proof-Number Search je algoritmus nezávislý na dobré ohodnocovací heuristice, který byl již úspěšně použit na řešení koncovek jiných deskových her. V této práci jsme adaptovali a implementovali algoritmus Proof-Number Search pro hru Arimaa.
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Nešetřil, Jaroslav (vedoucí práce) ; Valtr, Pavel (oponent)
Ramseyova teorie studuje vnitřní homogenitu matematických struktur (grafů, číselných oborů), jejichž části (podgrafy, podmnožiny) jsou libovolně obarveny. Často platí, že je-li studovaný objekt dostatečně velký, lze v něm najít určitý jednobarevný podobjekt. Kombinatorické hry jsou hry dvou hráčů s plnou informací, kde záleží pouze na jejich inteligenci. Teorie kombinatorických her studuje především otázky existence vyhrávajících či neprohrávajících strategií. Vezmeme-li ramseyovskou větu a necháme-li objekt, který tato věta studuje, střídavě barvit dvěma hráči, jejichž cílem je vytvořit určitý monochromatický podobjekt, dostaneme kombinatorickou hru. Předmětem našeho zájmu je jednak nejmenší velikost objektu, při které platí ramseyovská věta, tzv. ramseyovské číslo, a jednak nejmeněí velikost téhož objektu, při které má první hráč vyhrávající strategii v příslušné kombinatorické hře, tzv. herní číslo. V této práci popisujeme takové ramseyovské věty, u nichž je ramseyovské číslo podstatně větší než číslo herní. To znamená, že podáváme důkazy existence vyhrávajících strategií prvního hráče spolu s horními odhady na ramseyovská a herní čísla a obě čísla porovnáváme.
|
|
|
Algorithms for solving strong positional games with high symmetry
Novotná, Jitka ; Valla, Tomáš (vedoucí práce) ; Kit, Michal (oponent)
V této práce představujeme několik algoritmů pro počítačové řešení silných pozičních her a to především algoritmů založených na algoritmu PN-search. Zaměřujeme se na hry s vysokou symetrií herního plánu. Spojováním mnoha izomorfních pozic jsme dosáhli velkého zmenšení části herního strumu, kterou je potřeba prohledat. Představujeme již známa vylepšení a také navrhujeme vlastní. Ověřujeme jak tyto heuristiky funguji na příkladu klikové hry. K práci je přiložen software pro řešení silné klikové hry pro K=4 a N=5...8. Software zvládl vyřešit (6,4) a (7,4)-klikovou hru a dokázal, že druhý hráč má neprohrávající strategii, což se očekávalo, ale dosud nebylo potvrzeno.
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Nešetřil, Jaroslav (vedoucí práce)
Ramseyova teorie studuje vnitřní homogenitu matematických struktur (grafů, číselných oborů), jejichž části (podgrafy, podmnožiny) jsou libovolně obarveny. Často platí, že je-li studovaný objekt dostatečně velký, lze v něm najít určitý jednobarevný podobjekt. Kombinatorické hry jsou hry dvou hráčů s plnou informací, kde záleží pouze na jejich inteligenci. Teorie kombinatorických her studuje především otázky existence vyhrávajících či neprohrávajících strategií. Vezmeme-li ramseyovskou větu a nechámeli objekt, který tato věta studuje, střídavě barvit dvěma hráči, jejichž cílem je vytvořit určitý monochromatický podobjekt, dostaneme kombinatorickou hru. Předmětem našeho zájmu je jednak nejmenší velikost objektu, při které platí ramseyovská věta, tzv. ramseyovské číslo, a jednak nejmenší velikost téhož objektu, při které má první hráč vyhrávající strategii v příslušné kombinatorické hře, tzv. herní číslo. V této práci popisujeme takové ramseyovské věty, u nichž je ramseyovské číslo podstatně větší než číslo herní. To znamená, že podáváme důkazy existence vyhrávajících strategií prvního hráče spolu s horními odhady na ramseyovská a herní čísla a obě čísla porovnáváme.
|
|
|
Dětské vozítko poháněné akuvrtačkou
Valla, Tomáš ; Böhm, Michael (oponent) ; Štětina, Josef (vedoucí práce)
Tato bakalářská práce se zabývá návrhem dětského vozítka na aku pohon. Aku vrtačka musí zůstat použitelná i pro běžné používání. Teoretická část se zabývá popisem historického vývoje dětských autíček od prvních vyrobených modelů až po moderní šlapací a elektrická vozítka. V další části je popsán vznik aku vrtaček. Následující část zobrazuje dnešní možnosti nakoupení dětských vozítek. Je vidět, že trh se značně obohatil a prakticky není možné si nevybrat. Konstrukční část je zaměřena na návrh jednotlivých komponent a výpis nakoupených dílů. Zahrnuje i základní výpočty pro vybraný řetěz a navrhnutou konstrukci.
|
|
|
Poziční hry s efektivní vítěznou strategií
Svoboda, Jakub ; Šámal, Robert (vedoucí práce) ; Valla, Tomáš (oponent)
V práci zkoumáme hry, ve kterých dva hráči obarvují hrany nekonečného úplného grafu a snaží se vytvořit určitý, cílový, podgraf obarvený svou barvou. Nejprve se budeme uvažovat situaci, kdy cílový podgraf je úplným grafem a uká- žeme, že první hráč má vyhrávající strategii, když je cílový podgraf úplný graf na nejvýše třech vrcholech. Potom lehce změníme podmínky hry a ukážeme, že první hráč má vyhrávající strategii, pokud může omezit graf, na kterém se hraje, nebo zahrát několik tahů navíc. Nakonec budeme uvažovat hru, v níž musí být minorem cílového podgrafu úplný graf. Ukážeme vyhrávající strategii pro malou velikost úplného grafu, který musí být minorem cílového podgrafu a zamyslíme se nad důvody, proč by první hráč měl vyhrát jakoukoliv hru tohoto typu. 1
|
|
|
Cooperative interval games
Bok, Jan ; Hladík, Milan (vedoucí práce) ; Valla, Tomáš (oponent)
V této práci studujeme kooperativní intervalové hry, zobecněný model kooperativních her ve kterém hodnota každé koalice koresponduje s uzavřeným intervalem, reprezentujícím všechny možné výsledky jejich kooperace. Nejprve dáváme stručné úvody do klasické kooperativní teorie her a intervalové analýzy a následně uvádíme čtenáře do kooperativních intervalových her, a to se speciálním důrazem na selekce, což jsou všechny možné výsledky hry ve kterých už není žádná další neurčitost. Představujeme nové třídy her podle vlastností jejich selekcí a dokazujeme jejich charakterizace a vztahy s již existujícími třídami. Ukazujeme nové výsledky týkající se imputací a jader. Zavádíme definici silné imputace a silného jádra a zkoumáme problém rovnosti dvou různých typů jader -- hlavního stabilního řešení kooperativních intervalových her. Nakonec ukazujeme nová pozorování ohledně Shapleyho hodnoty intervalových her.
|
|
|
Online Ramsey Theory
Dvořák, Pavel ; Valla, Tomáš (vedoucí práce) ; Koucký, Michal (oponent)
Online Ramseyho hra je hra dvou hráčů, označovanými jako Builder a Painter. V každém kole Builder postaví hranu grafu a Painter ji nabarví červeně nebo modře. Builder vyhraje, pokud se po nějakém kole objeví v nabarveném grafu jednobarevná kopie daného grafu H, jinak vyhraje Painter. V této práci zkoumáme výpočetní složitost odvozeného rozhodovacího problém a ukážeme, že je PSPACE-úplný. Navíc se zabýváme verzí hry, kdy Builder může stavět jen rovinné grafy, a zobecněním hry pro hypergrafy. Nalezli jsme novou třídu grafů nevyhnutelných na rovinných grafech. Ukázali jsme, že Builder vyhraje online Ramseyho hru na 3-uniformních hyperlesech, pokud je cílový graf H je 1-degenerovaný. 1
|
|
|
Desktop client for open social networks
Kasinec, Maroš ; Valla, Tomáš (vedoucí práce) ; Vaner, Michal (oponent)
Sociálne siete zažívajú v poslednej dekáde obrovský romach a ovplyvnili nielen spôsob on-line komunikácie a sociálnej interakcie ale tiež oblasť obchodu, médií či vládnych inštitúcií. Avšak ich hlavný nedostatok, uzvretý a centralizovaný charakter, ostáva nepovšimnutý medzi širokou verejnosťou. Táto práca pojednáva a hodnotí ich otvorené a decentralizované alternatívy a súčasne sa zameriava na jednu konkrétnu - buddycloud. Vďaka využitiu XMPP protokolu, buddycloud a jeho protokol Channel sa javí ako sľubný prístup pre otvorenie ekosystému sociálnych sietí. Umožňuje im komunikovať federatívnym spôsobom ako funguje dnes e-mailová sieť. Ako príspevok do projektu buddycloud táto práca predstavuje aplikáciu SocialDesktopClient, desktopový klient pre širokú škálu sociálnych sietí. Bližšie sa zaoberá modulárnym návrhom klienta a implementáciou protokolu Channel ako prvej sociálnej sieti.
|
|
|
Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe
Dvořák, Pavel ; Valla, Tomáš (vedoucí práce) ; Šámal, Robert (oponent)
V této práci zkoumáme poziční hry, zejména pak vícerozměrné piškvorky. Porovnáváme existující pokročilé algoritmy (Pn-search, Db-Search, λ-search) pro řešení pozic v pozičních hrách. Algoritmy nasazujeme na domény her 43 a 53 , což jsou první netriviální připady trojrozměrných piškvorek. Paralelizujeme Pn-search pro případ, kdy existuje více počátečních pozic. Pn-search aplikujeme jako jed- novláknovou úlohu a řešíme, jak sdílet transpoziční tabulku s vyřešenými poz- icemi. Hlavním a čistě teoretickým výsledkem je charakterizace grupy auto- morfismů kombinatorické krychle nd se stejnou množinou linií jako vícerozměrné piškvorky. Toto je zobecnění Silvera [The American Mathematical Monthly, Vol. 74, No. 3, 1967], který popsal automorfismy hry 43 . 1
|
host ::
RSS.