Jeux combinatoires: théorie générale et exemples de résolution

par Éric Duchêne (LIRIS, Univ. Lyon 1)

mardi 7 févr. 2017, 10:45 → 11:45 Europe/Paris

Fokko du Cloux (ICJ)

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 ou la théorie des nombres. Dans cet exposé, j'aborderai dans un premier temps la jolie théorie de Conway où chaque jeu combinatoire se voit attribuer une valeur (dyadique, infinitésimale, ou autre) qui correspond à sa classe d'équivalence selon la relation "somme de jeux". Puis je m'attarderai sur différents exemples de résolution de jeux (certaines très actuelles, d'autres moins) faisant intervenir des outils variés comme les systèmes de numération.