Sprouts

Sprouts est un jeu de stratégie sur papier pour deux joueurs, inventé par les mathématiciens John Conway et Michael Paterson. Les joueurs dessinent à tour de rôle des courbes entre des points et ajoutent de nouveaux points sur ces courbes. Chaque point peut être relié à trois lignes au maximum, et les lignes ne peuvent pas se croiser. Le dernier joueur capable d’effectuer un coup valide remporte la partie (en mode normal) ou la perd (en mode « misère »). Malgré son matériel très simple — juste un stylo et du papier —, Sprouts donne lieu à des situations stratégiques remarquablement complexes.

Règles

1. Commencez par dessiner un petit nombre de points sur une feuille de papier — généralement entre 2 et 6.
2. Les joueurs jouent à tour de rôle.
3. À chaque tour, un joueur trace une courbe reliant deux points (ou un point à lui-même, formant ainsi une boucle).
4. La courbe ne doit croiser aucune courbe existante ni passer par aucun point existant.
5. Après avoir tracé la courbe, le joueur ajoute un nouveau point quelque part sur la courbe qu’il vient de tracer.
6. Chaque point peut être relié à trois courbes (lignes) au maximum. Un point comportant trois connexions est « mort » et ne peut plus être utilisé.
7. Le joueur qui effectue le dernier coup valide gagne (règle habituelle).

Stratégies

• Compter les vies : Chaque point commence avec 3 « vies » (connexions possibles). Tracer une ligne utilise une vie à chaque extrémité, et le nouveau point naît avec une vie déjà utilisée (la courbe le traverse), ce qui lui laisse 2 vies. Suivez le nombre total de vies restantes pour estimer le nombre de coups restants.
• Durée de la partie : une partie commençant avec N points dure toujours entre 2N et 3N-1 coups. Savoir cela permet de déterminer si vous souhaitez prolonger ou raccourcir la partie.
• Régions : les courbes divisent la feuille en régions. Les points situés dans une même région peuvent se connecter, mais ceux situés dans des régions différentes ne le peuvent pas (puisque les courbes ne peuvent pas se croiser). Il est essentiel de créer des régions qui isolent les options de votre adversaire.
• Contrôle des limites : essayez de ne laisser à votre adversaire que des points morts dans ses régions accessibles.
• Pharisiens et survivants : un « pharisien » est un point qui ne peut plus être utilisé. Gardez une trace des points qui sont vivants et du nombre de connexions qu’il leur reste.
• Parité : comme vous savez que la durée de la partie est limitée, vous pouvez parfois déterminer qui effectuera le dernier coup et jouer en conséquence.

Le jeu « Sprouts » a été inventé le 21 février 1967 au département de mathématiques de l’université de Cambridge. John Horton Conway et Michael Stewart Paterson prenaient le thé de l’après-midi lorsqu’ils ont commencé à tester ce jeu. Conway l’a par la suite décrit comme « l’un des meilleurs jeux issus de Cambridge depuis l’invention du cricket ».

Le jeu a immédiatement retenu l’attention des mathématiciens. Martin Gardner a présenté Sprouts dans sa rubrique « Mathematical Games » du magazine Scientific American en juillet 1967, le faisant ainsi connaître à un public international. Gardner rapporta que le jeu avait « fait naître » un engouement modéré parmi les mathématiciens et les informaticiens, les joueurs découvrant que ce qui semblait n'être qu'un simple jeu de gribouillage recelait une profondeur stratégique surprenante.

L’analyse mathématique de Sprouts est extrêmement complexe. Si les parties commençant avec peu de points (1 à 7) ont été entièrement analysées à la main et par ordinateur, la difficulté augmente rapidement. Le jeu est lié à la théorie des graphes et à la topologie — plus précisément, il peut être analysé à l’aide de concepts issus de la théorie des graphes planaires, puisque le jeu se déroule sur une surface où les courbes ne peuvent pas se croiser. L’analyse informatique réalisée par David Applegate, Guy Jacobson et Daniel Sleator dans les années 1990 a étendu les résultats connus aux parties commençant avec jusqu’à 11 points.

Une question ouverte importante consiste à savoir si le premier joueur gagne ou perd pour chaque nombre initial de points. L’analyse informatique a mis en évidence une tendance : le premier joueur perd lorsqu’il commence avec 0, 1 ou 2 points, mais gagne avec 3, 4 ou 5 points. La tendance semble indiquer que le premier joueur perd lorsque le nombre de points est égal à 0, 1 ou 2 modulo 6, mais cette conjecture reste à prouver pour toutes les positions de départ.

Conway, l’un des mathématiciens les plus célèbres du XXe siècle, a ensuite créé de nombreux autres jeux mathématiques et a apporté des contributions fondamentales à la théorie des groupes, à la théorie des nombres et à la théorie du codage. Il est décédé en 2020, mais « Sprouts » reste l’une de ses créations les plus accessibles et les plus appréciées.