Octal games are combinatorial games played on heaps of counters: two players alternate removing counters from a heap, and may split it into two nonempty heaps, under conditions expressed in the form of an octal code. The main problem is deciding which player wins (by playing the last legal move) from a heap of a given size. In order to answer to this question, the most used method consists in finding regularities in the sequence of its Grundy values (equivalence classes for games) on heaps of increasing sizes.
We propose a generalization of those games on graphs: the players remove connected subgraphs, and may disconnect the graph, under conditions similar to those of octal games. This definition includes several vertex deletion games, such as Arc-Kayles. We focus our study on subtraction games, a subfamily of octal games where the players cannot disconnect the graph.
This talk will start with an introduction to the Sprague-Grundy Theory used to study impartial combinatorial games, with a focus on octal games. I will then show how we generalized this family to play it on graphs, and how to study regularity in this context. Finally, I will focus on subtraction games on graphs, and present several of our results, from general ones (PSPACE-completeness, ultimate periodicity) to specific families of games on families of graphs. Our study is mostly focused on subdivided stars, which are already difficult to tackle: the classical game Arc-Kayles is open in the family of subdivided stars, even with only three paths with one of length 1! We determined polynomial-time algorithms which allow to decide the winner of the game 0.33 on subdivided stars and bistars.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne