|
|
Evaluation function for Atari-go
Kudělka, Miloš ; Majerech, Vladan (referee) ; Hric, Jan (advisor)
The present work describes a design and an implementation of Atari Go computer game. This includes an implementation of mini-max and mini-max with alpha-beta pruning algorithms for searching for the best moves. Additionally, the work describes the design and the implementation of an evaluation function and the selection of suitable criteria of the position. This function then can evaluate the position by evaluating these criteria. Further on, the work demonstrates one style of improving the parameters of evaluation function - simple learning algorithm is designed, applied to this problem and implemented. This algorithm improves the parameters by playing games. The results of improvings are presented in the work, too.
|
|
|
City-building game
Hejda, Benjamin ; Hric, Jan (referee) ; Malenko, Jaromír (advisor)
Present work describes the Sword of Damocles application. It is a citybuilding strategy game, where player's task is to care about some city and wellbeing of its inhabitants. Main goal of the work was to design and implement a control that would allow to govern the city in detail and e ectively at once. That was achieved by system of parameters set as expressions referencing other parameters and city describing indicators. Substantial feature of the game are independently acting people that can not be directly controlled. Part of the program is a scenario editor that makes the gameplay widely customizable. The graphical user interface is very simple, however, it is possible to change it not a ecting core of the application.
|
|
|
Go on Small Boards
Čížek, Pavel ; Majerech, Vladan (referee) ; Hric, Jan (advisor)
In presented work we study applicability of the heuristics used in computer analysis of the chess (to be specific we will consider transposition tables, killer moves, history heuristics and counter-moves) for the valuation of the position in the go. In the first part will try to deal with problems which arises, because rules and behaviour of the chess and go are really different in some ways. Obtained heuristics had been implemented and at the end we will try to evaluate their efficiency and mutual (in)dependence experimentally using this program to solve some simple positions.
|
|
|
Effective Algorithms for Verifying Goals in Computer Games
Suda, Martin ; Majerech, Vladan (referee) ; Hric, Jan (advisor)
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).
|
|
|
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.
|
|
|
Using Machine Learning Techniques to Analyze and Recognize Complex Patterns of Student E-Discussions
Mikšátko, Jan ; McLaren, Bruce M. (advisor) ; Hric, Jan (referee)
Visual e-discussion is a form of debate in that contributions are written into graphical shapes and linked to one another according to their relationship. In order to moderate several simultaneous e-discussions effectively, it is important to point teachers to interesting clusters of contributions. We designed an algorithm that uses inexact graph matching along with text analysis and machine learning classifiers for searching for such patterns based on a provided example. The method was evaluated on a dataset of real discussion and demonstrated promising initial results.
|
|
|
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.
|
|
|
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.
|
|
|
Methods of MCTS and the game Arimaa
Kozelek, Tomáš ; Majerech, Vladan (referee) ; Hric, Jan (advisor)
Game of Arimaa is an artificially created strategic board game with the purpose to be difficult for computers. A vast majority of introduced computer engines for Arimaa are based on successful approaches from chess, namely the minimax algorithm with pruning and further extensions. In this thesis we have analyzed the applicability of the so called MCTS methods in the game of Arimaa. MCTS methods are a state-of-the-art approach to the computer Go with bright prospects in other strategic games as well. We have implemented a MCTS based Arimaa engine called Akimot and adapted the MCTS techniques for the Arimaa environment. We have experimented with various MCTS enhancements known from computer Go and identified which are prospective in our setup. Moreover, we have proposed several new enhancements on ourselves. Performance experiments show that our MCTS approach is comparable to an average engine.
|
|
|
Artificial intelligence for strategy games
Hubík, Tomáš ; Hric, Jan (referee) ; Sýkora, Ondřej (advisor)
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.
|
guest ::
