|
|
Gobblet game from the point of artificial intelligence
Kotrč, Pavel ; Majerech, Vladan (referee) ; Vomlelová, Marta (advisor)
Gobblet is a new abstract board game, rules of which are based on the classic 4-in-arow game played on 4×4 board. However, the ability to gobble up and move the pieces on the board greatly increases its complexity and Gobblet is thus comparable to games like Checkers or Othello. That makes it interesting from the artificial intelligence point of view. This thesis explores the possibilities of classic and more recent methods for searching the Gobblet game tree - the minimax algorithm, alpha-beta pruning, a heuristic for move ordering, iterative deepening and others. The resulting algorithm is compared to the computer players on the Boardspace game server where it plays above-average with the best-playing robot. Implementation of all described algorithms and a graphical user interface for testing them in the Java programming language is an inseparable part of this thesis.
|
|
|
Plausible computational model of a rodent behaviour
Preuss, Michal ; Vomlelová, Marta (referee) ; Brom, Cyril (advisor)
Two different computational models are presented. These models simulate behaviour of a rat during a laboratory experiment focused on spatial cognition. First model arises from principles of reinforcement learning while second represents a method usual for models in computational neuroscience. The two models are compared with the results of laboratory experiments as well as with each other. Assets of both models and the possibility of combining the two methods are then discussed.
|
|
|
Constraint satisfaction for HW/SW verification
Cigler, Luděk ; Vomlelová, Marta (referee) ; Barták, Roman (advisor)
Constraint satisfaction techniques (CSP) are a powerful framework for modeling and solving various problems in artificial intelligence and operations research. Verification of HW and SW can profit from employing constraint satisfaction for test generation. The essential property of a CSP algorithm (wrt. test generation) is the uniform generation of solution samples. We present several algorithms for sampling solutions of a CSP and extend them so that they can be used for sampling solutions of CSP with preferences. We test the performance of our algorithms on various benchmark problems.
|
|
|
Text clustering and classification /(Klastrování a klasifikace textů)
Gabašová, Evelina ; Hric, Jan (referee) ; Vomlelová, Marta (advisor)
Text clustering and classi cation are important machine learning tasks. In this work, a combination of their approaches is presented. The main purpose was to automatically prepare a set of clusters (or generally concepts), which would subsequently serve as a training data for learning of a classiffi er. This work comprises of theoretical background, implementation details and experimental results of clustering and classi cation of text documents. A train set of documents is rst hierarchically clustered by the bisecting k-means algorithm. The result is o ered to an expert for modifi cations and possible improvements of the hierarchy. Following this, the resulting structure is used for learning of a naive Bayes classi er and a test set of documents is classi ed by it. A program was developed to perform these tasks and its results are evaluated and compared in processing document collections written in both English and Czech.
|
|
|
POMDPs for dynamic troubleshooting
Krč, Pavel ; Hric, Jan (referee) ; Vomlelová, Marta (advisor)
Dynamic troubleshooting is a process of analysing a running system in real time, predicting or detecting possible problems, correcting them and acting so as to avoid them. When realised by a computer in its most generic form it is an optimum decision problem. The framework of partially observable Markov decision processes (POMDPs) is well suited for such problems as it allows modelling the uncertainty of the future evolution of the process as well as the limited knowledge about the current state and enables to presume its own future choices of actions that alter the system or gain knowledge about it. In this work the author provides an introduction to the theory of POMDPs and describes current POMDP solution algorithms with respect to their applicability for dynamic troubleshooting. Further he presents a speci c dynamic troubleshooting problem, solves it using generic POMDP solutions and proposes his own heuristic for it which can be easily generalised to a wider class of POMDP problems. He creates a Python programming language framework for solving POMDPs, implements the mentioned algorithms within it and tests them on the presented problem.
|
|
| |
|
|
Approximate solution of Unconstrained influence diagrams
Fried, Vojtěch ; Vomlelová, Marta (advisor) ; Studený, Milan (referee)
We give an introduction to the theory of probabilistic graphical models and describe several types of them (Bayesian Networks - BN, Influence Diagrams - ID, Unconstrained Influence Diagrams - UID). Unconstrained Influence Diagrams support the possibility for the user to choose the ordering of decisions based on observations. This increases the expressive power of UIDs compared to IDs but makes it harder to find an optimal solution. It is often impossible to find an optimal solution because of exponential complexity increase compared to IDs. Therefore we design and investigate several approximate methods to solve UIDs. The result of these methods is an ordinary ID created from the former UID by adding edges. The optimal solution of the ID should be as close to the original UID as possible. Heuristical methods represent one type of the methods investigated. Heuristical methods use a simplification of the optimal algorithm. During the run of the algorithm heuristics are used to cut off the branches that are not perspective for further calculation. Another type of methods is to create the ID directly. We evaluate our methods experimentally based on randomly generated UIDs of three types and compare their performance namely to the optimal solution and to equally complex random methods.
|
|
|
Non-optimal solver of permutational puzzles using divide and conquer technique
Penkala, Michal ; Vomlelová, Marta (referee) ; Majerech, Vladan (advisor)
In the present work I study the attributes of permutation puzzles and try to find the algorithms usable for solving these puzzles. The task of this project is to implement the algorithm for non-optimal solution of permutation puzzles by decomposition to sub problems and invent a suitable form of puzzle definition. The result of this project is a program with graphic interface, which allows the user to create custom permutation puzzle. With this puzzle, the user will be able to do the predefined moves, make custom positions and search the result of the position.
|
|
|
Life/death analysis in Go (Analyzátor života skupiny v Go)
Kozelek, Tomáš ; Vomlelová, Marta (advisor) ; Hric, Jan (referee)
In this thesis I focused myself on problematics of solving life and death problems in the game of Go, which is one of fundamental skills of a Go playing program. Together with thesis, life and death solving program TGA was created. Program is built upon basic space search algorithms from the game theory (e.g. alpha beta pruning, transposition tables) in combination with methods using knowledges about the game of Go (heuristics and pruning methods). For program purposes I created "block oriented" position representation, I implemented simpliffied static analysis of life and death of the group and I proposed a set of heuristic. These heuristics not only speed up search signifficantly, moreover they make it possible to solve di±cult problems of "under the stones" type. Program is designed to solve mostly enclosed problems and it is capable to treat di®erent life and death solving pecularities (e.g. different types of ko, seki, "bent four in the corner"). As for performance, I estimate program's strength in solving speciffied Go problems to be 1 dan. This is comparable with a strong human player.
|
|
| |
guest ::
RSS feed.