Les jeux suivants sont basés sur des colorations de graphes :

• la Pipopipette
• hex
• « gale » ou « bridg-it » ou « connectia »
• le jeu de circuit de Shannon, une généralisation de « gale »
• sprouts

Le graphe d’un jeu combinatoire est formé

• de sommets, représentant les états successifs du jeu ;
• d’arêtes (flèches), représentant les mouvements du jeu

L’ensemble des arêtes est la règle du jeu ; le graphe du jeu est très utile pour analyser le jeu et notamment pour trouver une stratégie gagnante : On se sert du graphe pour calculer le nimber du jeu, et le théorème de Sprague-Grundy fournit un algorithme simple pour repérer les cases gagnantes : Ce sont celles dont le nimber est nul... Pour un jeu impartial, le graphe est équivalent à un produit cartésien de jeux de Nim. Ce qui donne une grande importance à ces jeux.

Voici des versions cliquables de ces jeux : On clique sur l’arête que l’on veut voir parcourir et le pion bouge tout seul le long de l’arête :

Jeu de la soustraction	Soustrais un carré

Cela permet des variantes où un joueur peut avoir à passer son tour selon le coup qu’il a joué :

Jeu de la soustraction	Soustrais un carré

Autre possibilité : Modéliser le jeu de Nim (ou plutôt, son graphe) par un site internet...

Le jeu de Wythoff utilise l’échiquier comme graphe d’un jeu de Nim à deux tas, l’abscisse de la dame représentant la taille du premier tas, et son ordonnée représentant la taille du second tas. Le jeu de Welter en est la version monodimensionnelle : Par exemple un jeu de Nim avec des tas de tailles respectives 7, 2 et 4 (regarder les abscisses des pions) peut se jouer sur cet échiquier :

La règle du jeu est que chaque joueur peut bouger vers la gauche, d’autant de cases qu’il veut, un pion de son choix ; le premier joueur qui ne peut plus bouger (parce que tous les pions sont collés à gauche) perd.

Jouer à un jeu de Nim, c’est donc bouger un pion sur un graphe (celui du jeu), et il est possible de trouver la stratégie gagnante en marquant comme gagnantes ou perdantes les cases du jeu, comme l’on fait des élèves pendant la semaine des maths 2016. Voici le jeu de Nim sur trois tas de 2, sur son graphe à tester en ligne en cliquant dessus) :

Berlekamp, Conway et Guy ont trouvé que dans le jeu de Welter, on pouvait mettre les pions sur une seule ligne, comme le montre cette figure extraite de leur ouvrage :

Le jeu de Nim classique est repréenté sur la gauche, avec des tas de tailles respectives 7, 3, 3 et 5 (des pions du jeu de dames superposés) alors que la version montrée à droite n’utilise que 4 pions mais posés sur une ligne du damier. Les cases de cette ligne forment un graphe de jeu de Nim à un tas, avec la convention que chacune d’entre elles est « reliée » à toutes celles qui sont à sa gauche.

Voici le jeu de Nim précédent (3 tas de 2) sur le graphe de Welter (on peut le tester en ligne en cliquant dessus) :

Comme on le voit, le graphe de Welter du jeu est nettement moins complexe que le graphe du jeu lui-même ; ceci permet de créer des jeux combinatoires très complexes avec les graphes de la fête de la science. Par exemple, en, disposant 3 pions sur les sommets en bas à gauche de ce graphe :

Le but du jeu est d’amener les trois pions en haut du graphe, et le gagnant est celui qui bouge le dernier pion.

Comme les sommets sont petits (et nombreux), on peut imposer une règle supplémentaire, selon laquelle on n’a pas le droit de mettre le pion sur une case déjà occupée (Berlekamp, Conway et Guy appellent ce genre de Nim un antonim). Voici la version jouable en ligne d’un tel jeu de Nim sur graphe, à 3 pions (cliquer l’image pour jouer) :

Et la version « soustrais un carré » :

Ici le but du jeu est d’amener les trois pions sur les trois dernières cases, un pion par case ; et le premier qui ne peut plus bouger de pion a perdu.

On peut, au contraire, vouloir que plusieurs pions puissent être sur une même case (Berlekamp, Conway et Guy parlent de synonim), et même imposer comme condition de sortie d’une case, que celle-ci soit suffisamment peuplée : On obtient alors un réseau de Petri qui n’était, jusqu’ici, pas considéré comme un jeu (mais il n’est pas déterministe).

Un exemple de jeu combinatoire relativement simple est celui dit « du fer à cheval » :

Et un jeu similaire, recommandé par Édouard Lucas (pour les enfants) parce que plus complexe donc plus intéressant ; là aussi il s’agit d’un plateau de jeu à manipuler à deux, en ligne :

Le jeu suivant n’était pas connu d’Édouard Lucas puisqu’il a été inventé en 2016 (le jeu, pas Édouard Lucas) ; sa créatrice étant âgée de 6 ans, a donc dessiné un graphe à 6 ans, ce qui tend à montrer qu’on peut percevoir les lignes à cet âge. Le jeu est trop récent pour qu’on en connaisse une stratégie gagnante :

Pour jouer, cliquer sur l’image ci-dessus ; on joue à deux joueurs sur une seule tablette, chacun son tour. Un plateau de jeu plastifié sera préparé pour la fête de la science 2016.