Two-player Domino games

Benjamin Hellouin de Menibus (1) , Rémi Pallen (2)

1 GALaC - Graphes, Algorithmes et Combinatoire - LISN
2 ENS Paris Saclay - Ecole Normale Supérieure Paris-Saclay

We introduce a 2-player game played on an infinite grid, initially empty, where each player in turn chooses a vertex and colours it. The first player aims to create some pattern from a target set, while the second player aims to prevent it. We study the problem of deciding which player wins, and prove that it is undecidable. We also consider a variant where the turn order is not alternating but given by a balanced word, and we characterise the decidable and undecidable cases.

Mots clés: Game; Tiling; Pattern; Computability; Symbolic dynamics; Subshift; Tic-tac-toe

Domaines: Informatique [cs]; Mathématiques [math]

Benjamin Hellouin de Menibus, Rémi Pallen. Two-player Domino games. 2023. ⟨hal-04265421⟩