|
|
Solving Endgames in Large Imperfect-Information Games such as Poker
Ha, Karel ; Hladík, Milan (advisor) ; Bošanský, Branislav (referee)
Title: Solving Endgames in Large Imperfect-Information Games such as Poker Author: Bc. Karel Ha Department: Department of Applied Mathematics Supervisor: doc. Mgr. Milan Hladík, Ph.D., Department of Applied Mathematics Abstract: Endgames have a distinctive role for players. At the late stage of games, many aspects are finally clearly defined, deeming exhaustive analysis tractable. Specialised endgame handling is rewarding for games with perfect information (e.g., Chess databases pre-computed for entire classes of endings, or dividing Go board into separate independent subgames). An appealing idea would be to extend this approach to imperfect-information games such as the famous Poker: play the early parts of the game, and once the subgame becomes feasible, calculate an ending solution. However, the problem is much more complex for imperfect information. Subgames need to be generalized to account for information sets. Unfortunately, such a generalization cannot be solved straightaway, as it does not generally preserve optimality. As a consequence, we may end up with a far more exploitable strategy. There are currently three techniques to deal with this challenge: (a) disregard the problem entirely; (b) use a decomposition technique, which sadly retains only the same quality; (c) or formalize improvements of...
|
|
|
Solving interval systems by the least squares method
Tomandl, David ; Hladík, Milan (advisor) ; Hartman, David (referee)
This thesis is describing, comparing and implementing enclosure methods for solving overdetermined system of interval linear equations by the least squares method. Input data of the methods are within given intervals. We describe the structure of the solution set, which is the basis of algorithms for computing interval hull of the solution set. Although computation of the interval hull is NP-hard problem, there exist algorithms which encloses the solution set with less than exponential steps. We are heavily focusing on these algorithms. The solution set can be alternatively characterized as a solution to the symmetric interval system. Therefore the work includes solvers of the symmetric interval system. This thesis contains numerical experiments for comparing the methods. All methods are implemented in Matlab with utilisation of the interval toolbox Intlab. Powered by TCPDF (www.tcpdf.org)
|
|
|
Duality in interval linear programming
Novotná, Jana ; Hladík, Milan (advisor) ; Bartl, David (referee)
This thesis combines a traditional concept of linear programming and interval analysis. Interval analysis ensures that a result belongs to a counted interval and allows us to put an interval instead of a single value on the input. It can be useful especially in practical problems where we get data from measurements and we do not know exact values. The first explored topic is the optimal value range with respect to values and its bounds. Also, the classical concept of duality gap is expanded to interval linear programmimg, necessary and sufficient conditions for zero duality gap and connections between zero duality gap and a continuous set of optimal values are determined. Possible values of duality gap in an interval linear program are shown in examples. The last topic are weak and strong duality in interval linear programming, strong duality types for bounds of the optimal value range and their extensions. Powered by TCPDF (www.tcpdf.org)
|
|
|
Interval linear systems with linear dependencies
Král, Ondřej ; Hladík, Milan (advisor) ; Rada, Miroslav (referee)
The main problem discussed in this thesis is about finding an enclo- sure of the solution set of an interval linear system with linear dependencies. We get familiar with definitions from interval arithmetic and analysis. Then we extend them to matrices and linear systems, where we introduce several modern approaches to finding an enclosure and divide them thematically. Most of them are implemented in MATLAB using INTLAB library. We compare their precision and computational time on Toeplitz, symmetric and random matrices. For depen- dencies we design our memory saving representation. The results are interpreted and the final function, which can compute either fast, sharp or memory efficient, is build on individual methods. Powered by TCPDF (www.tcpdf.org)
|
|
|
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.
|
|
|
Extrema of the solution set of an interval linear system of equations
Šťastný, Bořek ; Hladík, Milan (advisor) ; Ratschan, Stefan (referee)
Main topic of this thesis is solving interval linear systems. At first, we describe the structure of the solution set, which is the basis of several algorithms for computing interval hull of the solution set. Although computation of the interval hull is NP-hard problem, there exist algorithms which are not apriori exponential. One such algorithm is Jansson's algorithm which we implemented in MATLAB with utilisation of the interval toolbox INTLAB. We optimised the method and compared it to related implementations. Test results show that our implementation performs better in comparison on interval systems with solution set that is intersecting with many orthants. The opossite holds true when the amount of visited orthants is low. We describe a method of verified linear programming, which is necessary for producing rigorous results.
|
|
|
Cooperative interval games
Bok, Jan ; Hladík, Milan (advisor) ; Valla, Tomáš (referee)
In this thesis, we study cooperative interval games, a generalized model of cooperative games in which worth of every coalition corresponds with a closed interval representing all possible outcomes of their cooperation. We give a brief introduction into classical cooperative games, interval analysis and finally introduction to cooperative interval games with focus on selections, that is on all possible outcomes of interval game with no additional uncertainty. We introduce new selection-based classes of interval games and prove their characterizations and relation to existing classes. We show a new results regarding core and imputations. We introduce a definition of strong imputation and core and examine a problem of equality of two different versions of core -- the main stability solution of cooperative interval games. Finally, we make some new remarks on Shapley value of interval games.
|
|
|
Eigenvalues of symmetric interval matrices
Kaleyski, Nikolay Stoyanov ; Hladík, Milan (advisor) ; Hartman, David (referee)
The goal of the thesis is to describe and possibly improve some algorithms for finding inner and outer approximations of the borders of eigenvalue intervals of real symmetric interval matrices, to modify them so that they perform verified computations and to implement them in the Matlab programming language. The main principles of verification and interval arithmetic are described, as well as the used theoretical foundations and the problems which occur when attempting to verify the individual algorithms, including possibilities of overcoming them. Experiments illustrating some empirical properties of the algorithms are described. The practical result of the thesis is a software package for computing approximations of the sets of eigenvalues of symmetric interval matrices. Powered by TCPDF (www.tcpdf.org)
|
|
|
Evaluating public state space abstractions in extensive form games with an application in poker
Moravčík, Matej ; Hladík, Milan (advisor) ; Zimmermann, Karel (referee)
Efficient algorithms exist for finding optimal strategies in extensive-form games. However human scale problems, such as poker, are typically so large that computation of these strategies remain infeasible with current technology. State space abstraction techniques allow us to derive a smaller abstract game, in which an optimal strategy can be computed and then used in the real game. This thesis introduces state of the art abstraction techniques. Most of these techniques do not deal with public information. We present a new automatic public state space abstraction technique. We examine the quality of this technique in the domain of poker. Our experimental results show that the new technique brings significant performance improvement. Powered by TCPDF (www.tcpdf.org)
|
|
|
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
|
guest ::
RSS feed.