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

In link with the project