|
|
PNS for the game Arimaa
Majerech, Ondřej ; Hric, Jan (advisor) ; Valla, Tomáš (referee)
The game of Arimaa is a strategic board game that has proved to be a challenge to computers. Not only because of its huge branching factor, but also thanks to the difficulty in creating a good evaluation function to be used with the Alpha-Beta algorithm. Proof-Number Search is an algorithm that does not depend on a heuristic evaluation function and it has been successfully applied to solving endgames of various other games. In this work, we adapt and implement the Proof-Number Search method for the game of Arimaa.
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Nešetřil, Jaroslav (advisor) ; Valtr, Pavel (referee)
Ramsey theory studies the internal homogenity of mathematical structures (graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called Ramsey number, and on the minimum object size such that the rst player has a winning strategy in the corresponding combinatorial game, called game number. In this thesis, we describe such Ramsey-type theorems where the Ramsey number is substantially greater than the game number. This means, we show the existence of rst player's winning strategies, zogether with Ramsey and game numbers upper bounds, and we compare both numbers.
|
|
|
Algorithms for solving strong positional games with high symmetry
Novotná, Jitka ; Valla, Tomáš (advisor) ; Kit, Michal (referee)
In this thesis, we analyse several algorithms for solving strong positional games, mostly based on PN-search. We focus on games with high symmetry of the game plan, where it is possible to substantially reduce the partial game tree by joining isomorph positions. We review several known enhancements of PN-search and also propose some of our own design. We measure the effect of the enhancements on the clique game. A part of the thesis is a software solver for clique game for K=4 and N=5...8. We were able to solve (6,4) and (7,4) clique games and prove that the second player has a draw strategy, which was expected but not shown previously.
|
|
|
Ramsey theory and combinatorial games
Valla, Tomáš ; Nešetřil, Jaroslav (advisor)
Ramsey theory studies the internal homogenity of mathematical structures (graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called Ramsey number, and on the minimum object size such that the rst player has a winning strategy in the corresponding combinatorial game, called game number. In this thesis, we describe such Ramsey-type theorems where the Ramsey number is substantially greater than the game number. This means, we show the existence of rst player's winning strategies, together with Ramsey and game numbers upper bounds, and we compare both numbers.
|
|
|
Cordless drill powered hobby car
Valla, Tomáš ; Böhm, Michael (referee) ; Štětina, Josef (advisor)
This bachelor thesis deals with the design of a cordless drill powered hobby car. The cordless drill must remain usable for normal use. The theoretical part deals with the description of the historical development of childrens’ cars from the first manufactured models to modern pedal and electric carts. The next section describes the origin of cordless drills. The following section shows today's options for purchasing prams. The market has greatly enriched, and it is practically impossible not to choose. The construction part is focused on the design of individual components and a list of purchased parts. It also includes basic calculations for the selected chain and the designed structure.
|
|
|
Positional games with efficient winning strategy
Svoboda, Jakub ; Šámal, Robert (advisor) ; Valla, Tomáš (referee)
We study games where two players are coloring edges of infinite complete graph. Both players are trying to create given target subgraph colored by their colors. Firstly, we will look at situation when the target subgraph is a complete graph. We will show that first player has winning strategy if the target subgraph is complete graph on at most three vertices. Then we will slightly change the rules. This will help us show that the first player has a winning strategy if he can bound the size of the complete graph on which the game is played or he can color a few edges more then the opponent. At the end we will discuss game, when a complete graph of a given size is a minor of target subgraph. We will show a winning strategy for the first player and for small size of complete graph which is the minor of target subgraph. We also will discuss, why the first player should have winning strategy for all games of this type. 1
|
|
|
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.
|
|
|
Online Ramsey Theory
Dvořák, Pavel ; Valla, Tomáš (advisor) ; Koucký, Michal (referee)
An online Ramsey game is a game between Builder and Painter, alternating in turns. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some round there is a monochromatic copy of the fixed graph H, otherwise Painter is the winner. In this thesis we investigate the computational complexity of the related decision problem and we show that it is PSPACE-complete. Moreover, we study a version of the game when Builder can draw only planar graphs and a generalization of the game for hypergraphs. We found a new class of graphs unavoidable on planar graphs. We provide a result showing that Builder wins the online Ramsey game on 3-uniform hyperforests when the goal graph H is 1-degenerate. 1
|
|
|
Desktop client for open social networks
Kasinec, Maroš ; Valla, Tomáš (advisor) ; Vaner, Michal (referee)
For the past decade social network sites emerged rapidly and effect not only online communication and social experience but also businesses, media and governments. However, their greatest deficiency, closed and centralized character, remains unnoticed among the general public. This thesis discusses and evaluates open and decentralized alternatives for them and draws attention to one particular - buddycloud. While leveraging the use of XMPP protocol, buddycloud with its Channel protocol appears to be a promising approach for opening ecosystem of social networks. It enables them to work in federated manner like e-mail network does today. As a contribution to the buddycloud project this thesis presents SocialDesktopClient, a desktop client for multiple social network services. It deals with modular client architecture and a Channel protocol implementation as the client's first social network service.
|
|
|
Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe
Dvořák, Pavel ; Valla, Tomáš (advisor) ; Šámal, Robert (referee)
In this thesis we study positional games, especially multidimensional tic-tac-toe. We compare present advanced algorithms (Pn-search, Db-search and λ-search) for position solving in positional games. We apply the algorithms on the do- main of 43 and 53 games, which are the first nontrivial cases of 3-dimensional tic-tac-toe. We parallelize Pn-search for cases when there are more starting po- sitions. We apply Pn-search as a single-thread task and we solve how to share the transposition table with solved positions. Our main and clearly theoretical result is the characterization of the group of all automorphisms of combinatorial cube nd with the same set of lines as multidimensional tic-tac-toe has. This is a generalization of Silver [The American Mathematical Monthly, Vol. 74, No. 3, 1967], who characterized the automorphisms of the game 43 . 1
|
guest ::
