Positional games: algorithms and strategies (P-GASE)

Type of project: ANR
Contract dates: 2022 - 2025
Équipe(s): GOAL
Responsable scientifique LIRIS: Aline Parreau

Description:
Les jeux positionnels sont des jeux à deux joueurs, finis et à information complète. Ils sont décrits par un ensemble fini d'éléments et des sous-ensembles de ces éléments qui sont les ensembles gagnants, le tout étant représenté sous forme d'un hypergraphe. Les joueurs prennent chacun leur tour un élément et essaient de remplir en premier un ensemble gagnant, ou bien d'empêcher leur adversaire de le faire avant eux. Le célèbre jeu du morpion appartient à cette classe. Si les deux joueurs jouent optimalement, l’un d’eux a toujours une stratégie gagnante ou bien les deux peuvent garantir un match nul. Cependant, déterminer quel joueur gagne et quelle est sa stratégie est la plupart du temps un problème PSPACE-difficile. Plusieurs études récentes montrent un intérêt grandissant pour ces jeux, soulevant de nombreuses questions autour de leur résolution. Nous voulons affiner l’étude de leur complexité et trouver des stratégies effectives pour les joueurs. En effet, à l'heure actuelle, la plupart des études sur ces jeux portent sur des études asymptotiques et l'équilibrage de ces jeux. Par ailleurs, ces jeux sont joués sur des structures très régulières, ce qui limite l'étude de complexité algorithmique. Nous proposons une nouvelle approche algorithmique et combinatoire de ces jeux, en considérant d’une part des structures pour l’hypergraphe du jeu issues de problématiques de théorie des graphes et d’autre part en adaptant les outils de théorie des jeux combinatoires aux jeux positionnels. Nous étudierons en particulier l'influence de plusieurs paramètres sur cette résolution comme le rôle des joueurs, la longueur de la partie ou la structure de l'hypergraphe de jeu. Enfin, nous étendrons le cadre des jeux positionnels afin d'englober des notions qui ne sont pour l'instant pas prise en compte, comme par exemple le score.