Modélisation Python du jeu de Welter

Le jeu de Welter

C’est dans le cadre de recherches sur les algèbres de Kac-Moody en physique théorique, que dans les années 1950, P.C. Welter d’une part, Mikio Sato de l’autre, ont inventé le jeu étudié ici. Le jeu se joue sur un plateau similaire à celui de Sowing, avec des cases alignées. Des pions ou des jetons sont posés sur le plateau de jeu, de telle manière qu’il n’y ait jamais plus d’un pion par case.

Un tour de jeu consiste à déplacer un pion vers la gauche, d’au moins une case, et vers une case vide (sinon il y aurait plusieurs pions dans une même case, ce qui est interdit par la règle du jeu). Par exemple à partir de la situation ci-dessus il y a 8 possibilités dont celle-ci :

(le pion le plus dextre est parti dans la troisième case)

Le coup ci-dessus est d’ailleurs un mauvais coup, parce que l’adversaire peut alors jouer à son tour le pion le plus dextre et arriver à cette situation bloquante :

En effet, dès que tous les pions sont tassés à gauche comme ci-dessus, le jeu est terminé, et le premier qui ne peut plus bouger aucun pion a perdu le jeu.

Ce jeu est praticable dès lors qu’on sait

• distinguer le nombre 1 des nombres supérieurs à 1 (il est interdit d’avoir plus d’un pion par case),
• distinguer la gauche et la droite (on joue vers la gauche),

ce qui vise la fin du CP et les classes suivantes.

Conway consacre à ce jeu un chapitre entier (le 13) de son livre On Numbers And Games :

La stratégie gagnante est en effet basée sur des notions subtiles de théorie des groupes et de physique théorique, et n’est pas très simple à décrire. Ceci dit, le cadre du jeu est lui-même assez simple avec des jetons sur une bande, comme cette figure de Conway :

(on constate que Conway utilise bien des jetons plats, empilables, mais des pions comme ceux du jeu d’échecs sont également possibles, d’autant que ci-dessus il n’y en a que 8, en effet il est matériellement difficile de mettre des pions du jeu d’échecs l’un au-dessus de l’autre)

Le jeu de Welter est impartial, donc on peut chercher une stratégie gagnante sans utiliser l’arsenal théorique de Conway : il suffit de tracer le graphe du jeu et de le colorier pour trouver une stratégie gagnante. Pour cela, il est intéressant de modéliser le jeu (et son plateau) en Python.

Codage du plateau

Le plateau du départ :

est assez naturellement codé par un tableau de booléens :

[True,False,False,True,False,True,True,False]

ou (ce qui revient au même) par un tuple d’entiers :

(1,0,0,1,0,1,1,0)

ou encore (c’est ce qu’on ferait en C ou Rust) par un octet 10010110 soit le nombre entier 150) mais aucune de ces représentations ne permet facilement de coder un tour de jeu. Ceci dit, on constate la présence

• d’un variant : la somme des indices des cases où il y a un pion (un tour de jeu consiste à faire décroître l’un de ces indices, donc leur somme),
• d’un invariant : le nombre de pions est toujours égal au nombre initial de pions, puisqu’on ne retire ni ne rajoute un pion au cours du jeu (comme disait Lavoisier, rien ne se perd, rien ne se crée, tout se transforme).

Or il y a un moyen de coder cet invariant, non dans une variable, mais comme longueur d’une collection, celle des abscisses des jetons. Finalement le plateau

sera codé par l’expression (0,3,5,6) donnant (dans l’ordre croissant) les abscisses des 4 pions, le pion le plus à gauche ayant pour abscisse 0. C’est cette modélisation qui sera choisie dans la suite, ne serait-ce que parce que le tuple

(0,3,5,6)

occupe 56 octets de mémoire, alors que la chaîne de caractères

|o| | |o| |o|o|

en occupe 64.

Utilitaires

Tout d’abord, on regarde les pions de gauche à droite, sans tenir compte de l’historique de leurs déplacements, donc (0,3,5,2) peut aussi être représenté sous la forme (0,2,3,5) où les abscisses sont triées dans l’ordre croissant. On définit alors une fonction can donnant la forme canonique d’un tuple (ou plateau de jeu) :

def can(p):
    return tuple(sorted(list(p)))

(on convertit le tuple en une liste, qui est mutable, on trie cette liste et on convertit le résultat à nouveau en un tuple)

Ainsi, dans le dessin du graphe d’un jeu de Welter, on évitera d’avoir plusieurs sommets correspondant à la même situation de jeu.

Ensuite, on définit une fonction str1, destinée à remplacer str, qui donne une chaîne de caractères plus lisible que le tuple, avec des pions représentés par la lettre o et des bords de cases représentés par des traits verticaux :

def str1(p):
    tab = [' ']*(1+max(p))
    for x in p:
        tab[x] = 'o'
    return '|'+'|'.join(tab)+'|'

avec ça on dessine des tuples lisibles :

>>> str1((0,3,5,6))
'|o| | |o| |o|o|'
>>> str1(can((0,3,5,2)))
'|o| |o|o| |o|'

On constate au passage que les cases vides à droite ne sont plus représentées, en effet elles ne servent plus à rien dans le jeu.

Enfin, un dernier utilitaire pour la suite est la vérification que chaque case ne contient au maximum qu’un seul pion :

def ok(p):
    return all(p[i]!=p[j] for i in range(len(p)) for j in range(i))

En effet, dire qu’aucune case ne contient plus d’un pion, c’est vérifier qu’aucune abscisse n’est présente plus d’une fois dans le tuple. A priori, c’était le point faible de cette modélisation (avec un tableau d’entiers on aurait juste eu à écrire all (x in (0,1) for x in tab)) et le fait d’avoir réussi à exprimer la condition en termes d’abscisses est garante de la réussite du modèle.

Règle du jeu

On définit maintenant une fonction tenter qui modifie le plateau (un tuple d’abscisses entières) en respectant la règle du jeu :

def tenter(p,i,j):
    if j<p[i]:
        q = list(p)
        q[i] = j
        if ok(q):
            return can(q)

La fonction prend en entrée un plateau de jeu p (un tuple d’abscisses de pions), un indice de départ i (p[i] est l’abscisse du pion à bouger) et une abscisse j d’arrivée (là où ira le pion si possible). Si on peut bouger le pion d’indice i, son abscisse sera j, et si on ne peut pas (parce que j est trop grand – trajet vers la droite ce qui est interdit par la règle du jeu – ou parce que cela aboutirait à plus d’un pion sur une case) alors la fonction ne renvoie rien, ou plutôt elle renvoie None. Si le mouvement est possible, la fonction renvoie le nouveau plateau can(q).

La modélisation du jeu de Welter en Python est, à ce stade, terminée. Il reste juste à construire le graphe du jeu.

Graphe du jeu

Fidèle au programme de NSI (Terminale), on choisit de représenter le graphe par listes d’adjacences. Dans un graphe orienté, on dit qu’un sommet est enfant d’un autre s’il y a un arc les joignant, et la liste d’adjacence d’un sommet est la liste de ses enfants. On la calcule par une fonction, en tenant compte du fait que l’indice i ne peut pas dépasser la longueur du tuple, et que l’abscisse j ne peut pas dépasser p[i] :

def enfants(p):
    tab = []
    for i in range(len(p)):
        for j in range(p[i]):
            t = tenter(p,i,j)
            if t is not None:
                tab.append(t)
    return tab

Dans la liste tab, on n’a gardé que les positions possibles à partir de p, c’est-à-dire celles pour lesquelles la tentative renvoie autre chose que None.

On a alors les 8 coups possibles :

>>> enfants((0,3,5,6))
[(0, 1, 5, 6), (0, 2, 5, 6), (0, 1, 3, 6), (0, 2, 3, 6), (0, 3, 4, 6), (0, 1, 3, 5), (0, 2, 3, 5), (0, 3, 4, 5)]

Pour construire le graphe (un dictionnaire dont les valeurs sont des listes d’adjacence), on utilise le fait que sum(p) est un variant, donc que sa valeur initiale majore le nombre de boucles à parcourir :

def graphe(p):
    g = {p: enfants(p)}
    for n in range(sum(p)):
        gr = {k:v for k,v in g.items()}
        for k,v in g.items():
            for u in v:
                if u not in gr:
                    gr[u] = enfants(u)
        g = gr.copy()
    return g

On travaille sur une copie gr du graphe, parce que Python interdit (à juste titre) de modifier un objet mutable en cours de parcours dudit objet. Avec cette fonction on peut construire le graphe d’un jeu (utile pour chercher la stratégie gagnante) :

>>> graphe((0,3,5,6))
{(0, 3, 5, 6): [(0, 1, 5, 6), (0, 2, 5, 6), (0, 1, 3, 6), (0, 2, 3, 6), (0, 3, 4, 6), (0, 1, 3, 5), (0, 2, 3, 5), (0, 3, 4, 5)], (0, 1, 5, 6): [(0, 1, 2, 6), (0, 1, 3, 6), (0, 1, 4, 6), (0, 1, 2, 5), (0, 1, 3, 5), (0, 1, 4, 5)], (0, 2, 5, 6): [(0, 1, 5, 6), (0, 1, 2, 6), (0, 2, 3, 6), (0, 2, 4, 6), (0, 1, 2, 5), (0, 2, 3, 5), (0, 2, 4, 5)], (0, 1, 3, 6): [(0, 1, 2, 6), (0, 1, 2, 3), (0, 1, 3, 4), (0, 1, 3, 5)], (0, 2, 3, 6): [(0, 1, 3, 6), (0, 1, 2, 6), (0, 1, 2, 3), (0, 2, 3, 4), (0, 2, 3, 5)], (0, 3, 4, 6): [(0, 1, 4, 6), (0, 2, 4, 6), (0, 1, 3, 6), (0, 2, 3, 6), (0, 1, 3, 4), (0, 2, 3, 4), (0, 3, 4, 5)], (0, 1, 3, 5): [(0, 1, 2, 5), (0, 1, 2, 3), (0, 1, 3, 4)], (0, 2, 3, 5): [(0, 1, 3, 5), (0, 1, 2, 5), (0, 1, 2, 3), (0, 2, 3, 4)], (0, 3, 4, 5): [(0, 1, 4, 5), (0, 2, 4, 5), (0, 1, 3, 5), (0, 2, 3, 5), (0, 1, 3, 4), (0, 2, 3, 4)], (0, 1, 2, 6): [(0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 2, 5)], (0, 1, 4, 6): [(0, 1, 2, 6), (0, 1, 3, 6), (0, 1, 2, 4), (0, 1, 3, 4), (0, 1, 4, 5)], (0, 1, 2, 5): [(0, 1, 2, 3), (0, 1, 2, 4)], (0, 1, 4, 5): [(0, 1, 2, 5), (0, 1, 3, 5), (0, 1, 2, 4), (0, 1, 3, 4)], (0, 2, 4, 6): [(0, 1, 4, 6), (0, 1, 2, 6), (0, 2, 3, 6), (0, 1, 2, 4), (0, 2, 3, 4), (0, 2, 4, 5)], (0, 2, 4, 5): [(0, 1, 4, 5), (0, 1, 2, 5), (0, 2, 3, 5), (0, 1, 2, 4), (0, 2, 3, 4)], (0, 1, 2, 3): [], (0, 1, 3, 4): [(0, 1, 2, 4), (0, 1, 2, 3)], (0, 2, 3, 4): [(0, 1, 3, 4), (0, 1, 2, 4), (0, 1, 2, 3)], (0, 1, 2, 4): [(0, 1, 2, 3)]}

Mais un graphe, ça se dessine, du coup avec

from graphviz import Digraph

on peut définir une fonction de dessin :

def dessin(p):
    g = graphe(p)
    gr = Digraph(engine='dot')
    for k,v in g.items():
        for u in v:
            gr.edge(str1(k),str1(u))
    return gr

qui définit un graphe en essayant autant que possible de mettre au même niveau des sommets de même nombre de Grundy. Alors

gragra = dessin((0,3,5,6))
gragra.render('welt0356',format='pdf')

donne le graphe suivant :

Pour trouver la stratégie gagnante, il n’y a même pas besoin de calculer tous les nombres de Grundy, mais seulement colorier en vert les sommets de nombre de Grundy nul (et en rouge les autres). Cela revient à l’algorithme suivant :

• si un sommet a au moins un enfant vert, alors il est rouge,
• si un sommet n’a que des enfants rouges (ou pas d’enfant du tout) alors il est vert.

La stratégie gagnante est alors de systématiquement viser un sommet vert. Mais avec le jeu

qui est vert :

il n’y a pas de stratégie gagnante puisque tous les enfants de la position de départ sont, par définition, rouges.

Exemples

Voici d’autres exemples de jeux de Welter, où on peut calculer la stratégie gagnante. Nombre de Grundy 1 :

nombre de Grundy 0 :

Nombre de Grundy 2 :

Jeu du dollar d’argent

C’est à Nicholas de Bruijn que Conway et Gardner attribuent ce jeu. La variante sans le dollar d’argent est peut-être inspirée d’un jeu que Conway attribue à un certain Northcott, mais que Charles Béart décrit comme traditionnel de l’Ouest africain, sous le nom de Tiouk Tiouk. Quoiqu’il en soit, le jeu du dollar d’argent sans le dollar est une variante du jeu de Welter, où il n’est plus permis de sauter par-dessus un jeton, mais seulement de glisser un jeton (et il est toujours interdit d’empiler les jetons, contrairement à la version avec le dollar). Le plateau de jeu est donc le même que pour le jeu de Welter, comme en témoigne cette figure de Conway :

La théorie de ce jeu est plus simple que celle du jeu de Welter : dans la position ci-dessus, on est face à un jeu de Nim dont les tas ont pour hauteurs respectives 0, 2, 4, 5 et 3. Pour ce qui est de la modélisation en Python, la seule différence avec le jeu de Welter est qu’on ne peut pas sauter par-dessus un pion, ce qui s’exprime par une contrainte supplémentaire dans la fonction tenter :

def tenter(p,i,j):
    if j<p[i] and (i==0 or j>p[i-1]):
        q = list(p)
        q[i] = j
        if ok(q):
            return can(q)

(j doit être plus petit que p[i] parce qu’on va toujours vers la gauche, mais en plus il doit être plus grand que l’abscisse p[i-1] du pion précédent – à condition que celui-ci existe c’est-à-dire que i soit non nul – parce que sinon on a sauté par-dessus un pion, ce qui est autorisé dans le jeu de Welter mais pas celui du dollar d’argent sans le dollar)

Avec cette contrainte supplémentaire, les graphes de jeu ne sont pas les mêmes que pour Welter. Par exemple avec

le graphe est :

et sa coloration

montre que, cette fois-ci, il y a une stratégie gagnante, elle consiste à glisser le plus à gauche possible le second jeton.

Voici d’autres graphes du jeu du dollar d’argent sans le dollar :

Nombre de Grundy 1 :

Nombre de Grundy 0 :

Nombre de Grundy 3 :

Nombre de Grundy 1 :