|
|
Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe
Dvořák, Pavel ; Valla, Tomáš (advisor) ; Šámal, Robert (referee)
In this thesis we study positional games, especially multidimensional tic-tac-toe. We compare present advanced algorithms (Pn-search, Db-search and λ-search) for position solving in positional games. We apply the algorithms on the do- main of 43 and 53 games, which are the first nontrivial cases of 3-dimensional tic-tac-toe. We parallelize Pn-search for cases when there are more starting po- sitions. We apply Pn-search as a single-thread task and we solve how to share the transposition table with solved positions. Our main and clearly theoretical result is the characterization of the group of all automorphisms of combinatorial cube nd with the same set of lines as multidimensional tic-tac-toe has. This is a generalization of Silver [The American Mathematical Monthly, Vol. 74, No. 3, 1967], who characterized the automorphisms of the game 43 . 1
|
|
|
Visualization algorithms for graphs
Kuča, Tomáš ; Valla, Tomáš (advisor) ; Mareš, Martin (referee)
In the present work we study the algorithms for graph drawing. We focus mainly on planar graphs, but we also show a few algorithms for non-planar graphs and the methods which convert a non-planar graph into a planar one. We extend the algorithm based on the areas of inner faces by a new force, taking into account the size of angles. We describe how to use the algorithm for nding maximum independent set on circle graphs in planarization. Finally, we present a plugin for editor VRR developed to test these algorithms.
|
|
|
Planning algorithms and plan simulation in logistics domain
Štefan, Zdeněk ; Toropila, Daniel (advisor) ; Valla, Tomáš (referee)
The goal of this thesis is to compare some means of planning in the logistics domain.The aim was to compare the capabilities of those techniques among each other and against plans designed by humans.Because some planners do not return parallel plans,it is necessary to parallelize them.It is shown that some algorithms achieve good results in comparison to plans designed by hu- mans. However, due to their high time and memory consumptions they cannot be nowadays commonly used to solve more difficult tasks.
|
|
|
Music effects
Marko, Matej ; Bálek, Martin (advisor) ; Valla, Tomáš (referee)
Title: Music effects Author: Matej Marko Department: Department of applied mathematics Supervisor: Mgr. Martin Bálek Supervisor's e-mail address: Martin.Balek@mff.cuni.cz Abstract: The effects have crucial position in the proccess of creating music. They enrich song's arrangement and make it all more colorful. Aim of the work is to create application that allows the user to play a sound file and apply chosen effets on it's content in real-time. All changes in effects' settings are imidiatelly transformed into the hearable results. Certain settings can be applied on the whole file and the results afterwards exported to the file. Part of the application is naturally implementation of chosen effects. Main topic of the work's text are methods used to implement the effects. Keywords: effects, music, sound
|
|
|
Artificial intelligence in abstract 2-player games
Veselý, Pavel ; Valla, Tomáš (advisor) ; Baudiš, Petr (referee)
In this thesis we focus on algorithms for searching for the best move in a given position in an abstract strategy 2-player game. We describe algorithms Alpha-beta and Proof-number Search with their enhancements and we come with new ideas for making them quicker. We also propose an algorithm for choosing randomly between moves not much worse than the best move and ideas how to play in lost positions. We apply the algorithms on the game Tzaar which is special for having a lot of possible moves which makes the game hard for a computer. Our goal is to create a robot for playing Tzaar as good as possible. We show that our artificial intelligence can play on the level of best human and computer players. We also examine experimentally how enhancements of the algorithms help making computations quicker in this game.
|
|
| |
|
|
Visualisation of algorithms
Bašista, Peter ; Mareš, Martin (advisor) ; Valla, Tomáš (referee)
The goal of this work is to design a computer program for visualisation of algorithms and their execution in a classroom. The user writes the algorithm and attaches the prepared visualisation components to its data structures. The program will then record the progress of the computation and displays it as an interactive animation, alternatively it creates a PDF document with the key moments of the animation. In the presented work we introduce the Algorithm Animation Library. This library has been designed to be as flexible as possible, and at the same time as easy and friendly to use as possible. We present our approach towards animation of algorithms, briefly compare the developed library with the alternatives and conclude on when it is convenient to use the Algorithm Animation Library.
|
|
|
PNS for the game Arimaa
Majerech, Ondřej ; Hric, Jan (advisor) ; Valla, Tomáš (referee)
The game of Arimaa is a strategic board game that has proved to be a challenge to computers. Not only because of its huge branching factor, but also thanks to the difficulty in creating a good evaluation function to be used with the Alpha-Beta algorithm. Proof-Number Search is an algorithm that does not depend on a heuristic evaluation function and it has been successfully applied to solving endgames of various other games. In this work, we adapt and implement the Proof-Number Search method for the game of Arimaa.
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Nešetřil, Jaroslav (advisor) ; Valtr, Pavel (referee)
Ramsey theory studies the internal homogenity of mathematical structures (graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called Ramsey number, and on the minimum object size such that the rst player has a winning strategy in the corresponding combinatorial game, called game number. In this thesis, we describe such Ramsey-type theorems where the Ramsey number is substantially greater than the game number. This means, we show the existence of rst player's winning strategies, zogether with Ramsey and game numbers upper bounds, and we compare both numbers.
|
|
|
Algorithms for solving strong positional games with high symmetry
Novotná, Jitka ; Valla, Tomáš (advisor) ; Kit, Michal (referee)
In this thesis, we analyse several algorithms for solving strong positional games, mostly based on PN-search. We focus on games with high symmetry of the game plan, where it is possible to substantially reduce the partial game tree by joining isomorph positions. We review several known enhancements of PN-search and also propose some of our own design. We measure the effect of the enhancements on the clique game. A part of the thesis is a software solver for clique game for K=4 and N=5...8. We were able to solve (6,4) and (7,4) clique games and prove that the second player has a draw strategy, which was expected but not shown previously.
|
guest ::
