Modélisation de Sowing impartial en Python

Le jeu Sowing impartial, créé par John Conway à la fin du XX^e siècle, a servi de fil conducteur en NSI (première et terminale) durant l’année scolaire 2025-2026. De nombreux concepts du programme de cette spécialité sont en effet illustrés par ce jeu. Voici la règle du jeu :

Chaque joueur, à son tour,

• choisit une case non vide,
• met dans sa main toutes les graines que contenait la case,
• choisit un sens de semis (vers la gauche ou vers la droite),
• sème, une par une, dans le sens choisi, toutes les graines.

Si le semis se termine en dehors du plateau ou dans une case jusque là vide, on a perdu. Le premier qui ne peut plus jouer ainsi, perd le jeu.

Algorithmique

Invariant

En jouant sur un plateau de 8 cases, tel qu’initialement il y a 2 graines par cases, alors la proposition le nombre total de graines est 16 est un invariant. Il sert notamment à détecter la triche, mais aussi, lors de la programmation du jeu en Python, d’éventuels bugs.

Variant

L’existence d’un variant simple et au programme de NSI permettant de prouver la terminaison de ce jeu, est en 2025 un problème ouvert.

Structures de données

Le jeu Sowing impartial est partiellement simulable en SQL, avec deux attributs, le premier étant l’indice de la case (clé primaire), le second étant le nombre de graines contenues dans la case. De même, en Python, il est logique de modéliser un plateau de Sowing par un tableau d’entiers, par exemple ce plateau :

est assez logiquement modélisé par le tableau [1,2,2,0,2,2,2,1]. Cependant, pour pouvoir backtracker (annuler une hypothèse), il peut être nécessaire d’utiliser une structure linéaire comme les tableaux (type list en Python) mais, contrairement à iceux, immuable. La modélisation de Sowing en Python peut donc motiver l’introduction des tuples, qui, de plus, prennent moins de place en mémoire. Le fait que les tuples sont immuables permet, également, de s’en servir comme clés dans un dictionnaire, qui modélisera le graphe du jeu.

Programmation du jeu en Python

Pour simuler le jeu, on a besoin de pouvoir choisir au hasard l’indice d’une case parmi les cases jouables. Aussi le programme commence-t-il par :

from random import choice

et, en Terminale, pour dessiner le graphe du jeu, on fera

from graphviz import Digraph

Règle du jeu

Une case ne peut être jouée que si elle existe (indice à l’intérieur du plateau), elle est non vide, et que la case où tombe la dernière graine est dans le plateau et n’est pas vide :

def jouable(p,i,s):
    n = len(p)
    if i<0:
        return False
    if i>=n:
        return False
    if p[i]==0:
        return False
    if i+s*p[i]<0:
        return False
    if i+s*p[i]>=n:
        return False
    if p[i+s*p[i]]==0:
        return False
    return True

La fonction booléenne est_jouable ci-dessus s’applique à un plateau p (un tuple), un indice i (un entier) et un sens s (un entier égal à 1 ou -1), et dit si la case d’indice i dans le plateau p est jouable en semant dans le sens s. L’ordre dans lequel s’effectuent les tests garantit que chaque expression a un sens au moment où on l’évalue (sinon on aurait quitté la fonction avec un return).

La fonction est_jouable sert à définir une fonction jouables, qui, à un plateau p, associe la liste des indices des cases jouables sur ce plateau :

def jouables(p):
    return [i for i in range(len(p)) if jouable(p,i,-1) or jouable(p,i,1)]

Le jeu est fini lorsque plus aucun indice n’est jouable, donc on cherche à obtenir une telle situation et le plateau est alors considéré comme gagnant :

def gagnant(p):
    return jouables(p)==[]

Semis

Pour effectuer un semis, on a besoin d’un objet mutable, alors on convertit le plateau p en une liste q, que l’on modifie en semant les graines, et que l’on convertit en tuple à la fin du semis. Les graines sont semées une par une :

def jouer(p,i,s):
    assert jouable(p,i,s), "tricheur !"
    q = list(p)
    graines = q[i]
    q[i] = 0
    while graines:
        i += s
        graines -= 1
        q[i] += 1
    return tuple(q)

L’expression graines (le nombre de graines restant à semer) est un variant (grâce à graines -= 1) qui prouve qu’un tour de jeu dure un temps fini (ce n’est pas nécessairement le cas au katro). C’est pour une partie complète du jeu, qu’on ne dispose pas de variant.

Liste d’adjacence

Pour la construction du graphe du jeu mais aussi pour l’affichage des étapes, on aura besoin d’une fonction qui, à un plateau p, associe ses enfants (les plateaux q tels qu’il y a un arc de p vers q dans le graphe orienté du jeu) :

def enfants(p):
    tab = [jouer(p,i,-1) for i in range(len(p)) if jouable(p,i,-1)]
    tab += [jouer(p,i,1) for i in range(len(p)) if jouable(p,i,1)]
    return tab

Cette fois-ci, on renvoie un objet mutable (un tableau) ce qui permet d’utiliser la méthode append pour construire ledit tableau.

Il sera intéressant, pour afficher le déroulé du jeu, de pouvoir calculer l’indice de la case jouée, et le sens du semis, à partir de la connaissance de l’ancien plateau p et du nouveau plateau q :

def indice(p,q):
    return [i for i in range(len(p)) if p[i]>q[i]][0]

def sens(p,q):
    i = indice(p,q)
    if i>0 and p[i-1]<q[i-1]:
        return -1
    if i<len(p)-1 and p[i+1]<q[i+1]:
        return 1

La case jouée est la seule qui soit devenue vide (c’est-à-dire dont l’ancienne valeur soit supérieure à la nouvelle valeur qui est zéro), et le sens est celui selon lequel la case voisine a plus de graines qu’avant.

Distance entre plateaux

Très peu d’élèves de Première se souviennent de la formule donnant la distance euclidienne entre deux points du plan repéré. De plus, des problèmes d’approximation se posent avec les flottants. Aussi a-t-on choisi ici, la distance de Manhattan entre plateaux :

def d(p,q):
    '''distance de Manhattan
    entre deux plateaux p et q.
    p et q sont deux tuples.
    '''
    assert len(p)==len(q)
    return sum([abs(p[i]-q[i]) for i in range(len(p))])

Algorithme des k plus proches voisins

Récapitulons : on sait classer les plateaux entre gagnants et non gagnants, et on dispose d’une distance entre plateaux. Pour aider un joueur à choisir la case à jouer (ce qu’on appelle une stratégie), on considère, quelque peu arbitrairement, qu’on a intérêt à viser un plateau qui a l’air gagnant, c’est-à-dire dont la distance à un (ou plusieurs) plateaux connus pour être gagnants, est petite.

Liste triée par distances

On associe donc, à un plateau p (un tuple d’entiers), une liste tab de tuples dont le premier élément est la distance entre p et l’enfant, et le deuxième élément est l’enfant lui-même. Le tri est alors fait selon les distances :

def voisins(p):
    return sorted([(d(p,q),q) for q in enfants(p)])

Majorité parmi les k plus proches voisins

Un entier positif k étant donné, on regarde l’état (gagnant ou non) de l’enfant médian (c’est l’état majoritaire parmi les k plus proches voisins de p), et on considère que c’est probablement l’état de p :

def major(k,p):
    kppv = voisins(p)[:k]
    etats = [gagnant(q[1]) for q in kppv]
    etats.sort()
    if etats:
        return etats[:k//2][-1]

La stratégie proposée consiste alors à regarder, parmi les enfants du plateau p, lesquels ont l’air (selon kNN) d’être gagnants, et lesquels n’en ont pas l’air. Ensuite, s’il y a au moins un plateau ayant l’air gagnant, on en choisit un au hasard parmi les plateaux ayant l’air gagnants, sinon on choisit au hasard un autre plateau :

def strat(k,p):
    gagnants = []
    perdants = []
    for e in enfants(p):
        if major(k,e):
            gagnants.append(e)
        else:
            perdants.append(e)
    if gagnants:
        return choice(gagnants)
    else:
        return choice(perdants)

Le choix de k est fait empiriquement. Comme il y a souvent moins de 4 enfants, et qu’un ballotage est impossible s’il y a un nombre impair d’électeurs, la valeur de 3 paraît raisonnable. On dispose maintenant des fonctions nécessaires pour simuler une partie de ce jeu, l’IA jouant contre elle-même (comme alpha zero) :

def simulpartie(p):
    k = 3
    plateau = p
    joueur = 0
    nom = ['Sud','Nord']
    nomsens = {-1: 'gauche', 1: 'droite'}
    while not gagnant(plateau):
        print(plateau)
        print('C\'est à',nom[joueur],'de jouer.')
        q = strat(k,plateau)
        print(nom[joueur],'joue la case d\'indice',indice(plateau,q),'vers la',nomsens[sens(plateau,q)],'.')
        plateau = q
        joueur = 1-joueur
        if gagnant(plateau):
            print(plateau)
            print(nom[joueur],'ne pouvant plus semer, a perdu.')

La stratégie choisit un enfant du plateau, et pour l’affichage on calcule la manière dont on peut passer du plateau actuel au plateau suivant, à l’aide des fonctions indice et sens. En fait la stratégie ressemble plutôt à une tactique :

>>> simulpartie((1,2,2,1,1,2,2,1))
(1, 2, 2, 1, 1, 2, 2, 1)
C'est à Sud de jouer.
Sud joue la case d'indice 3 vers la gauche .
(1, 2, 3, 0, 1, 2, 2, 1)
C'est à Nord de jouer.
Nord joue la case d'indice 5 vers la droite .
(1, 2, 3, 0, 1, 0, 3, 2)
C'est à Sud de jouer.
Sud joue la case d'indice 0 vers la droite .
(0, 3, 3, 0, 1, 0, 3, 2)
C'est à Nord de jouer.
Nord joue la case d'indice 1 vers la droite .
(0, 0, 4, 1, 2, 0, 3, 2)
C'est à Sud de jouer.
Sud joue la case d'indice 3 vers la gauche .
(0, 0, 5, 0, 2, 0, 3, 2)
C'est à Nord de jouer.
Nord joue la case d'indice 4 vers la gauche .
(0, 0, 6, 1, 0, 0, 3, 2)
C'est à Sud de jouer.
Sud joue la case d'indice 3 vers la gauche .
(0, 0, 7, 0, 0, 0, 3, 2)
Nord ne pouvant plus semer, a perdu.

L’écriture formatée, n’étant pas au programme, n’a pas été utilisée ici. Dans l’exemple ci-dessus, les joueurs n’ont pas joué au mieux, car sinon Nord aurait gagné (nombre de Grundy nul) :

Pour comparer avec la suite, on reessaye avec un plateau plus simple :

>>> simulpartie((2,2,2,2))
(2, 2, 2, 2)
C'est à Sud de jouer.
Sud joue la case d'indice 3 vers la gauche .
(2, 3, 3, 0)
C'est à Nord de jouer.
Nord joue la case d'indice 0 vers la droite .
(0, 4, 4, 0)
Sud ne pouvant plus semer, a perdu.

Là encore, les joueurs n’ont pas joué au mieux, puisqu’il y a une stratégie gagnante pour Sud, comme on le verra plus bas (le nombre de Grundy est égal à 2).

En Terminale

On peut en fait trouver la stratégie gagnante, en explorant le graphe du jeu. Celui-ci est défini en Terminale par un dictionnaire de listes d’adjacences :

def graphe(p):
    dico = {p: enfants(p)}
    d = {}
    while len(d) != len(dico):
        d = dico.copy()
        for k,v in d.items():
            for q in v:
                if q not in d:
                    dico[q] = enfants(q)
    return dico

On a besoin d’une copie d du dictionnaire parce qu’il est (heureusement) impossible de modifier un objet mutable (ici un dictionnaire) pendant qu’on le parcourt.

Pour obtenir un dessin du graphe, on utilise l’objet Digraph du module graphviz :

def dessin(p):
    digraph = Digraph(format='pdf')
    dico = graphe(p)
    for k,v in dico.items():
        for y in v:
            digraph.edge(str(k),str(y))
    return digraph

La fonction parcourt le dictionnaire des listes d’adjacences, et pour chaque couple (k,y) de plateaux tels que l’arc (k,y) fait partie du graphe, crée l’arc dans le graphe orienté. Ensuite la commande

>>> dessin((2,2,2,2)).render('exple1')

crée le graphe suivant :

où on voit que, si Sud avait joué (3,3,0,2) plutôt que (2,3,3,0) il aurait gagné, quoi que fasse Nord ensuite.