Séminaire

Les jeux combinatoires sont des jeux à exactement deux joueurs, à information totale, sans hasard ni coalition entre les joueurs. S’ils existent depuis très longtemps, on constate très peu de travaux concernant leur résolution dans la littérature précédent la première moitié du 20ème siècle. La première théorie mathématique permettant de bien les comprendre est apparue dans les années 1970 avec les travaux de Conway. Dès lors, une communauté très active est née, et aujourd’hui, les problèmes les plus difficiles concernent les jeux à score (type Othello ou Dots and Boxes) ou encore les jeux en version misère (càd celui qui joue le dernier coup gagne). Par ailleurs, ces jeux présentent l’intérêt d’être un domaine d’application pour de nombreux autres, comme la théorie des graphes, la théorie des nombre, la combinatoire des mots ou encore l’intelligence artificielle. Dans cet exposé, j’aborderai dans un premier temps la jolie théorie de Conway en l’illustrant sur le jeu Domineering. Puis je m’attarderai sur les différentes variantes du jeu de Nim dans les graphes pondérés (règle simple : on enlève du poids et on se déplace sur un sommet voisin), en présentant les principaux résultats de complexité connus sur le sujet.