Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Contrairement aux jeux dits "partisans", la particularité des jeux combinatoires impartiaux est que les deux joueurs ont des options de jeu identiques. Un des attraits de ces jeux aux règles généralement simples, est que les stratégies gagnantes sont parfois très compliquées à trouver, notamment pour les jeux de coloriage impartiaux. Ce travail s'articule principalement autour de l'article de G. Beaulieu, K. Burke et E. Duchêne, intitulé "Impartial Coloring Games". Il se décompose en huit chapitres.
En guise d’introduction, deux jeux combinatoires impartiaux très célèbres sont étudiés : le jeu des bâtonnets et le jeu de Marienbad. Ceux-ci permettent de présenter au lecteur les notions de stratégie et de position gagnantes ainsi que des démarches permettant d’obtenir une telle stratégie. De par sa simplicité, le jeu des bâtonnets est mis en lien avec un jeu joué sur un graphe, ce qui amène au cœur du sujet : les jeux de coloriage impartiaux.
Afin de pouvoir approfondir notre étude, certains outils théoriques relatifs aux notions de calculabilité et de la théorie de la complexité (machine de Turing, fonction calculable par machine de Turing, espaces PSPACE, problèmes décidables par machine de Turing, …) sont rappelés. 
Ensuite, la fonction de Sprague-Grundy et certaines de ses extensions et applications, ainsi que les notions de mex, de jeu de coloriage successif et de valeur de Grundy d’une position d’un jeu de coloriage successif sont étudiées. La valeur de Grundy est alors étendue aux autres jeux combinatoires impartiaux par le biais du graphe des positions d’un jeu acyclique.
Enfin, lorsque le graphe sur lequel se déroule la partie est non connexe, il est naturel de considérer que l’on joue simultanément à plusieurs jeux de coloriage indépendants, sur des graphes connexes. Ceci mène à la notion de somme de jeux, à l’introduction de la somme de Nim et à un résultat très important en théorie des jeux combinatoires : le théorème de Sprague-Grundy. 
Les définitions et résultats obtenus précédemment sont alors appliqués à divers jeux de coloriage impartiaux tels que les k-coloriages propres, coloriages orientés, faibles, 2-distants et séquentiels. Entre autres, pour les jeux précités, il est montré que déterminer si une position de ces jeux est gagnante est un problème PSPACE-complet.

Jeux --- Sprague-Grundy --- Coloriage --- Graphe --- Stratégie --- Physique, chimie, mathématiques & sciences de la terre > Mathématiques