Author name cluster

Eric Duchêne

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

TCS Journal 2024 Journal Article

Bipartite instances of INFLUENCE

Eric Duchêne
Nacim Oijid
Aline Parreau

The game Influence is a scoring combinatorial game that has been introduced in 2021 by Duchêne et al. [5]. It is a good representative of Milnor's universe of scoring games, i. e. games where it is never interesting for a player to miss their turn. New general results are first given for this universe, by transposing the notions of mean and temperature derived from non-scoring combinatorial games. Such results are then applied to Influence to refine the case of unions of segments started by Duchêne et al. [5]. The computational complexity of the score of the game is also solved and proved to be PSPACE-complete. We finally focus on some specific cases of Influence when the graph is bipartite, by giving explicit strategies and bounds on the optimal score on structures like grids, hypercubes or tori.

Details DOI

TCS Journal 2021 Journal Article

influence: A partizan scoring game on graphs

Eric Duchêne
Stéphane Gonzalez
Aline Parreau
Eric Rémila
Philippe Solal

We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor's universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.

Details DOI

TCS Journal 2018 Journal Article

The switch operators and push-the-button games: A sequential compound over rulesets

Eric Duchêne
Marc Heinrich
Urban Larsson
Aline Parreau

We study operators that combine combinatorial games. This field was initiated by Sprague–Grundy (1930s), Milnor (1950s) and Berlekamp–Conway–Guy (1970–80s) via the now classical disjunctive sum operator on (abstract) games. The new class consists in operators for rulesets, dubbed the switch-operators. The ordered pair of rulesets ( R 1, R 2 ) is compatible if, given any position in R 1, there is a description of how to move in R 2. Given compatible ( R 1, R 2 ), we build the push-the-button game R 1 ⊚ R 2, where players start by playing according to the rules R 1, but at some point during play, one of the players must switch the rules to R 2, by pushing the button ‘⊚’. Thus, the game ends according to the terminal condition of ruleset R 2. We study the pairwise combinations of the classical rulesets Nim, Wythoff and Euclid. In addition, we prove that standard periodicity results for Subtraction games transfer to this setting, and we give partial results for a variation of Domineering, where R 1 is the game where the players put the domino tiles horizontally and R 2 the game where they play vertically (thus generalizing the octal game 0. 07).

Details DOI

I&C Journal 2017 Journal Article

Deciding game invariance

Eric Duchêne
Aline Parreau
Michel Rigo

In a previous paper, Duchêne and Rigo introduced the notion of invariance for take-away games on heaps. Roughly speaking, these are games whose rulesets do not depend on the position. Given a sequence S of positive tuples of integers, the question of whether there exists an invariant game having S as set of P -positions is relevant. In particular, it was recently proved by Larsson et al. that if S is a pair of complementary Beatty sequences, then the answer to this question is always positive. In this paper, we show that for a fairly large set of sequences (expressed by infinite words), the answer to this question is decidable.

Details DOI

TCS Journal 2014 Journal Article

Vertex Nim played on graphs

Eric Duchêne
Gabriel Renault

Given a graph G with positive integer weights on the vertices, and a token placed on some current vertex u, two players alternately remove a positive integer weight from u and then move the token to a new current vertex adjacent to u. When the weight of a vertex is set to 0, it is removed and its neighborhood becomes a clique. The player making the last move wins. This adaptation of Nim on graphs is called Vertexnim, and slightly differs from the game Vertex NimG introduced by Stockman in 2004. Vertexnim can be played on both directed or undirected graphs. In this paper, we study the complexity of deciding whether a given game position of Vertexnim is winning for the first or second player. In particular, we show that for undirected graphs, this problem can be solved in quadratic time. Our algorithm is also available for the game Vertex NimG, thus improving Stockmanʼs exptime algorithm. In the directed case, we are able to compute the winning strategy in polynomial time for several instances, including circuits or digraphs with self loops.

Details DOI

TCS Journal 2010 Journal Article

Invariant games

Eric Duchêne
Michel Rigo

In the context of 2-player removal games, we define the notion of invariant game for which each allowed move is independent of the position it is played from. We present a family of invariant games which are variations of Wythoff’s game. The set of P -positions of these games is given by a pair of complementary Beatty sequences related to the irrational quadratic number α k = ( 1; 1, k ¯ ). We also provide a recursive characterization of this set.

Details DOI