Combinatorial games on graphs

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.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00097047
Author Duchene, Eric
Maintainer CCSD
Last Updated May 5, 2026, 18:12 (UTC)
Created May 5, 2026, 18:12 (UTC)
Identifier tel-00097047
Language fr
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire Leibniz (Leibniz - IMAG) ; Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)
creator Duchene, Eric
date 2006-09-11T00:00:00
harvest_object_id aa5ce470-eedf-41ef-bb7f-207d62fbf22a
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-09-27T00:00:00
set_spec type:THESE