Jeux et graphes – GAG

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 création d'une théorie dédiée est aujourd'hui encore en pleine construction. Précisons
toutefois que la théorie des jeux combinatoires est très différente de la théorie des jeux dits "économiques" 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.
Récemment, on constate une activité nationale un peu plus présente sur le sujet : trois thèses de doctorat soutenues ou
en cours depuis 2006 (LaBRI, Institut Fourier), des mémoires de Master 2R (LaBRI, LIRIS), des premiers travaux
communs avec des spécialistes internationaux du domaine, et une première collaboration entre nos équipes autour d'un
projet CNRS PEPS. Comparée à celle concernant les jeux économiques ou stochastiques, cette activité reste toutefois
relativement faible. Ce projet ANR constitue pour nous l'opportunité d'étendre l'intérêt national porté au sujet, et
également d'amplifier la portée des résultats obtenus dans le cadre du projet tremplin PEPS sur les jeux misère. Une
candidature JCJC est aussi une opportunité pour le coordinateur de rassembler presque toute la communauté nationale
des jeunes chercheurs en jeux combinatoires, avec le soutien de trois chercheurs confirmés du domaine.
Notre réussite passera par des résultats forts sur des problématiques reconnues, l'introduction d'une nouvelle approche
de résolution, la collaboration avec les meilleurs experts du domaine, et l'organisation d'une conférence internationale.
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 équivaut à 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 ; des résultats généraux sont
attendus, tels qu'un équivalent de la théorie de Sprague-Grundy pour la somme de jeux impartiaux misère,
- les jeux de réécriture sur les graphes, et en particulier les jeux octaux ou les jeux de suppression sur des tas.
- étude du lien qui existe entre jeux combinatoires et certains paramètres d'optimisation de graphes (nombre chromatique
ou nombre de domination ludiques par ex.), qui sont des problèmes fortement étudiés actuellement.
La complexité de calcul d'une stratégie gagnante et la recherche d'algorithmes performants (exacts ou approchés) feront également partie des objectifs forts de ce projet.