|
|
Text clustering and classification /(Klastrování a klasifikace textů)
Gabašová, Evelina ; Vomlelová, Marta (advisor) ; Hric, Jan (referee)
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.
|
|
|
Configurable Entity Extraction
Koval, Petr ; Hric, Jan (advisor) ; Kopecký, Michal (referee)
In the present work we deal with the task of the Information Extraction. The task of this work is to implement a system for Information Extraction working with Czech texts. At first, created system constructs automatically a set of extraction patterns. The construction of this set is based on training examples. Then the system is able to find relevant entities in the present collections of texts. Design of our system enables to use the created set of extraction patterns both for domain searching and for searching without domain specification. This work contains description of similar systems working with English texts.
|
|
|
Sub-optimal algorithms for solving sliding puzzles
Michalík, Petr ; Surynek, Pavel (advisor) ; Hric, Jan (referee)
Title: Sub-optimal algorithms for solving sliding puzzles Author: Petr Michalík Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Pavel Surynek, Ph.D. Supervisor's e-mail address: Pavel.Surynek@mff.cuni.cz In the present work techniques for solving the so-called sliding tiles puzzles, which generate optimal or sub-optimal solution, are studied. This thesis focuses especially on a specific variant of the puzzle: the (n^2-1)-puzzle. This work shows and compares current methods for solving this type of problem. A choosen method is a subject to a close analysis of complexity and is also implemented so that theoretical and experimental results could be confronted. An alternative sub-optimal algorithm is proposed and its theoretical analysis is presented. This algorithm is implemented as well and is compared with the existing algorithm. Both the theoretical analysis and the test results show that better (shorter) solutions can often be obtained using this alternative algorithm.
|
|
|
Artificial intelligence for strategy games
Hubík, Tomáš ; Sýkora, Ondřej (advisor) ; Hric, Jan (referee)
In the present work I devote to simple turn-based strategic game design and implementation of a platform for testing algorithms for this game. Another part of the work is implementation of various types of algorithms for this platform. I have implemented one algorithm based on map and game environment analysis without any prediction or searching the game state space. Next two algorithms are based on searching the game state and making decisions using modified Minimax algorithm. The last two algorithms are inspired by method called Monte Carlo Planning.
|
|
|
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.
|
|
|
POMDPs for dynamic troubleshooting
Krč, Pavel ; Vomlelová, Marta (advisor) ; Hric, Jan (referee)
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.
|
|
|
Scrabble
Dvořák, Filip ; Babilon, Robert (advisor) ; Hric, Jan (referee)
The subject matter of the submitted thesis is a study of the board game Scrabble and its transfer to electronic form. The object of this thesis is to present possible and used approaches in implementation of Scrabble systems and to present and evaluate data structures and algorithms used in those systems. The implementation of the chosen approaches is a part of this thesis. After the brief introduction into the rules of Scrabble and initiatory problem's analyse there are presented data structures used for dictionary storage, move generating algorithms and possible approaches in game strategies. The practical part of this thesis deals with chosen approaches and reasons why they were chosen. At the end of this thesis there is a summary of possible contributions of developed system and its possible following expansions.
|
|
|
Effective Algorithms for Verifying Goals in Computer Games
Suda, Martin ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
In the present work we study non-uniform methods for searching game trees of two player games with perfect information. Particularly the non-uniformity based on threats as realized in lambda search and dual-lambda search algorithms is investigated. Threats, de ned as such attack moves that if followed by a pass from the defender result in his certain loss, allow for a reduction of the search space while guaranteeing correctness at the same time. The work then describes a new method for construction of so called relevancy zones, a list of moves or places on the game desk that can only have in uence on the result of the problem in question. Using these zones it is possible to speed up the mentioned algorithms considerably. In the work there are also described three games, AtariGo, Hex and Go-Moku, and their appropriateness with respect to the studied methods is analyzed. Part of the work is also an implementation of the methods for these games using known techniques (transposition tables, history heuristic).
|
|
|
Solving of Problems using MCTS
Malý, Dominik ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
Title: Solving problems using MCTS Author: Dominik Malý Department: Department of theoretical informatics and mathematical logic Supervisor: RNDr. Jan Hric Supervisor's e-mail address: Jan.Hric@mff.cuni.cz Abstract: MCTS (Monte Carlo Tree Search) methods are a state-of-the-art approach to the computer solution of strategic board game Go. Because of their versatility and successfulness, these techniques show great potential for all kinds of problems. This paper aims to explore the suitability of MCTS for solving different kind of problems, specifically games of one player, like Sudoku or SameGame. I've created a computer player based on MCTS, who can solve not only Sudoku and SameGame, but also other tasks of similar kind. I've experimentally examined many MCTS extensions and their eligibility for solving these games and through extensive testing I've also compared the suitability of various kinds of UCT selection fun- ctions and used heuristics. In case of SameGame I've compared my algorithm to another exi- sting one undertaking the same problem. In the end I've described what kind of problems has a MCTS-based computer player to overcome, if it is to successfully solve games of this type, and what characteristics should these problems posses to be suitable for MCTS solution. Keywords: MCTS, Go, Sudoku,...
|
|
|
Detecting elementary particles with Timepix3 detector
Meduna, Lukáš ; Mráz, František (advisor) ; Hric, Jan (referee)
Detecting elementary particles and observing accompanying events in particle colliders is one of the most important field of current research in experimental physics. TimePix and its successor TimePix3 are types of the currently used detectors which are placed beside other in ATLAS experiment conducted by Eu- ropean Organization for Nuclear Research. Such detectors can produce huge amount of data about passing particles at high rate. The goal of the thesis is to develop methods for detecting and classification of elementary particles observed by detector network ATLAS-TPX3. Suitable methods for clustering and/or classification based on semi-labelled data should be identified or new one should be developed. The proposed methods will be implemented and their performance on real data will be evaluated. The results will also include an implementation of framework for preprocessing low level data from detector network ATLAS-TPX3 in real-time and creating outputs that are suitable for subsequent physics investigation (e.g. ROOT framework files) includ- ing the proposed or future methods for particle classification. 5
|
guest ::
