Reconfiguration and combinatorial games
Reconfiguration et jeux combinatoires
Résumé
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
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
Origine : Version validée par le jury (STAR)