|
|
Artificial intelligence in abstract 2-player games
Veselý, Pavel ; Valla, Tomáš (vedoucí práce) ; Baudiš, Petr (oponent)
V této práci se zaměříme na algoritmy pro hledání nejlepšího tahu v~zadané pozici abstraktní strategické hry dvou hráčů. Popíšeme algoritmy Alfa-beta a Proof-number search včetně jejich vylepšení a přispějeme novými nápady na jejich zrychlení. Rovněž navrhneme postup, jak vybírat náhod\-ně mezi tahy ne o moc horšími než nejlepší nalezený a jak hrát v prohraných pozicích. Algoritmy nasadíme na hru Tzaar, která je zvláštní velkým počtem možných tahů, což ji dělá obtížnou pro počítač. Naším cílem je vytvořit co nejlepšího robota na hraní Tzaaru. Ukážeme, že naše umělá inteligence dokáže hrát na úrovni nejlepších lidských i~počítačových hráčů na internetu. Také na základě experimentů rozebereme, jak jednotlivá vylepšení algoritmů pomáhají v zrychlení výpočtů u~této hry.
|
|
|
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.
|
|
|
Plánovací algoritmy a simulace plánu v logistické doméně
Štefan, Zdeněk ; Toropila, Daniel (vedoucí práce) ; Valla, Tomáš (oponent)
Bakalářská práce se zabývá porovnáním některých technik pro řešení plánování v logistické doméně. Její cílem je porovnání schopností těchto technik z umělé inteligence řešit zadaný problém z hlediska optimality nejen mezi sebou, ale i s plány navrženými lidmi. Protože ne všechny plánovače vrací paralelní plány, je potřeba tyto plány paralelizovat. Práce ukazuje, že některé algoritmy dosahují dobré výsledky ve srovnání s lidskými plány, bohužel však kvůli časové a paměťové náročnosti nemůžou být v dnešní době běžně používány pro řešení náročnějších úkolů.
|
|
|
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.
|
|
|
Visualisation of algorithms
Bašista, Peter ; Valla, Tomáš (oponent) ; Mareš, Martin (vedoucí práce)
Cieľom práce je navrhnúť program pre vizualizáciu činnosti algoritmov pri výuke. Užívateľ vytvorí algoritmus a pripojí k jeho datovým štruktúram pripravené vizualizačné komponenty. Program potom zaznamená priebeh výpočtu algoritmu a zobrazí ho ako interaktívnu animáciu, prípadne vytvorí súbor PDF zachytávajúci kľúčové body výpočtu. V predloženej práci sa zameriavame na predstavenie knižnice Algorithm Animation Library. Táto knižnica bola navrhnutá tak, aby umožnila užívateľovi pokiaľ možno čo najväčšiu flexibilitu pri tvorbe animácií, a zároveň tak, aby jej ovládanie bolo používateľsky čo najprijateľnejšie. V práci vysvetlíme základné princípy jej fungovania a používania, v krátkosti ju porovnáme s alternatívami a vyslovíme závery o tom, kedy je vhodné knižnicu Algorithm Animation Library použiť.
|
|
| |
|
|
Music effects
Marko, Matej ; Valla, Tomáš (oponent) ; Bálek, Martin (vedoucí práce)
Názov práce: Hudobné efekty Autor: Matej Marko Katedra (ústav): Katedra aplikovanej matematiky Vedúci baklárskej práce: Mgr. Martin Bálek e-mail vedúceho: Martin.Balek@mff.cuni.cz Abstrakt: Efekty zohrávajú v procese tvorby hudby významnú úlohu. Pomáhajú doplniť a obohatiť aranžmán skladby. Cieľom práce je vyvinúť aplikáciu, ktorá umožní užívateľovi prehrať zvukový súbor a v reálnom čase na prehrávaný obsah aplikovať zvolené efekty. Každá zmena v nastavení efektov sa tak ihneď prejaví na výslednom zvuku a užívateľ ju môže okamžite posúdiť. Konkrétne nastavenie môže užívateľ aplikovať na celý vstupný súbor a tento výsledok uložiť. Súčasťou aplikácie je tiež implementácia vybraných efektov. V texte práce sa potom zameriavame na postupy, ktoré sú použité pri implementovaní týchto efektov. Kľúčové slová: efekty, hudba, zvuk
|
|
|
Vizualizační algoritmy pro grafy
Kuča, Tomáš ; Mareš, Martin (oponent) ; Valla, Tomáš (vedoucí práce)
Tato práce studuje současné algoritmy pro kreslení grafů. Zaměřuje se především na rovinné grafy, ale rozebírá i několik algoritmů pro nerovinné grafy a metody, které umožňují převádět nerovinné grafy na rovinné. Navrhuje rozšíření algoritmu pro kreslení se stejným obsahem vnitřních stěn, které zohledňuje velikost úhlů. Popisuje, jak lze využít algoritmus pro hledání maximální nezávislé množiny na průsekových grafech při planarizaci. V závěru je představen zásuvný modul pro gra cký editor VRR, který byl vyvinut pro testování algoritmů.
|
|
|
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.
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Valtr, Pavel (oponent) ; 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á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.
|
host ::
RSS.