|
|
Implementace top-trees
Šofka, Jiří ; Majerech, Vladan (vedoucí práce) ; Mareš, Martin (oponent)
Nazev prace: Implerneiitace top-trees Autor: Jifi Sofka Katedra (ustav): Katedra teoreticke informatiky a matematicke logiky Vedouci diplornove prace: Mgr. Vladan Majerech, Dr. e-mail vedouciho: Vladan.Majerech@mff.cuni.cz Abstrakt: Top Trees reprezentuji puvodni strom pomoci jeho dekompozice do binarni hierarchie kontrakcnich clusteru. Kazdy z techto clusteru obsahuje agregovana data o celem podstromu, jehoz je kofenem. Mezi pfednosti Top Trees patfi oddeleni spravy dat clusteru do funkci Create, Destroy, Join, Split a Select, ktere jsou automaticky volany pfi kazde zmene hierarchie clusteru. Diky tomu je irnplementace Top Trees zcela nezavisla na datech, ktera uchovava. Velikost dat agregovanych v clusteru, ktere pfislusi k jedne udrzovane vlastnosti o podstromu, muze byt zavisla na velikosti celeho reprezento- vaneho stromu. Stejne tak jejich vypocet muze byt casove narocny. Pfi dota- zovani Top Trees se casto pouzivaji operace, ktere zpusobi zmenu struktury clusteru. V puvodnim navrhu Top Trees je pfi kazde takove zmene nutna ak- tualizace dat vsech sledovanych vlastnosti ve zmenenych clusterech, nehlede na to, zda jsou vsechny tyto vlastnosti relevantni k polozenemu dotazu. Ak- tualizace dat nerelevantnich vlastnosti je zpravidla zbytecna. Tato prace detailne popisuje implementaci Self-Adjusting Top...
|
|
|
Řešení problémů pomocí MCTS
Malý, Dominik ; Hric, Jan (vedoucí práce) ; Majerech, Vladan (oponent)
Název práce: Řešení problémů pomocí MCTS Autor: Dominik Malý Katedra (ústav): Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: RNDr. Jan Hric E-mail vedoucího: Jan.Hric@mff.cuni.cz Abstrakt: MCTS (Monte Carlo Tree Search) techniky jsou v současné době nejlepšími známými algoritmy pro počítačové řešení strategické deskové hry Go. Vzhledem k univerzálnosti a úspěšnosti těchto technik se však nabízí možnost užití i v jiných úlohách. Úkolem této práce je prozkoumat vhodnost MCTS pro řešení jiných problémů, konkrétně her jednoho hráče, jakými jsou například Sudoku nebo SameGame. Naprogramoval jsem počítačového hráče založeného na MCTS, který dokáže řešit úlohy tohoto typu a aplikoval ho na Sudoku a SameGame. Experimentálně jsem ověřil vhodnost různých rozšíření MCTS algoritmu na řešení těchto her a pomocí rozsáhlého testování porovnal také úspěšnost konkrétních nastavení výběrových UCT funkcí a užitých heuristik. V případě hry SameGame jsem navíc svůj algoritmus porovnal s jinými publikovanými výsledky zabývajícími se stejnou problematikou. Popsal jsem, jaké problémy musí programy řešící hry jednoho hráče pomocí MCTS překonávat, a jakými vlastnostmi by takovéto problémy obecně měly disponovat, aby na ně byly Monte Carlo techniky s úspěchem použitelné. Klíčová slova: MCTS, Go, Sudoku,...
|
|
|
Methods of MCTS and the game Arimaa
Kozelek, Tomáš ; Hric, Jan (vedoucí práce) ; Majerech, Vladan (oponent)
Arimaa je strategická hra vytvořená za účelem být obzvláště těžká pro počítače. Většina existujících programů hrajících hru Arimaa je založena na ověřených postupech z problematiky počítačových šachů obzvláště pak na prořezávání s rozšířeními. V této práci jsme se zaměřili na prostudovímé použitelnosti MCTS technik ve hře Arimaa. MCTS techniky jsou momentálně nejlepší známé algoritmy pro počítačové Go s dobrými vyhlídkami i v dalších strategických hrách. Naprogramovali jsme počítačového hráče založeného na MCTS, kterého jsme pojmenovali Akimot. V naší implementaci jsme přizpůsobili známé MCTS postupy pro prostředí hry Arimaa. Provedli jsme experimenty s různými vylepšeními známými z počítačového Go a určili jsme, které z nich jsou použitelné v naší implementaci. Navíc jsme navrhli a otestovali několik vlastních rozšíření. Experimenty ukázali, že náš MCTS program je srovnatelný s průměrným programem.
|
|
|
Malé hry - gobblet - remizová strategie
Bureš, Filip ; Majerech, Vladan (vedoucí práce) ; Hric, Jan (oponent)
Název práce: Malé hry - gobblet - remizová strategie Autor: Bc. Filip Bureš Katedra / Ústav: Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: Mgr. Vladan Majerech, Dr., KTIML Abstrakt: Diplomová práce se zabývá nalezením remizové strategie pro hru gobblet a provedením důkazu, že hra gobblet je remizová. Gobblet je nekooperativní desková hra pro dva hráče s plnou informací a nulovým součtem. V práci jsou popsány algoritmy, které byly pro důkaz remizovosti použity. Důkaz byl prováděn na zjednodušené variantě hry (omezené pouze na dva typy hracích kamenů). Pro tuto variantu hry byla nalezena remizová strategie; tato strategie byla ověřena pomocí uvedených algoritmů. Po provedení důkazu bylo přistoupeno ke složitější variantě (omezení na tři druhy hracích kamenů). Pro tuto variantu se nepodařilo remizovost dokázat. Důvodem neúspěchu byl počet pozic, které hra obsahuje. Důkaz by se nedal v rozumném čase provést. Pro variantu hry se všemi typy hracích kamenů (4) důkaz prováděn nebyl. Práce pouze nastiňuje metodu, která měla být použita pro nalezení remizové strategie. Klíčová slova: gobblet, remizová, strategie
|
|
|
Go na malých deskách
Čížek, Pavel ; Hric, Jan (vedoucí práce) ; Majerech, Vladan (oponent)
V předložené práci studujeme vhodnost použití heuristik užívaných při počítačové analýze šachu (konkrétně se bude jednat o transpoziční tabulky, killery, historii a protitahy) pro výpočty hodnoty pozice v go. V první části se budeme věnovat jejich úpravě, jelikož go se od šachu v některých ohledech poměrně dost liší. Takto vzniké heuristiky jsme pak implementovali a experimentálně na několika zadáních se pokusíme změřit a popsat jejich efektivitu a vzájemnou (ne)závislost.
|
|
|
Ohodnocovaci funkce v Atari Go
Kudělka, Miloš ; Hric, Jan (vedoucí práce) ; Majerech, Vladan (oponent)
V předložené práci je popsán návrh a implementace prostředí pro hraní Atari Go včetně implementace algoritmů pro hledání nejlepších tahů mini-maxu a minimaxu s alfa-beta prořezáváním. Následně je popsán návrh a implementace parametrizovatelné ohodnocovací funkce a výběr vhodných rysů pozice. Tato funkce pak hodnocením těchto rysů umožňuje hodnocení pozice v Atari Go. Dále je předveden způsob vylepšování parametrů ohodnocovací funkce - je navržen a na tento problém aplikován a implementován jednoduchý učící algoritmus, který parametry funkce pomocí hraní partií zlepšuje. V práci jsou také předvedeny výsledky provedených vylepšování.
|
|
|
Použití vzorů při hře Go
Hamplová, Romana ; Hric, Jan (vedoucí práce) ; Majerech, Vladan (oponent)
V této práci implementujeme řešič taktických cílů pro hru Go (např. zajmutí kamenů, spojení skupin). Tento řešiš je založen na rozpoznávání tvarů kamenů na desce a výběrů tahů podle předdefi novaných vzorů. Hlavní částí práce je analýza a návrh vhodné reprezentace vzorů pro zachycení typických situací a jejich řešení za útočníka i obránce. Uživatelské rozhraní programu umožňuje spouštění řešiče včetně možnosti zadávání druhu taktického cíle, vytváření nových vzorů a editaci celé databáze uložených vzorů. Součástí je i připravená databáze vzorů.
|
|
|
Testování webových aplikací
Borovcová, Anna ; Majerech, Vladan (vedoucí práce) ; Parízek, Pavel (oponent)
Předmětem diplomové práce je vysvětlení problematiky testování webových aplikací zejména potenciálním testerům. Práce proto srozumitelnou formou sděluje zkušenosti nasbírané z různých zdrojů a vychází z mojí tříleté praxe testování a roční praxe ve školení nových testerů převážně ve firmě Unicorn. První část práce je věnována úvodu do webových aplikací, jsou zde zmíněny základní principy a historie internetu i proces vývoje a jeho metodiky. Druhá část se zabývá základními aspekty testování a jak je vidí různí zkušení testeři z České republiky i ze zahraničí. Třetí část vybírá a představuje některé techniky a nástroje vhodné pro testování webových aplikací. Čtvrtá část obsahuje praktickou ukázku některých testovacích dokumentů.
|
|
|
Persistent weak-AVL trees
Škrobánek, Jiří ; Mareš, Martin (vedoucí práce) ; Majerech, Vladan (oponent)
This thesis investigates persistence (i.e., preservation of data by updates) of binary search trees. In particular, we explore how weak-AVL trees may be converted into efficient fully-persistent data structures. After mentioning all important properties of weak-AVL trees, we present a new method to store them with worst-case constant number of changes per update. Then we show some general schemes for conversion of binary search trees (and possibly other pointer-based data structures) into their persistent variants. Finally the established theory is used to obtain fully-persistent weak-AVL trees.
|
|
|
Minimum 0-Extensions of Graph Metrics
Dvořák, Martin ; Bulín, Jakub (vedoucí práce) ; Majerech, Vladan (oponent)
Uvažujeme Minimum 0-Extension problém pro pevně-daný neori- entovaný graf s kladnými vahami hran. Studujeme výpočetní složitost jeho rozhodovací varianty v závislosti na vlastnostech toho pevně-daného grafu, konkrétně s ohledem na to, zda je tento graf modulární a zda je orientovatelný ve smyslu, jak ho definoval Karzanov [Eur. J. Comb., 19/1 (1998)]. Na tento problém se díváme z pohledu Finite-Valued CSP, což nám umožňuje využít bohatství teorie, která byla vyvinuta pro důkaz jejich dichotomie. V rámci spodního odhadu složitosti, nejprve zkonstruujeme explicitní re- dukci z Max-Cut problému, čímž získáme NP-těžkost pro nemodulární grafy. Pro neorientovatelné grafy vyjádříme funkci, která splní určitou podmínku, jež zaručí existenci implicitní redukce z Max-Cut problému. Co se týče pozi- tivních výsledků, pomocí symetrických zlomkových polymorfismů ukážeme, že některé speciální případy pro vážené modulární orientovatelné grafy lze řešit technikou zvanou Basic LP Relaxation, konkrétně Minimum 0-Extension problém pro grafy typu cesta a pro grafy typu obdélník. 1
|
host ::
RSS.