No description available.

Many new board games are designed each year, ranging from the unplayable to the truly exceptional. For each successful design there are untold numbers of failures; game design is something of an art. Players generally agree on some basic properties that indicate the quality and viability of a game, however these properties have remained subjective and open to interpretation. The aims of this thesis are to determine whether such quality criteria may be precisely defined and automatically measured through self-play in order to estimate the likelihood that a given game will be of interest to human players, and whether this information may be used to direct an automated search for new games of high quality. Combinatorial games provide an excellent test bed for this purpose as they are typically deep yet described by simple welldefined rule sets. To test these ideas, a game description language was devised to express such games and a general game system implemented to play, measure and explore them. Key features of the system include modules for measuring statistical aspects of self-play and synthesising new games through the evolution of existing rule sets. Experiments were conducted to determine whether automated game measurements correlate with rankings of games by human players, and whether such correlations could be used to inform the automated search for new high quality games. The results support both hypotheses and demonstrate the emergence of interesting new rule combinations.

There have been several papers on the subject of traditional peg solitaire on different boards. However, in this paper we consider a generalization of the game to arbitrary boards. These boards are treated as graphs in the combinatorial sense. We present necessary and sufficient conditions for the solvability of several well-known families of graphs. In the major result of this paper, we show that the cartesian product of two solvable graphs is likewise solvable. Several related results are also presented. Finally, several open problems related to this study are given.

In a 2011 paper by Beeler and Hoilman, the game of peg solitaire is generalized to arbitrary boards. These boards are treated as graphs in the combinatorial sense. An open problem from that paper is to determine the minimum number of edges necessary for a graph with a fixed number of vertices to be solvable. This thesis provides new bounds on this number. It also provides necessary and sufficient conditions for two families of graphs to be solvable, along with criticality results, and the maximum number of pegs that can be left in each of the two graph families.

In this thesis we explore a number of ways in which combinatorial games can be used to help prove results in the area of propositional proof complexity. The results in this thesis can be divided into two sets, the first being dedicated to the study of Resolution space (memory) requirements, whereas the second is centered on formalizing the notion of `dangerous' reductions. The first group of results investigate Resolution space measures by asking questions of the form, `Given a formula F and integer k, does F have a [Type of Resolution] proof with [Type of Resource] at most k?'. We refer to this as a proof complexity resource problem, and provide comprehensive results for several forms of Resolution as well as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as practical motivations: Proof complexity research has focused on the size of proofs, and Resolution space requirements are an interesting new theoretical area of study. In more practical terms, the Resolution proof system forms the underpinnings of all modern SAT-solving algorithms, including clause learning. In practice, the limiting factor on these algorithms is memory space, so there is a strong motivation for better understanding it as a resource. With the second group of results in this thesis we investigate and formalize what it means for a reduction to be `dangerous'. The area of SAT-solving necessarily employs reductions in order to translate from other domains to SAT, where the power of highly-optimized algorithms can be brought to bear. Researchers have empirically observed that it is unfortunately possible for reductions to map easy instances from the input domain to hard SAT instances. We develop a non-Hamiltonicity proof system and combine it with additional results concerning the Prover/Delayer game from the first part of this thesis as well as proof complexity results for intuitionistic logic in order to provide the first formal examples of harmful and beneficial reductions, ultimately leading to the development of a framework for studying and comparing translations from one language to another.

In this thesis we explore a number of ways in which combinatorial games can be used to help prove results in the area of propositional proof complexity. The results in this thesis can be divided into two sets, the first being dedicated to the study of Resolution space (memory) requirements, whereas the second is centered on formalizing the notion of `dangerous' reductions. The first group of results investigate Resolution space measures by asking questions of the form, `Given a formula F and integer k, does F have a [Type of Resolution] proof with [Type of Resource] at most k?'. We refer to this as a proof complexity resource problem, and provide comprehensive results for several forms of Resolution as well as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as practical motivations: Proof complexity research has focused on the size of proofs, and Resolution space requirements are an interesting new theoretical area of study. In more practical terms, the Resolution proof system forms the underpinnings of all modern SAT-solving algorithms, including clause learning. In practice, the limiting factor on these algorithms is memory space, so there is a strong motivation for better understanding it as a resource. With the second group of results in this thesis we investigate and formalize what it means for a reduction to be `dangerous'. The area of SAT-solving necessarily employs reductions in order to translate from other domains to SAT, where the power of highly-optimized algorithms can be brought to bear. Researchers have empirically observed that it is unfortunately possible for reductions to map easy instances from the input domain to hard SAT instances. We develop a non-Hamiltonicity proof system and combine it with additional results concerning the Prover/Delayer game from the first part of this thesis as well as proof complexity results for intuitionistic logic in order to provide the first formal examples of harmful and beneficial reductions, ultimately leading to the development of a framework for studying and comparing translations from one language to another.

Cette thèse explore des problématiques liées aux jeux. Les jeux qui nous intéressent sont ceux pour lesquels il n'y a pas d'information cachée: tout les joueurs ont accès à toute l'information relative au jeu; il n'y a pas non plus d'aléa. Certains jeux de société (comme les échecs ou le go) satisfont ces propriétés et sont représentatifs des jeux que nous considérons ici. La notion de stratégie est au centre de l'étude de ces jeux. En termes simples, une stratégie est une façon de jouer qui permet de s'assurer un certain résultat. La question centrale, à la fois quand on joue à un jeu et quand on l'étudie, est le problème de trouver la 'meilleure' stratégie, qui assure la victoire du joueur qui l'applique. Dans cette thèse, nous considérons à la fois des jeux à un joueurs, appelés puzzles combinatoires, et des jeux à deux joueurs. Le Rubik's cube, Rush-Hour, et le taquin sont des exemples biens connus de puzzles combinatoires. Récemment, un certain nombre de jeux -- des jeux à un joueur notamment -- ont connu un regain d'intérêt en tant qu'objets d'étude dans un domaine plus grand appelé reconfiguration. Les puzzles que l'on vient de mentionner peuvent tous être décrit de la façon suivante: il y a un ensemble de configurations, qui représente tous les états possibles du jeu; et le joueur est autorisé à transformer une configuration en une autre à via un certain nombre de règles. Le but est d'atteindre une certaine configuration cible à partir d'une configuration initiale. Le domaine de la reconfiguration étend cette définition à des problèmes de recherche: l'ensemble des configurations devient l'ensemble des solutions à une instance d'un problème donné, et l'on se demande si l'on peut transformer une solution donnée en une autre en utilisant uniquement un ensemble de règles de transformation précises. La recherche sur ce type de problèmes a été guidée par des motivations algorithmiques: ce processus peut être vu comme un moyen d'adapter une solution déjà en place en une nouvelle solution à l'aide de petits changements locaux; et des connections avec d'autres problèmes comme la génération aléatoire, ainsi que des problèmes de physique statistique. Les jeux à deux joueurs, qui sont aussi appelés jeux combinatoires, ont été étudiés depuis le début du XXème siècle avec les travaux de Bouton, continués par Berlekamp, Conway et Guy avec le développement d'une théorie unifiant un certain nombre de jeux classiques. Ce travail se focalise sur des joueurs parfaits, c'est à dire qui choisissent toujours le coup optimal. Notre but est de caractériser lequel des deux joueurs possède une stratégie qui lui assure la victoire, quelque soient les coups de son adversaire. Cette approche est au coeur de ce qui est appelé la Théorie des Jeux Combinatoires. Une grande parties des recherche est focalisée sur des 'jeux mathématiques', qui sont des jeux inventés par des mathématiciens, souvent avec des règles très simples, et rarement connus en dehors de la recherche. La motivation principale pour étudier ces jeux est la présence de liens parfois surprenant entre ces jeux et d'autres domaines des mathématiques comme entre autre la théorie des nombres, les automates ou les systèmes dynamiques. Dans cette thèse, nous étudions ainsi des jeux à un et deux joueurs. Nous nous intéressons tout particulièrement à la complexité de ces jeux, c'est à dire évaluer à quel point il est difficile (d'un point de vue algorithmique) de calculer une stratégie gagnante. Nous nous intéressons aussi à leur structure et à certaines propriétés qu'ils peuve satisfaire. Finalement, un des outils principaux dans cette étude est la notion de graphe, et nous utilisons notamment des méthodes et des techniques provenant de théorie des graphes pour résoudre ces problèmes / This thesis explores problems related to games. The games that we consider in this study are games for which there is no hidden information: all the players have access to all the information related to the game; there is also no randomness and everything is deterministic. A few well-known board games (such as chess or go) fall in this category and are representative of the kinds of games that we consider here. Central to the study of these games is the notion of strategy, which roughly speaking, is a way of playing which ensures a certain objective. The main question of interest, when both playing and studying a game, is the problem of finding the 'best' strategy, which secures the victory for the player following it. In this thesis, we consider both one-player games, also called combinatorial puzzles, and two-player games. Examples of combinatorial puzzles include Rubik's cube, Rush-Hour, Sokoban, the 15 puzzle, or peg solitaire. Recently, some types of one-player games in particular have received a strong regain of interest as part of the larger area of reconfiguration problems. The puzzles we described above can all be described in the following way: there is a set of configurations, which represents all the possible states of the game; and the player is allowed to transform a configuration using a prescribed set of moves. Starting from an initial configuration, the goal is to reach a target configuration by a succession of valid moves. Reconfiguration extends this definition to any search problem: the set of configuration becomes the set of solutions to an instance of a given problem, and we ask whether we can transform one given solution to another using only a prescribed set of moves. Hence, in addition to the combinatorial puzzles, reconfiguration problems also include many `games' which are not played by humans anymore but are instead mathematical problems sharing a lot of similarities with combinatorial puzzles. The study of reconfiguration problems has been driven by many different motivations. It has algorithmic applications: it can be seen as a way to adapt a current solution already in place to reach a new one by only making small local changes. It is also connected to other problems such as random sampling, approximate counting or problems coming from statistical physics. It can also be used as a tool for understanding the performance of some heuristic algorithms based on local modifications of solutions such as local search. Two-player games, which are also called combinatorial games, have been studied since the beginning of the twentieth century, with the works of Bouton which were continued with the development of a nice theory by Berlekamp, Conway, and Guy, unifying a certain number of classical games. We focus in this study on perfect strategies (i.e., players always choosing the best possible move), and try to characterize who wins under perfect play for various games. This approach is at the heart of what is called Combinatorial Game Theory. Most of the research in this area is focused on `math games' which are games invented by mathematicians, often with simple rules and almost never played by humans. The main motivation for studying these games comes from the nice, and sometimes unexpected connections these games have with other areas of mathematics, such as for example number theory, automatons, or dynamical systems. In this thesis, we study one- and two-player games. The questions we consider are often related to complexity. Complexity theory consists in trying to classify problems depending on their hardness. By hardness we mean to quantify how much time it would take for a computer to solve the problem. An other aspect of this research consists in investigating structural properties that these games can satisfy. Finally, one of our main tools is the notion of graph, and we use in particular methods and techniques from graph theory to answer the different questions we just mentioned

In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all trees with diameter four. We also give the maximum number of pegs that can be left on such a graph under the restriction that we jump whenever possible.

Dans cette thèse nous étudions trois jeux à objectif compétitif sur les graphes. Les jeux à objectif compétitif proposent une approche dynamique des problèmes d'optimisation discrètes. L'idée générale consiste à associer à un problème d'optimisation (coloration, domination, etc.) un jeu combinatoire partisan de la façon suivante. Deux joueurs construisent tour à tour la structure reliée au problème d'optimisation. L'un d'eux cherche à ce que cette structure soit le plus optimale possible, tandis que l'autre essaye de l'en empêcher. Sous l'hypothèse que les deux joueurs jouent optimalement, la taille de la structure obtenue définit un invariant ludique.Nous commençons par étudier une variante 1-impropre du jeu de coloration, qui est le premier et le plus étudié des jeux à objectif compétitif. Dans ce jeu, les joueurs colorient les sommets d'un graphe de sorte que deux sommets adjacents ne partagent jamais la même couleur. Dans la version 1-impropre, un sommet peut avoir au plus un voisin ayant la même couleur que lui. Nous considérons ensuite le jeu de domination, dans lequel les deux joueurs doivent construire un ensemble dominant, c'est-à-dire un ensemble de sommets du graphe tel que tout autre sommet est adjacent à l'un des membres de cet ensemble. Finalement, nous définissons un nouveau jeu à objectif compétitif, relié au problème de coloration distinguante. Dans ce jeu, il s'agit de construire une coloration qui n'est invariante par aucun des automorphismes du graphe. Nous soulevons plusieurs interrogations stimulantes concernant ce nouveau jeu, notamment sur la caractérisation des graphes ayant un invariant ludique infini, par l'existence d'automorphismes d'ordre deux. / In this thesis, we study three competitive optimization graph games. These games allow a dynamic approach to discrete optimization problems, which is an advantageous alternative way to consider these questions. The global idea consists in defining a combinatorial partisan game, associated to the original optimization problem, like coloring, domination, etc. Two players alternatively build the structure related to the optimization problem. One of them tries to obtain a structure as optimal as possible, whereas his opponent wants to prevent him from doing it. Under the hypothesis that both players play optimally, the size of the obtained structure defines a game invariant of the graph.We start by studying a 1-improper variation of the coloring game, which is the first and the most studied competitive optimization graph game. In this game, the players colors the vertices of a graph, such that two adjacent vertices do not share the same color. In the 1-improper version, we allow a vertex to have at most one neighbor with the same color as it. Then, we study the domination game, in which the players have to build a domination set, that is a sub-set of vertices such that any other vertex is adjacent to one of the vertex in this set. Finally, we define a new game, related to the distinguishing coloring problem. This game is about building a vertex-coloring which is preserved by none of the graph automorphisms. We raise some challenging open questions about this new game, especially concerning the characterization of graphs with infinite game invariant, by the existence of order two automorphisms.

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...