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

  • April 2023: Opening postdoc position starting in september 2023
  • March 2023: Miloš Stojaković is visiting us for two weeks.
  • March 2023: Second meeting in Lyon
  • March 2023: Talk about "Avoider-Enforcer games" by Nacim at STACS 2023. The publication is online
  • Feb. 2023: New preprint on HAL - Complexity of Maker-Breaker Games on Edge Sets of Graphs
  • Jan. 2023: Part of the team is at CGT IV conference.
  • Jan. 2023: New published paper - The Maker-Breaker Largest Connected Subgraph game, published in Theoritcal Computer Science
  • Nov. 2023: New preprint on HAL - Incidence, a Scoring Positional Game on Graphs
  • 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 "Incidence, 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