Positional games: algorithms and strategies (P-GASE)
Type of project: ANRContract 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.