Combinatorial games on graphs
type: Dataset
description: Everyone has ever played a combinatorial game, such as chess or checkers. The interest of mathematicians about this subject is often related to the search of a winning strategy for one of both players. From the game of Nim to chess, the complexity of this search is very variable. In this manuscript, we firstly give a short view of the main stages of the topic, who really started in the beginning of the XXth century. Besides, we emphasize the correlation between combinatorial games and number theory, error-correcting codes, or graph theory. We then investigate some variations of « classical » combinatorial games : Wythoff's game and Dots and Boxes. We detail the strategy and « good » game positions for the first and the second player. We then consider a solitaire variation of a recent two-player game : Clobber. It is a one-player game, where stones are placed on the vertices of a given graph. A move consisting in removing a stone (under some conditions), the goal is to minimize the number of remaining stones at the end. We give structural and algorithmic results about this game played on grids, trees or hypercubes.
issued: 2026-05-05T18:12:11.030066
language: fr
modified: 2026-05-05T18:12:11.030071
contact point: Organization
  fn: CCSD
keyword: algorithmes
keyword: codes-correcteur-derreur
keyword: combinatorial-games
keyword: error-correcting-codes
keyword: graph-theory
keyword: graphes
keyword: infoeu-reposemanticsdoctoralthesis
keyword: jeux-combinatoires
keyword: mathmathematics-math
keyword: theses
landing page: https://theses.hal.science/tel-00097047

Combinatorial games on graphs
type: Distribution
format: HTML
issued: 2026-05-05T18:12:11.031864
modified: 2026-05-05T18:12:11.014691
access URL: https://theses.hal.science/tel-00097047

test_moissonnage_selune
type: Agent