Cette thèse explore des problématiques liées aux jeux. Nous nous intéressons en particulier aux jeux sans information cachée et sans aléa, à un ou deux joueurs.

    Les jeux à un joueur que nous considérons peuvent ê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 configuration cible donnée à partir d'une configuration initiale. Les problèmes pouvant être définis avec ce formalisme sont appelés problèmes de reconfiguration, et incluent à la fois certains puzzles combinatoires tels que le Rubik's cube ou Rush-hour, mais également des transformations sur des problèmes de recherche pour lesquels l'ensemble des configurations est l'ensemble des solutions d'une instance d'un problème donné.

    Les jeux à deux joueurs qui nous intéressent sont appelés jeux combinatoires. Pour ces jeux là, nous considérons le cas où les joueurs jouent parfaitement, ce qui revient à tenter de caractériser lequel des joueurs possède une stratégie gagnante (qui lui assure la victoire quels que soient les coups de l'adversaire).

    Dans cette thèse, nous étudions ainsi des jeux à un et deux joueurs, et tout particulièrement la complexité de ceux-ci, c'est-à-dire évaluer à quel point il est difficile (d'un point de vue algorithmique) de calculer une stratégie gagnante. Plus précisément, nous étudions la reconfiguration de deux problèmes sur les graphes : les couplages parfaits et la coloration de graphes, pour lesquels nous donnons à la fois des preuves de difficulté à l'aide de réductions, et des algorithmes polynomiaux dans des sous-cas spécifiques. Nous nous intéressons aussi à deux problèmes en lien avec la reconfiguration : la génération aléatoire de coloration, via l'application de transformations aléatoires à une coloration donnée, et des algorithmes de coloration online. Enfin, la dernière partie de ces travaux porte sur les jeux combinatoires, pour lesquels nous nous concentrons plutôt sur des aspects structurels. Nous considérons tout d'abord les propriétés d'une famille de jeux particulière, les jeux de soustractions partisans, et étudions ensuite une construction générale pour combiner plusieurs règles de jeux, et en créer de nouvelles