|
|
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...
|
|
|
Combinatorial Games Theory
Valla, Tomáš ; Nešetřil, Jaroslav (advisor) ; Sgall, Jiří (referee) ; Spirakis, Paul (referee)
Title: Combinatorial Games Theory Author: Tomáš Valla Department / Institute: IUUK MFF UK Supervisor: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstract: In this thesis we study the complexity that appears when we consider the competitive version of a certain environment or process, using mainly the tools of al- gorithmic game theory, complexity theory, and others. For example, in the Internet environment, one cannot apply any classical graph algorithm on the graph of connected computers, because it usually requires existence of a central authority, that manipu- lates with the graph. We describe a local and distributed game, that in a competitive environment without a central authority simulates the computation of the weighted vertex cover, together with generalisation to hitting set and submodular weight func- tion. We prove that this game always has a Nash equilibrium and each equilibrium yields the same approximation of optimal cover, that is achieved by the best known ap- proximation algorithms. More precisely, the Price of Anarchy of our game is the same as the best known approximation ratio for this problem. All previous results in this field do not have the Price of Anarchy bounded by a constant. Moreover, we include the results in two more fields, related to the complexity of competitive...
|
guest ::
