Games and graphs (GAG)

Type de projet : ANR
Dates du contrat : 2015 - 2019
Équipe(s) : GOAL
Responsable scientifique LIRIS : Eric Duchene
Partenaire(s) : Laboratoire d'Informatique de Grenoble, Laboratoire d'Analyse et d'Architecture des Systèmes, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes, Laboratoire Bordelais de Recherche en Informatique, Institut Fourier
URL du projet : http://liris.cnrs.fr/~gag/

Description :
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.).