Sprouts

Le Sprouts (germe en anglais) est un jeu à deux joueurs du type morpion, inventé en 1967 à l'Université de Cambridge par les mathématiciens John Horton Conway et Michael Paterson.

Règles du jeu

Principe

Sprouts à n=2 points

Ce jeu se joue à deux joueurs avec un stylo et une feuille de papier. Au départ il y a n points sur la feuille. Chaque joueur, à tour de rôle, relie deux points existants par une ligne et ajoute un nouveau point sur cette ligne. Deux contraintes doivent être respectées : les lignes ne peuvent se croiser, et un point ne peut être relié à plus de trois lignes. Ce jeu est également nommé jeu des pousses, car les figures représentés ressemblent à des pousses d'arbres.

But du jeu

Dans la version normale du jeu, le perdant est celui qui ne peut plus jouer sans enfreindre les deux contraintes. Il existe également une version misère, où celui qui ne peut plus jouer est cette fois le gagnant.

Nombre de coups

Le nombre de points tracés sur la feuille augmente à chaque coup, et on peut donc se demander si la partie se termine en un nombre fini de coups. En fait, on peut montrer qu'une partie se termine au maximum avec 3n-1 coups et au minimum avec 2n coups^[1].

La figure ci-contre donne un exemple de partie, avec 2 points initialement. Le point ajouté par chaque joueur est marqué en rouge. Après 4 coups, la partie est terminée, et c'est le joueur qui avait joué en premier qui est donc le perdant, puisqu'il ne peut plus jouer.

Stratégie gagnante

Pour un certain nombre de points de départ donné, l'un des deux joueurs possède une stratégie gagnante. L'analyse du jeu consiste donc notamment à déterminer lequel des deux joueurs possède une stratégie gagnante : soit celui qui joue en premier, soit celui qui joue en second. Cette analyse été réalisée à la main jusqu'à 6 points de départ.

Puis, en 1990, David Applegate, Guy Jacobson et Daniel Sleator ont calculé par ordinateur quel joueur a une stratégie gagnante jusqu'à 11 points de départ^[2]. Ce résultat a ensuite été étendu en 2007 par Julien Lemoine et Simon Viennot jusqu'à 32 points de départ, plus cinq valeurs entre 34 et 47 points de départ^[3].

Dans le cas de la version misère, l'analyse du jeu est plus difficile. En 1990, David Applegate, Guy Jacobson, et Daniel Sleator ont calculé la stratégie gagnante jusqu'à 9 points de départ. Ce résultat a été étendu en 2008 par Josh Purinton et Roman Khorkov jusqu'à 16 points de départ.

Références

1. ↑ Philippe Boulanger Sprouts en herbe Dossier Pour la Science N°59 - avril - juin 2008
2. ↑ D. Applegate, G. Jacobson, D. Sleator Computer Analysis of Sprouts technical report, 1991
3. ↑ Jean-Paul Delahaye Le jeu des pousses Pour la Science N°371 - septembre 2008

Liens externes

• (en) Joueur au Sprouts en ligne !
• (en) avancées récentes grâce a une recherche par ordinateur guidée