The project ANR P-GASE is a young researcher project funded by the French Agence Nationale de la Recherche and is running from January 2022 until December 2025. It is coordinated by Aline Parreau from LIRIS Laboratory (Lyon, France).

Abstract

Positional games are two-player finite perfect information games. They are described by a finite set of elements and subsets of these elements which are called the winning sets, the whole being represented by an hypergraph. The players alternatively claim elements and try to fill a winning set first, or to prevent their opponent from doing so before them. The famous Tic-Tac-Toe game belongs to this class.

If both players play optimally, one of them always has a winning strategy or both can guarantee a draw. However, determining which player wins and what his strategy is is mostly a PSPACE-hard problem. Several recent studies show a growing interest in these games, raising many questions around their resolution. We want to refine the study of their complexity and find effective strategies for the players. Indeed, most studies on these games actually focus on asymptotic studies and the balancing of these games. Moreover, these games are played on very regular structures, which limits the study of algorithmic complexity.

We propose a new algorithmic and combinatorial approach to these games, by considering on the one hand structures for the hypergraph of the game coming from graph theory problems and on the other hand by adapting combinatorial game theory tools to positional games. In particular, we will study the influence of several parameters on this resolution such as the role of the players, the length of the game or the structure of the game hypergraph. Finally, we will extend the framework of positional games to include notions that are not currently taken into account, such as the score.

News

  • Oct. 2022: Nacim and Valentin have proved that solving Avoider-Enforcer games is PSPACE-complete ! Preprint on HAL
  • Sept. 2022: The website is online !
  • Aug. 2022: Talk about "Incidenc e, a scoring positional game" by Nacim at CSGT 2022
  • July 2022: Talk on "Maker-Maker domination game" at ICGT 2022 by Nacim
  • June 2022: Preprint on HAL - Bipartite instances of Influence
  • June-Aug 2022: Internship of Mathéo Joseph on the game 7-in-a-row
  • May 2022: Talk about "Une introduction aux jeux positionnels... ou comment les chercheurs jouent au Morpion" by Aline at the LIMOS Seminar
  • May 2022: Talk about "Incidence, a scoring positional game" by Nacim at GRASTA 2022
  • Feb. 2022: First meeting in Lyon
  • Jan. 2022: Talk about "Smash and grab: a new scoring game on graphs" by Eric and Aline at the Virtual Game talk seminar
  • Jan. 2022: Official start of the project

In link with the project