Les jeux positionnels ont été introduits dans les années 1970 pour généraliser des jeux de stratégie comme le Tic-Tac-Toe. Ces jeux sont joués sur un hypergraphe par deux joueurs, appelés Maker et Breaker dans la variante la plus courante. Tour à tour, les joueurs choisissent un sommet de l’hypergraphe. Maker gagne si elle arrive à sélectionner tous les sommets d’une hyperarête, sinon Breaker gagne.
Historiquement, ces jeux ont surtout été étudiés sur des hypergraphes très réguliers issus de jeux sur des grilles ou sur des graphes complets. Ce n’est que récemment que des hypergraphes plus généraux ont été considérés avec une approche algorithmique, soulevant de nombreuses questions.
Dans cette thèse, nous nous intéresserons à cette nouvelle approche sous deux aspects particulièrement. Dans un premier temps, nous chercherons des algorithmes polynomiaux pour résoudre des jeux positionnels joués sur des hypergraphes avec des hyperarêtes de petite taille. Un algorithme polynomial a été prouvé en 2023 par Galliot et al. pour des hyperarêtes de taille 3. Le problème est largement ouvert pour des hyperarêtes de taille 4. Un algorithme polynomial pour ce cas semble hors de portée, aussi nous ajouterons des contraintes sur l’hypergraphe comme par exemple qu’il soit linéaire ou bien étudierons la complexité paramétrée du problème.
Dans un deuxième temps, nous étendrons le modèle des jeux positionnels en ajoutant des contraintes sur les sommets que l’on peut choisir, afin d’avoir un modèle plus large de jeux permettant d’inclure des jeux comme le Puissance 4. L’idée sera alors de comprendre comment les résultats connus sur les jeux positionnels peuvent s’étendre à ce nouveau modèle.