|
|
Search in Imperfect Information Games
Schmid, Martin ; Hladík, Milan (advisor) ; Szepesvari, Csaba (referee) ; Bošanský, Branislav (referee)
From the very dawn of the field, search with value functions was a fun- damental concept of computer games research. Turing's chess algorithm from 1950 was able to think two moves ahead, and Shannon's work on chess from 1950 includes an extensive section on evaluation functions to be used within a search. Samuel's checkers program from 1959 already combines search and value functions that are learned through self-play and bootstrapping. TD-Gammon improves upon those ideas and uses neural networks to learn those complex value functions - only to be again used within search. The combination of decision-time search and value functions has been present in the remarkable milestones where computers bested their human counterparts in long standing challenging games - DeepBlue for Chess and AlphaGo for Go. Until recently, this powerful framework of search aided with (learned) value functions has been limited to perfect information games. As many interesting problems do not provide the agent perfect information of the environment, this was an unfortunate limitation. This thesis introduces the reader to sound search for imperfect information games. 1
|
|
|
Integer programming and its applications
Eliáš, Marek ; Pergel, Martin (advisor) ; Hladík, Milan (referee)
In this thesis we present and implement several graph algorithms. In the rst part, we discus algorithm for the minimum weighted perfect matching in bipartite and general graphs based on the primal-dual method and their modi cations. In the second part, there are algorithms for the max-cut in planar graphs and Christo des' heuristic for TSP. We present full descriptions of these algorithms providing either proof of correctness or reference to the literature. The last part deals with two approaches which we use to visualise these algorithms with di erent degree of interactivity both allowing custom graph on input.
|
|
|
Operation optimization in wholesale warehouses
Kolárik, Jan ; Pangrác, Ondřej (advisor) ; Hladík, Milan (referee)
The goal of this work is to choose a strategy for given warehouse that will increase the efficiency of its operation. This is primarily about reducing customer downtime and minimizing the distance travelled by handling machines. The final program can generate warehouse structure according to given parameters and then evaluate monitored variables from simulated operations based on optimization techniques used. There is also a planar and spatial warehouse model available, which helps to visualize what is actually happening in the warehouse. The program could serve as an auxiliary tool in the organizing of wholesale warehouse operations and reduce costs required for its operation.
|
|
|
Orthogonal contrator
Krejčová, Kristýna ; Hladík, Milan (advisor) ; Pilát, Martin (referee)
The thesis proposes an orthogonal contractors. At the beginning we define the basic concepts of interval analysis and interval linear algebra. Then, we pro- pose several contractor methods. Based on propagation techniques, we propose contraction according to bilinear and quadratic terms of the conditions that we get from the properties of orthogonal matrices. We also linearize bilinear terms and use linear programming. The known contractors by eigenvalues we employed to the construction contractor by the determinant. The proposed methods are implemented in Matlab with the use of the toolbox Intlab and the library Versoft. Finally, we test and compare the presented methods. Based on the comparison of particular techniques we build a final contractor. 1
|
|
|
Visualisation of phenomena related to linear programming
Gregor, Jan ; Pergel, Martin (advisor) ; Hladík, Milan (referee)
This thesis introduces design and implementation of scripting language especially focused on visualization of phenomena related to linear programming. We describe a construction of an interpreter and a theory around it. Further we specify what the linear programming is and we show the simplex method. Regarding requierements of manipulation and visualization in vector space of dimension greater than three, there could not be used standard methods, e.g., from computer graphic. That is why there is also a description of modified algorithms used in this cases. Namely projection, transformation and drawing of n-dimensional polyhedron. This thesis also contains examples of scripts showing possibilities of the language and its interpreter.
|
|
|
Simulation of Car Traffic
Gregor, Ivan ; Pudlák, Petr (advisor) ; Hladík, Milan (referee)
This bachelor's thesis describes the main components of the program that simulates the car traffic. It describes the representation of road system, agents, simulation in progress and its output. It also describes several results reached during the simulation of concrete traffic situations. Moreover, the comparison between this program and multiagent systems is included in the end of this thesis. The road system consists of roads and crossroads which are controlled by traffic lights. The user of this program can observe different agent's behaviour. The only condition is that the class that represents an agent implements a uniform interface. The term agent means the car and its driver together. It is autonomous object that moves inside the road system respecting given limits of the simulation. Consequently, behaviour of agents is limited by the simulation rules. Agents are possibly controlled by simulation in order to avoid collisions and not to break traffic rules. The output of the simulation is used to compare the successfulness of individual strategies of agents in terms of length of the drive or fuel usage.
|
|
|
Visualization in vector spaces
Klímek, Jakub ; Fiala, Jiří (advisor) ; Hladík, Milan (referee)
The goal was to create a set of Java applets, which would serve as an addition to the teaching of Linear algebra. These applets make possible to compute with rational numbers, real numbers, complex numbers and Zp - integers modulo prime p using addition, subtraction, multiplication and division. It is also possible to compute with vectors of elements of those spaces using addition and subtraction of vectors and multiplication and division by scalar. In addition, the vector calculator can figure coordinates of a vector, determine a linearly independent subset of vectors and, when in standard scalar product space, figure an orthogonal projection onto a subspace generated by a set of vectors. The advantage of these applets is their ease of use simulating a classical handheld calculator.
|
|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (advisor) ; Pergel, Martin (referee)
The thesis is focused on the Sivia algorithm (Set Inverter via Interval Ana- lysis) designed for solving a continuous constraint satisfaction problem using interval methods and propagation techniques. Basic properties of the algorithm are derived, including the correction of its presented complexity bound. Some improvements concerning the testing of constraint satisfaction and optimiza- tion of the number of interval boxes describing the solution are proposed. The thesis also introduces contractors used to enhance the effectivity of the Sivia algorithm by reducing the interval boxes processed. Presented algorithms were implemented in a solver for nonlinear constraints with a simple visualization of the result using the Matlab language. A comparison of basic contractors on specific examples is given.
|
|
|
Game theory and poker
Schmid, Martin ; Hladík, Milan (advisor) ; Zimmermann, Karel (referee)
This thesis introduces the basic concepts of the game theory. Necessary models and solution concepts are described. Follows the summary of the computational complexity of these concepts and corresponding algorithms. Poker is formalized as one of the game theory game models. State of the art algorithms for the ex- tensive form games are explained with the application to the Poker. The thesis also introduces the Annual Computer Poker Competition and participating pro- grams. Finally, new result about the extensive form games with many actions is presented. Keywords: Game theory, Poker, Nash equilibrium, Extensive form games
|
|
| |
guest ::
RSS feed.