Sprouts
Le Sprouts (germes, ou choux de Bruxelles, en anglais) est un jeu de stratégie à deux joueurs, inventé en 1967 à l'Université de Cambridge par les mathématiciens John Horton Conway et Michael Paterson.
Il est appelé jeu de la taupe du Pérou aux pages 58 et 59 dans le 2e manuel des Castors Juniors[1].
Règles du jeu
[modifier | modifier le code]Principe
[modifier | modifier le code]
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 un point à un autre 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ées ressemblent à des pousses d'arbres.
But du jeu
[modifier | modifier le code]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
[modifier | modifier le code]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[2].
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
[modifier | modifier le code]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 a é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[3]. 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[4].
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
[modifier | modifier le code]- Yvan Delporte (trad. de l'anglais), 2e manuel des Castors Juniors, Paris, Hachette, , 189 p. (ISBN 2-01-001971-7).
- Philippe Boulanger, « Sprouts en herbe », Dossier Pour la Science, avril - juin 2008 (lire en ligne).
- D. Applegate, G. Jacobson, D. Sleator Computer Analysis of Sprouts technical report, 1991
- Jean-Paul Delahaye, « Le jeu des pousses », Pour la Science, (lire en ligne).
