Voici l’ancienne règle de ce jeu (à l’époque où on tenait compte des scores pour départager les joueurs) telle que décrite par des élèves de CE2 (une version plus détaillée au format pdf est disponible par un clic sur l’image) :

ainsi que la présentation faite aux élèves pour expliquer le principe du jeu :

La règle du jeu est également ici.

Ici la victoire des blancs est inéluctable :

En effet,

• les pions n’ayant pas le droit de reculer, aucun des deux n’aura l’occasion par la suite, de menacer l’autre,
• le pion noir ne peut avancer qu’une fois avant d’être bloqué alors que le pion blanc peut encore avancer, ce qui lui donne l’avantage.

Dans cette situation, on peut estimer que le raisonnement est numérique (on compte le nombre de mouvements possibles de chaque pion) ou géométrique (on estime la distance entre chaque pion et sa ligne d’arrivée). La rapidité du jugement laisse penser que c’est l’estimation de distance qui a été prépondérante.

Ceci dit, le motif deux pions ennemis sont à portée de cavalier l’un de l’autre, déjà évoqué ici) est présent dans cette situation. Mais lorsque le pion noir est en haut et le pion blanc en bas, ce motif joue un rôle plus décisif :

En effet,

• si c’est aux noirs de jouer, leur pion va en C3 (seul mouvement autorisé par la règle du jeu) et sera mangé par le pion blanc juste après (donc victoire des blancs),
• si c’est aux blancs de jouer ils peuvent suicider leur pion en D3, mais ils peuvent aussi maintenir leur piège en B3 :

Après cela le pion noir ne peut aller qu’en C3 et se faire manger.

On remarque que les deux figures ci-dessus comportent le même motif deux pions de couleur différente à portée de cavalier.

Ce motif est présent deux fois dans la situation que voici (et que les meilleures joueuses cherchent à obtenir) :

Les deux pions noirs tendent un piège au pion blanc, de façon analogue à une fourchette (échecs). Si on nomme Charybde le pion noir qui est en A3, et Scylla celui qui est en D4, alors

• ou bien le pion blanc va en B3 pour se faire manger par Charybde,
• ou il va en D3 pour se faire manger par Scylla.

Le piège est redoutable si c’est aux blancs de jouer. Mais même si c’est aux noirs de jouer, ils peuvent gagner ! En effet,

• ou bien Scylla va en C3

pour se faire manger juste après (avec défaite des noirs, selon l’argument arithmétique évoqué plus haut),

• ou bien Charybde bouge pour aller en B2

et se faire manger (seule réplique valable des blancs) ce qui aboutit à

ce qui permet à Scylla de tendre un nouveau piège :

Pour modéliser un concept (feature) dans ludii, on utilise le paradigme de la tortue : une liste de fractions précise les mouvements à effectuer pour aller d’une position (là où se trouve un pion, par exemple) jusqu’à une autre position (celle qu’on vise, celle où se trouve une pièce dangereuse, etc.), en supposant que l’orientation initiale est vers le nord et les fractions sont en tour de tortue, du moins dans le graphe du plateau de jeu. Par exemple la position

peut se coder

• {0,0,1/4} (deux fois vers le nord puis une fois vers l’est), ou
• {1/4,-1/4,0} (vers l’est, puis deux fois vers le nord, dont une sans rotation), ou
• {0,1/8} etc.

Pour faire de ce motif un concept, on se propose de ne l’appliquer qu’à la case to où vient d’arriver le pion (c’est-à-dire que le piège est tendu à l’adversaire) et uniquement lorsqu’il y a un pion ennemi à portée de cavalier e{0,0,1/4}, et d’y associer la valeur 0.5 c’est-à-dire que lorsqu’on essaye un coup au hasard, on s’arrange pour que le hasard favorise légèrement l’obtention de cette position. Ce qui s’écrit

(pair "rel:to=<{}>:pat=<els=[e{0,0,1/4}]>" 0.5)

On recherche de même à obtenir (et à empêcher l’adversaire d’obtenir) la position symétrique :

(pair "rel:to=<{}>:pat=<els=[e{0,0,-1/4}]>" 0.5)

Mais pour le motif

on va donner plus de poids (on en fait un concept plus fort) :

(pair "rel:to=<{}>:pat=<els=[e{1/4,0,-1/4}]>" 0.75)

Ainsi, pour imiter les enfants jouant à alquerkonane, on peut modifier le fichier source de ce jeu en y ajoutant l’IA suivante (dans les metadata) :

    (ai
        (features
            (featureSet
                All
                {
				(pair "rel:to=<{}>:pat=<els=[e{0,0,1/4}]>" 0.5)
				(pair "rel:to=<{}>:pat=<els=[e{0,0,-1/4}]>" 0.5)
				(pair "rel:to=<{}>:pat=<els=[e{1/4,0,-1/4}]>" 0.75)
				(pair "rel:to=<{}>:pat=<els=[e{-1/4,0,1/4}]>" 0.75)
                }
            )
        )
    )

On observe un comportement presque humain, jusqu’à rater une occasion de gagner évidente, tant l’IA est obsédée par la crainte de laisser l’adversaire bénéficier des concepts ci-dessus :

Sowing est un cas d’étude intéressant en NSI, essentiellement parce que son plateau est modélisable par une liste en Python (ou un tableau à deux colonnes en SQL) et de ce fait, a permis d’introduire en Première NSI la programmation défensive sur les listes, la programmation modulaire, le traitement de données en tables, et le seul chapitre sur l’IA qui soit au programme : la méthode des k plus proches voisins. Il s’agit d’un exemple d’algorithme qui apprend, mais c’est un algorithme de classification, donc pas spécialement adapté à la recherche d’une stratégie gagnante. Néanmoins, il est possible avec un algorithme de classification, de « décider » si une position qu’on peut atteindre en jouant, « ressemble » plutôt à une position gagnante ou à une position perdante, ce qui nécessite la notion de distance entre plateaux. Trois choix se proposent assez rapidement :

• La distance de Manhattan (illustrée ci-dessous) est la somme des différences entre les éléments correspondants des tableaux. Par exemple la distance de Manhattan entre [3,1,0,2] et [1,2,2,1] est 2+1+2+1=6. La distance de Manhattan généralise la distance de Hamming, utilisée en binaire.
• La distance euclidienne est la racine carrée de la somme des carrés des écarts. Par exemple le carré de la distance euclidienne entre [3,1,0,2] et [1,2,2,1] est 2²+1²+2²+1²=12 et la distance euclidienne est donc la racine de 12, soit environ 3,4641 (plus petite que la distance de Manhattan). La distance euclidienne n’est pas choisie ici parce qu’elle n’est pas forcément entière et est peu porteuse de sens en dimension 4.
• La distance de Tchebychev est le plus grand écart entre les deux tableaux. Par exemple la distance de Tchebychev entre [3,1,0,2] et [1,2,2,1] est le plus grand des nombres 1, 2, 2 et 1, soit 2.

On va détailler ici un exemple : on a vu que pour Sud, la position [0,3,3,0,0,1,5,0]

est gagnante. C’est à Sud de jouer, et Sud a 5 possibilités de jeu entre lesquelles choisir :

Le plateau est modélisé par [2,1,1,2,0,1,5,0] et, en indexant les cases du tableau par les nombres 0 à 7 (comme en Python, et contrairement à ce qui avait été fait plus haut), Sud peut jouer les cases 0, 1, 2, 3 et 5 :

• si Sud joue la case 0, on arrive à [0,2,2,2,0,1,5,0] dont la distance (de Manhattan) à la position gagnante est 4 :

• si Sud joue la case 1, on arrive à [2,0,2,2,0,1,5,0] dont la distance à la position gagnante est 8 :

• si Sud joue la case 2, on arrive à [2,1,0,3,0,1,5,0] dont la distance à la position gagnante est 10 :

• si Sud joue la case 3, on arrive à [2,1,1,0,1,2,5,0] dont la distance à la position gagnante est 8 :

• si Sud joue la case 5, on arrive à [2,1,1,2,0,0,6,0] dont la distance à la position gagnante est 10 :

Parmi les coups jouables par Sud, la case 0 (tout à gauche) est celle qui aboutit à la plus proche d’une position connue pour être gagnante, on peut donc considérer qu’elle ressemble à une position gagnante et l’algorithme conseille de jouer cette case.

En fait, on va utiliser plus de données qu’une seule position gagnante, en se constituant (par 100 parties jouées au hasard) une base de donnée de positions gagnantes pour Sud ou pour Nord, et en classant ces positions dans l’ordre croissant de distances (de Manhattan) à la position à tester. On regarde parmi les 5 plus proches positions s’il y a une majorité de positions gagnantes (auquel cas on conseille de jouer cette position) ou de positions perdantes (auquel cas on déconseille de la jouer). Et on le fait en Python :

On commence par programmer en Python le jeu Sowing (fait vers le début d’année de Première). On commence par définir les constantes et les valeurs initiales des variables :

from random import choice
N = 6
SUD = 1
NORD = -1
plateau = [2 for i in range(N)]

(ici il s’agit d’un plateau de 6 cases, contenant initialement chacune 2 graines ; chaque joueur est associé à un pas de semis, 1 pour Sud parce que Sud sème vers la droite, et -1 pour Nord parce que Nord sème vers la gauche)

Comme le premier qui ne peut plus jouer aucune case a perdu, il est utile de savoir quelles sont les cases jouables par le joueur j :

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

def jouables(p,j):
    return [i for i in range(len(p)) if est_jouable(p,i,j)]

Ensuite on crée deux fonctions utiles pour la suite, permettant de savoir si un joueur peut jouer, ou a déjà perdu :

def peut_jouer(p,j):
    return len(jouables(p,j))>0

def a_perdu(p,j):
    return len(jouables(p,j))==0

C’est maintenant qu’on explicite ce qu’on entend par jouer :

def jouer(p,i,j):
    if est_jouable(p,i,j):
        q = [x for x in p]
        graines = q[i]
        q[i] = 0
        while graines>0:
            i += j
            graines -= 1
            q[i] += 1
    return q

On définit les distances entre tableaux (ici c’est non la distance de Manhattan l1 mais la distance de Tchebychev linf qui a été retenue) :

def l1(tab1,tab2):  # distance de Manhattan
    assert len(tab1)==len(tab2)
    return sum([abs(tab1[i]-tab2[i]) for i in range(len(tab1))])

def linf(tab1,tab2):
    assert len(tab1)==len(tab2)
    return max([abs(tab1[i]-tab2[i]) for i in range(len(tab1))])

def l2(tab1,tab2):  # distance euclidienne
    assert len(tab1)==len(tab2)
    return sum([(tab1[i]-tab2[i])**2 for i in range(len(tab1))])**0.5

On dispose maintenant des outils permettant de simuler une partie de Sowing, où chacun des joueurs joue au hasard (parmi les cases jouables) :

def unepartie():
    fini = False
    j = SUD
    p = [x for x in plateau]
    while not fini:
        if peut_jouer(p,j):
            p = jouer(p,choice(jouables(p,j)),j)
            j = -j
        else:
            fini = True
    return ((j+1)//2,p)

La fonction choice du module random permet de choisir au hasard une case ; on la choisit au hasard parmi les cases jouables. On a vu plus haut que les concepts servent à moduler ce hasard, en faisant jouer moins au hasard. Mais ici on va se contenter de faire des statistiques sur les parties jouées, et pour cela à la fin d’une partie, on renvoie l’état final du plateau ainsi qu’un entier précisant pour qui ce plateau était gagnant. Cet entier est la moitié de j+1, soit de 0 pour Nord et de 2 pour Sud. L’indice 0 désignera donc Nord et l’indice 1 désignera Sud.

Pour simuler 100 parties de Sowing au hasard, on crée une variable destinée à contenir les statistiques, et après chaque fin de partie, on stocke la position gagnante dans le tableau statistique, à l’indice précisant le gagnant :

gagnant = [[],[]]

for n in range(100):
    j,p = unepartie()
    if p not in gagnant[j]:
        gagnant[j].append(p)

print([len(x) for x in gagnant])

L’affichage

[17, 13]

signifie que 30 positions gagnantes ont été enregistrées, dont 17 gagnantes pour Nord (donc perdantes pour Sud) et 13 gagnantes pour Sud.

Le choix des paramètres (distance, nombre de voisins les plus proches à considérer) a été établi empiriquement : il s’agissait d’éviter que par exemple aucun coup ne soit conseillé. Le script ci-dessous utilise donc la distance de Tchebychev et la valeur k=3 (il s’agit donc de la méthode des 3 plus proches voisins) :

def est_gagnante(p,j):
    tab = []
    for x in gagnant[0]:
        tab.append((linf(p,x),1))
    for x in gagnant[1]:
        tab.append((linf(p,x),-1))
    return sum([x[1] for x in sorted(tab)[:3]])>0

Le tableau tab contient des couples formés des distances entre la position à tester et les positions gagnantes, et du nom du joueur qui gagne (-1 pour Nord, 1 pour Sud). La fonction sorted lui associe un tableau similaire, mais rangé dans l’ordre croissant. L’ordre sur les couples est l’ordre lexicographique et les couples sont rangés par ordre de distance croissante. La notation :3 signifie qu’on extrait un tableau (de couples donc) formé par les trois premiers couples (c’est-à-dire les plus proches de la position p. Pour chaque couple x de ce tableau, on ne garde que son deuxième élement (égal à -1 ou 1) ce qui donne un tableau du genre [-1,1,-1]. On calcule la somme de ces éléments, laquelle sera égale à

• -3 si les trois positions étaient gagnantes pour Nord
• -1 si une des positions était gagnante pour Sud
• 1 si une position était gagnante pour Nord
• 3 si les trois positions étaient gagnantes pour Sud

Le signe de cette somme détermine donc le nombre majoritaire parmi les termes du tableau de longueur 3. La fonction ci-dessus renvoie donc le résultat de la comparaison de la somme avec 0 : on considère que si la somme est positive (c’est-à-dire qu’au moins deux des trois positions les plus proches était gagnante pour Sud) alors la position p ressemble plus à une position gagnante qu’à une position perdante, et on conseille de la jouer. Par exemple avec

for i in jouables(plateau,SUD):
    p = jouer(plateau,i,SUD)
    print(p,est_gagnante(p,SUD))

on peut voir quelque chose comme

[0, 3, 3, 2, 2, 2] False
[2, 0, 3, 3, 2, 2] False
[2, 2, 0, 3, 3, 2] True
[2, 2, 2, 0, 3, 3] False

qui fait conseiller par cet algorithme le choix de démarrer le jeu en semant le contenu de la case 2 qui aboutit au plateau [2, 2, 0, 3, 3, 2] lequel, selon les 3 plus proches voisins, a une allure de plateau gagnant (en tout cas, plus que les autres positions possibles).

Le logiciel CGSuite permet de calculer la valeur donnée par Conway à des jeux (parmi lesquels il y a des nombres). Dans CGSuite, les joueurs ne s’appellent pas Sud et Nord mais Left et Right. Alors la valeur d’un jeu est

• positive si c’est Left qui a une stratégie gagnante,
• négative si c’est Right qui a une stratégie gagnante,
• nulle s’il y a une stratégie gagnante pour celui qui vient de jouer, quel que soit son nom,
• sans signe (et donc non numérique) s’il y a une stratégie gagnante pour le prochain qui joue.

Une fois qu’on a placé dans le dossier examples de CGScript le fichier que voici :

on peut analyser certaines configurations de Sowing.

En entrant

g := examples.Sowing([2,2,0,3,3,2])
g.CanonicalForm

on obtient

{1|||1,{1|7/8}|{1|-1*},{*,{1|0,*},{1|v*}|0,{0|-1}}||0|-1}

dont il est difficile de voir si Sud a vraiment bien joué. Mais

g.CanonicalForm > 0

donne l’affichage true ce qui indique que Sud (Left dans CGSuite) a maintenant l’avantage : le meilleur coup (du point de vue) de Nord est de semer la case 3, ce après quoi Sud sème la case 1, et ensuite

• Nord peut semer la case 3 aboutissant à [3,0,3,0,4,2] d’où Sud gagne en semant la case 2,
• ou Nord peut semer la case 4 aboutissant à [4,1,3,2,0,2] d’où Sud peut semer la case 1, aboutissant à [4,0,4,2,0,2]. De là, Nord ne peut semer que la case 5, ce qui permet ensuite à Sud de gagner en semant la case 0.

Ceci prouve que dans le cas présent, l’algorithme des 3 plus proches voisins (avec la distance de Tchebychev) fut de bon conseil.

Noter que dans le cas des plateaux à 2 graines par case, seul le plateau à 6 cases a une valeur aussi complexe. Le plateau à 8 cases par exemple a une valeur égale à l’étoile (nimber 1), ainsi que le plateau à 7 cases et les plateaux à 3 ou 4 cases. Le plateau à 5 cases a une valeur nulle (il y a une stratégie gagnante pour celui qui joue en deuxième). Le jeu de Sowing à deux graines par case sur un plateau de 6 cases a cette valeur canonique :

+-{1|||1,{1|7/8}|{1|-1*},{*,{1|0,*},{1|v*}|0,{0|-1}}||0|-1}

De nombreuses valeurs ont été observées, notamment des nombres.

Les fractions possibles pour les mouvements sont données ici :

Les motifs recherchés sont ici. Les voici, pour les noirs (le lièvre) :

(pair "rel:last_from=<{1/8,3/8}>:to=<{}>:pat=<els=[!R0{0,1/8}]>" 1.9902246)
(pair "rel:last_from=<{0,-3/8}>:to=<{}>:pat=<els=[!R0{1/8,-1/4}]>" 1.4719115)
(pair "rel:last_from=<{1/8,3/8}>:to=<{}>:pat=<els=[!R0{0,1/4}]>" 1.4719115)
(pair "rel:last_from=<{-1/8,-3/8}>:to=<{}>:pat=<els=[!R1{0,1/8}, !R0{0,-1/4}]>" 2.0531988)
(pair "rel:last_from=<{1/8,3/8}>:from=<{0}>:to=<{}>:pat=<els=[!R0{0,1/4}, #{0,1/2,0,3/8}]>" 1.2288803)
(pair "rel:last_from=<{-1/8,-3/8}>:from=<{0}>:to=<{}>:pat=<els=[!R1{1/8,-1/8}, !R0{0,-1/4}]>" 1.9216644)
(pair "rel:last_from=<{0,-3/8}>:to=<{}>:pat=<els=[!R0{1/4,-1/8}]>" 2.0068963)
(pair "rel:last_to=<{0,3/8}>:to=<{}>:pat=<els=[!-{0,1/4,3/8}, !R1{0}, -{0,-3/8,-1/8}]>" 1.8388541)
(pair "rel:last_to=<{0,3/8}>:to=<{}>:pat=<els=[!R1{0}, -{0,-3/8,-1/8}]>" 1.6188504)

et pour les blancs (les chiens) :

(pair "rel:last_to=<{0,0}>:from=<{}>:to=<{0}>:pat=<els=[!-{1/4,-3/8}, f{0,1/8,3/8}]>" 1.8937898)
(pair "rel:last_to=<{0,0}>:from=<{}>:to=<{0}>:pat=<els=[]>" 1.3411281)
(pair "rel:from=<{0}>:to=<{}>:pat=<els=[N4{-1/2,0}, -{0,3/8,3/8}]>" 1.1824998)
(pair "rel:last_to=<{0,0}>:from=<{}>:pat=<els=[R1{1/8,3/8}, !-{1/4,-3/8}, f{0,1/8,3/8}]>" 1.683382)
(pair "rel:last_to=<{0,0}>:from=<{}>:pat=<els=[R1{1/8,3/8}, -{3/8,-3/8}, f{0,1/8,3/8}]>" 1.5172195)
(pair "rel:last_from=<{0,-3/8,-3/8}>:to=<{}>:pat=<els=[-{0,3/8,3/8}]>" 0.38498688)

Difficile d’y voir des concepts exploitables. Le point d’exclamation signifie la négation, la lettre f signifie pion de la même couleur (friend), le e est un pion de l’autre couleur (enemy), le dièse désigne une sortie de plateau (case hors du plateau de jeu), et les régions R0 et R1 sont les sommets où se trouvent les pions au départ. N4 signifie que le sommet considéré est de degré 4 (Neighbours : 4).

Par exemple le dernier concept des chiens (pour qui la direction 0 est vers le nord) est faible (il ne lui a été donné qu’un poids de 0,385) et associé aux deux caractéristiques suivantes :

• le sommet qui se trouve à un trajet d’une case vers le nord puis une case tournée de 3/8 de tour (vers la gauche) par rapport au nord puis une case tournée de 3/8 de tour par rapport au trajet précédent, est celui depuis lequel le pion noir venait d’effectuer un mouvement au tour d’avant (last from), autrement dit, le pion noir vient de quitter ce sommet ;
• le sommet auquel on accède en effectuant un trajet vers le nord (0) puis vers le sud-est (3/8) et enfin vers l’ouest (3/8+3/8=3/4=-1/4) est vide (tiret devant le trajet).

Mais ce sommet est facile à retrouver. Si un pion blanc est ici (tourné vers le nord) :

après le 0 il a avancé d’une case vers le nord :

après le premier 3/8 il a avancé d’une case vers le sud-est :

et après le second 3/8 (trajet d’une case vers l’ouest) il est de retour au début du trajet :

C’est compliqué, comme trajet, pour revenir au départ ! Mais ce trajet n’est pas possible à partir de n’importe quel sommet, seul un de ces trois sommets (marqués d’un pion blanc) peut le faire (le concept correspondant est l’angle droit d’un triangle rectangle isocèle dont l’hypoténuse est au nord-est) :

Le dernier motif est donc que les trois positions indiquées ci-dessus sont vides.

Quand à l’autre condition, elle revient à dire que le pion noir vient de quitter l’une des trois positions suivantes :

On est loin d’une stratégie gagnante facile à retenir, cela ressemble quand même beaucoup à du cas par cas. La situation ci-dessus a été souvent observée au cours du jeu mais on a du mal à estimer l’avantage qu’il peut y avoir (pour les chiens) à la provoquer.

L’idée géniale de Berlekamp, Conway et Guy est de donner un numéro à chaque sommet :

On constate qu’au début du jeu, les 4 animaux sont sur des sommets numérotés 1 (le lièvre), 0, 0 et -1 (les chiens) :

Or la somme de ces nombres est 1+0+0-1=0. Comme dans le jeu de Nim, quel que soit le mouvement fait par le lièvre, la nouvelle somme ne peut pas être 0. Dans le cas présent, le seul mouvement que peut faire le lièvre va d’une position numérotée 1 à une position numérotée 2, et la somme est devenue 2+0+0-1=1.

Il n’est pas possible de rendre la position à nouveau nulle, mais si le chien le plus en retrait avance (seule possibilité pour bloquer le lièvre), son numéro passe de -1 à 1 et la somme devient 2+0+0+1=3. Donc les chiens peuvent annuler à nouveau la somme des positions des 4 animaux, à condition de regarder cette somme modulo 3. Et il se trouve que la somme est divisible par 3 dans chacune des positions gagnantes décrites par Lucas :

Ici elle vaut 1+0+2+3=6 :

et ici elle vaut 5+3+4+3=15 :

Or, les nombres 6 et 15 sont divisibles par 3 !

Pour les chiens, la stratégie gagnante est faire en sorte que la somme des numéros des positions occupées par les 4 pions soit divisible par 3.

Et pour ce pauvre lièvre, la stratégie gagnante consiste à essayer de rendre cette somme divisible par 3, en exploitant pour ce faire une éventuelle erreur des chiens...