Description du projet scientifique

Dans le domaine de la combinatoire, les jeux à deux joueurs font partie des problèmes de très haute complexité. On le conçoit aisément dès lors qu'il s'agit de répondre à la question: à chaque tour de jeu, quelle que soit la stratégie de mon adversaire, il existe un coup qui m'assure la victoire. Cette difficulté associée à l'attrait naturel du sujet leur a conféré un intérêt d'autant plus grand et la construction d'une théorie dédiée aujourd'hui encore en plein construction. Précisons toutefois que la théorie des jeux combinatoires est très différente de la théorie des jeux dite "économique" ou encore des jeux infinis et stochastiques. Au contraire de ces derniers, les jeux combinatoires ne constituent pas encore un domaine de recherche bien établi en France, alors que la théorie se développe fortement à l'étranger, en particulier en Amérique du Nord.

Dans ce projet, nous choisissons de mettre la théorie des graphes au service des jeux combinatoires: étant donné un jeu, il est facile de le représenter par un graphe orienté (le graphe de jeu), où les sommets codent les positions de jeu, et les arêtes correspondent aux coups autorisés. Dans le contexte des jeux impartiaux à 2 joueurs, trouver une stratégie gagnante est équivalent à trouver un noyau (ensemble stable et absorbant) dans le graphe de jeu. Cependant, trouver un noyau dans un graphe est un problème difficile en général. Par ailleurs, il existe certains types de jeux combinatoires (misère,partisans) pour lesquels la théorie des graphes n'a jamais été considérée comme un véritable outil. Notre objectif est d'établir une boite à outils en théorie des graphes pour aider à une résolution globale des jeux combinatoires, et en particulier de certains des problèmes les plus ardus du domaine:

  • les jeux misère, qui sont considérés aujourd'hui comme le sujet phare du domaine, et en particulier les jeux octaux/hexadécimaux misère. Des résultats généraux sont attendus, tels qu'un équivalent de la théorie de Sprague-Grundy pour la somme de jeux misère.
  • les jeux de réécriture sur les graphes, et en particulier les jeux dérivés de problèmes combinatoires classiques comme la coloration ou la domination.

Un autre apport original de notre projet est l'utilisation de la théorie des jeux combinatoires pour le calcul de paramètres d'optimisation de graphes (nombre chromatique ou de domination ludique par ex.).

 

Project description

Two-player games certainly belong to the most complex problems in the field of combinatorics. One can indeed figure out this complexity when trying to answer the following question: whatever the strategy of my opponent is, does there exist a move that would lead me to victory? This hardness as well as the natural appeal of games made their interest grow, and led to the creation of a dedicated theory which is still under construction today. For a better understanding of our project topic, we point out that combinatorial game theory (CGT) is very different from the so-called "economic" game theory introduced by Von Neumann and Morgenstern, which allows hidden information, more than 2 players, negotiations or coalitions between the players.

In this project, we choose to put graph theory in the heart of the combinatorial game problematic. Given any game, it is indeed easy to represent it by a digraph (which we call the game graph), where the vertices are the game positions, and the edges are the allowed moves. In the context of impartial 2-player games, finding a winning strategy is equivalent to finding a kernel (stable and absorbing set) in the game graph. However, the problem of finding a kernel is hard in general; moreover, there are some types of combinatorial games (misère, partisan) for which graph theory has never been considered as a tool. Our goal is thus to provide a graph theoretical toolbox to help in solving games in a more general context, including most of the major issues in combinatorial games. In particular, we plan to have applications of this toolbox in the following “key” problems:
- misère games, which are considered as the current hot topic of the domain. General results are also expected, like an equivalent of the Sprague-Grundy theory for misère impartial games.
- rewrite games on graphs, and in particular octal games or removal games on heaps.
- study of the link between CGT and some graph optimization parameters (e.g. game chromatic number, game domination number...), that are currently widely studied problems.
Analysis of game complexity for computing winning strategies and research of efficient algorithms are also strong objectives of this project.