Quand on ne connaît aucun raccourci, ni choix glouton dont on sache prouver qu’il est le bon, ni sous-problèmes qui se répètent, il reste à parcourir l’arbre de tous les choix possibles. Cet arbre est le plus souvent gigantesque, mais on n’a presque jamais besoin de le parcourir en entier : il suffit de reconnaître au plus tôt qu’une branche ne mène nulle part, de l’abandonner, et de revenir au dernier embranchement pour essayer la suivante. C’est le retour sur trace (backtracking). Et quand l’arbre est celui d’une partie, les embranchements appartiennent tour à tour à l’un et à l’autre joueur, qui ne veulent pas la même chose.
En 1848, le compositeur de problèmes d’échecs Max Bezzel pose une question dans un journal berlinois : peut-on placer huit reines sur un échiquier sans qu’aucune ne puisse en prendre une autre ? Une reine attaque sur toute sa ligne, toute sa colonne et ses deux diagonales. Gauss lui-même s’y intéresse, et l’on finit par établir qu’il y a $92$ solutions. On peut essayer à la main sur l’échiquier ci-dessous avant de laisser faire l’algorithme.
Deux reines sur une même ligne se prendraient : il y en a donc exactement une par ligne. L’algorithme les pose ligne après ligne, de haut en bas. Sur chaque ligne, il essaie les colonnes de gauche à droite et pose la reine sur la première case qui n’est pas en prise, puis passe à la ligne suivante. Si une ligne n’offre aucune case libre, c’est une impasse : inutile d’aller plus loin, l’un des choix précédents était mauvais. On revient alors sur la ligne précédente, on retire sa reine et on la décale vers la droite.
Sur l’échiquier ordinaire, il suffit d’essayer $876$ cases pour trouver une première solution, et $15\,720$ pour les trouver toutes. C’est infime comparé aux $16\,777\,216$ façons de poser une reine par ligne. Chaque impasse coupe d’un coup toutes les façons de compléter l’échiquier qu’on aurait pu imaginer à partir de là : on ne les examine jamais.
Tous les algorithmes de retour sur trace ont la même forme : une fonction récursive qui reçoit une solution partielle et essaie de la prolonger.
def explorer(partielle):
if partielle est complète:
on la garde
else:
for choix in les prolongements possibles:
if choix est compatible avec partielle:
faire(choix)
explorer(partielle)
défaire(choix)
Le retour en arrière, c’est la ligne défaire(choix) : au retour de l’appel récursif, la solution partielle doit être exactement celle d’avant, pour que le choix suivant parte du bon endroit. Pour savoir où l’on en était dans chaque ligne, rien à programmer : c’est la pile d’appels qui s’en souvient.
Le sac à dos de la page précédente se prête lui aussi au retour sur trace. Pour chaque objet, on le prend ou on le laisse : l’arbre des choix est binaire, et ses $2^n$ feuilles sont tous les sacs imaginables. La force brute les examine toutes. On peut couper deux sortes de branches :
Pour l’estimation, on remplit la place restante avec les objets restants par valeur au kilo décroissante, en s’autorisant à découper le dernier objet qui ne rentre pas. Pour ce sac à dos « fractionnaire », le glouton est optimal, et aucun vrai sac ne peut faire mieux : c’est une borne. La méthode porte le nom de séparation et évaluation (branch and bound) : séparer, c’est créer les deux branches, évaluer, c’est calculer la borne.
L’ordre d’exploration compte : en descendant d’abord du côté « avec » et en rangeant les objets par valeur au kilo décroissante, on rencontre très tôt un bon sac, et un bon record fait couper davantage. Sur ces six objets, la force brute visite les $127$ nœuds de l’arbre, la séparation et l’évaluation seulement $13$. L’écart se creuse vite avec le nombre d’objets :
Rien ne garantit que l’élagage soit toujours aussi efficace : sur des instances construites pour le piéger, il reste un nombre exponentiel de nœuds à visiter. Mais avec des bornes plus fines, c’est cette méthode qui permet aux logiciels d’optimisation de résoudre en pratique des problèmes à des milliers de variables, de la planification des vols à la découpe de tôles.
Polyominos et Sudoku ont droit à leur algorithme au nom aguicheur : X. Il résout les problèmes de couverture exacte : on dispose d’une liste de contraintes et d’une liste d’options, chaque option satisfaisant certaines contraintes, et l’on doit choisir des options de sorte que chaque contrainte soit satisfaite une et une seule fois. Paver une grille avec des pièces, c’est cela : chaque case doit être couverte exactement une fois, et chaque pièce utilisée exactement une fois.
Une option, c’est un triplet $(l, c, n)$ : « mettre le chiffre $n$ dans la case de la ligne $l$ et de la colonne $c$ ». Il y en a $9 \times 9 \times 9 = 729$. Les contraintes se rangent en quatre familles de $81$, soit $324$ en tout :
| Famille | Contrainte (une par couple) | L'option $(l, c, n)$ satisfait… |
|---|---|---|
| case | la case $(l, c)$ reçoit un chiffre | la contrainte $(l, c)$ |
| ligne × chiffre | la ligne $l$ contient le chiffre $n$ | la contrainte $(l, n)$ |
| colonne × chiffre | la colonne $c$ contient le chiffre $n$ | la contrainte $(c, n)$ |
| bloc × chiffre | le bloc $b$ contient le chiffre $n$ | la contrainte $(b, n)$ |
Chaque option satisfait exactement quatre contraintes, une par famille. Une grille remplie, ce sont $81$ options qui, ensemble, satisfont chacune des $324$ contraintes une et une seule fois : $81 \times 4 = 324$, le compte est bon. Les chiffres donnés au départ ne sont que des options imposées d’avance.
L’algorithme X est un retour sur trace dont chaque étape tient en quelques mots :
Le choix de l’étape 2 est l’élagage : plutôt que d’ouvrir l’arbre des possibles là où il est le plus touffu, on va là où il y a le moins de branches. Quand une contrainte n’a plus qu’une option, il n’y a même pas de choix à faire. L’animation ci-dessous suit l’algorithme pas à pas. À gauche, les petits chiffres gris sont les options encore vivantes ; à droite, les $324$ contraintes sont dessinées en quatre grilles de $9 \times 9$ (pour « ligne × chiffre », la rangée est la ligne et la colonne est le chiffre), colorées selon leur nombre d’options restantes.
Les amateurs de Sudoku connaissent deux réflexes de base. Le singleton nu : une case n’a plus qu’un candidat. Le singleton caché : dans une ligne, une colonne ou un bloc, un chiffre n’a plus qu’une place possible. Personne ne les a appris à l’algorithme X, et pourtant il les applique : une contrainte « case » à une seule option, c’est un singleton nu ; une contrainte « ligne × chiffre », « colonne × chiffre » ou « bloc × chiffre » à une seule option, c’est un singleton caché. Sur la grille « Facile », il ne fait que cela : aucun pari, aucun retour en arrière. Les techniques humaines apparaissent d’elles-mêmes, comme les cas particuliers d’une seule règle : aller au plus contraint.
Regardons les trois premières familles : elles correspondent aux couples $(l, c)$, $(l, n)$ et $(c, n)$. Les trois coordonnées de l’option $(l, c, n)$ y jouent des rôles parfaitement symétriques : sans les blocs, une grille de Sudoku est un carré latin, c’est-à-dire $81$ triplets tels que deux coordonnées quelconques déterminent toujours la troisième. Le joueur, lui, privilégie les cases, parce que c’est là qu’il écrit. Pour l’algorithme, « quel chiffre dans la case $(3, 5)$ ? » et « où va le $7$ dans la ligne $3$ ? » sont la même question, posée selon un autre couple de coordonnées. C’est pourquoi il trouve les singletons cachés, réputés plus difficiles à repérer, aussi facilement que les singletons nus. Seuls les blocs brisent la symétrie.
Difficile pour un humain ne veut d’ailleurs pas dire difficile pour l’algorithme. La grille « AI Escargot », présentée en 2006 par le mathématicien finlandais Arto Inkala comme la plus difficile jamais conçue, ne demande ici que $87$ retours en arrière, et celle qu’Inkala a proposée en 2012 environ $1\,400$ : quelques millisecondes pour un ordinateur. Ces nombres dépendent beaucoup de la façon de départager les contraintes qui ont le même nombre d’options : en changeant seulement cet ordre, l’Escargot peut en demander près de $1\,500$. La raison profonde est ailleurs : la couverture exacte est un problème NP-complet (comme le voyageur de commerce), et l’on ne connaît aucun algorithme efficace dans tous les cas. Pour une grille $9 \times 9$, l’élagage suffit largement ; pour des Sudoku géants $n^2 \times n^2$, l’explosion combinatoire finit toujours par gagner.
Ali Assaf a montré qu’avec des dictionnaires d’ensembles, l’algorithme X tient en une trentaine de lignes de Python. La version ci-dessous suit son idée. X associe à chaque contrainte l’ensemble des options qui la satisfont, et Y à chaque option la liste des contraintes qu’elle satisfait. La fonction choisir retire les contraintes satisfaites par une option, et retire les options incompatibles des autres contraintes. Elle renvoie ce qu’elle a retiré, pour que rendre puisse le remettre : rendre parcourt les mêmes boucles en sens inverse, si bien que le problème retrouve exactement son état d’avant. La recherche elle-même ne s’occupe que de choisir, essayer et revenir.
Rien dans algorithme_x, choisir et rendre ne parle de Sudoku : seule la fonction sudoku traduit la grille en contraintes et en options. Le même moteur pave un échiquier de pentominos ou place huit reines, pourvu qu’on lui décrive le problème dans sa langue.
Avec des dictionnaires, chaque retrait et chaque remise a un coût. Tout l’art de l’algorithme X tient pourtant dans la façon de revenir en arrière à moindre coût, et Donald Knuth l’a résolu en 2000 par une structure de données d’une élégance rare, les liens dansants (dancing links) : dans une liste doublement chaînée, retirer un élément $x$ se fait en deux affectations, x.gauche.droite = x.droite et x.droite.gauche = x.gauche. Or $x$ garde, lui, la mémoire de ses voisins : pour le remettre en place au moment de revenir en arrière, il suffit de deux autres affectations, x.gauche.droite = x et x.droite.gauche = x. Les éléments « dansent » hors de la liste puis y reviennent.
Dans un jeu à deux joueurs, l’arbre des possibles change de nature : on ne choisit plus qu’à un embranchement sur deux, l’adversaire choisit aux autres, et il ne choisira pas ce qui nous arrange. On s’intéresse ici aux jeux où les deux joueurs jouent chacun à leur tour, sans hasard et en voyant tout (information complète) : le morpion, les dames, les échecs ou le go, mais pas le poker, le backgammon ou le pierre-feuille-ciseaux.
Un tas d’allumettes ; chacun à son tour en retire une, deux ou trois, et celui qui prend la dernière gagne. Qui doit gagner, selon le nombre d’allumettes ? On le décide de proche en proche, en partant de la fin, à partir de deux règles :
Devant $1$, $2$ ou $3$ allumettes, on prend tout et l’on gagne. Devant $4$, chaque coup laisse $3$, $2$ ou $1$ allumette à l’adversaire, qui gagne : $4$ est perdante. Devant $5$, $6$ ou $7$, on gagne en laissant $4$ à l’adversaire. Et ainsi de suite :
Les positions perdantes sont les multiples de $4$. La stratégie gagnante s’en déduit : laisser toujours un multiple de $4$ à l’adversaire. Celui qui commence devant un multiple de $4$ a perdu d’avance, si l’autre ne se trompe pas. La définition est récursive, et le dictionnaire memo évite de recalculer une position déjà rencontrée : c’est de la programmation dynamique.
Dans le jeu des bâtonnets de Fort Boyard, on part de $20$ bâtonnets, on en retire de $1$ à $3$, et c’est celui qui prend le dernier qui perd. Quelles sont alors les positions perdantes, et faut-il commencer ? Il suffit de changer une ligne du programme : devant un tas vide, c’est maintenant celui qui doit jouer qui a gagné.
Le jeu de Nim se joue avec plusieurs rangées d’allumettes. Chacun à son tour en retire autant qu’il veut, au moins une, mais dans une seule rangée. Celui qui prend la dernière gagne. La disposition $1$, $3$, $5$, $7$ est celle du film L’Année dernière à Marienbad (Alain Resnais, 1961), où un personnage gagne partie après partie.
Les positions sont trop nombreuses pour les tabuler de tête. En 1901, le mathématicien américain Charles Bouton trouve la règle : on écrit le nombre d’allumettes de chaque rangée en binaire, et l’on additionne sans retenue, colonne par colonne : $1 + 1 = 0$. C’est le ou exclusif (xor), noté ^ en Python. Le résultat s’appelle la somme de Nim, et une position est perdante exactement quand elle est nulle, c’est-à-dire quand chaque colonne contient un nombre pair de $1$. Les deux règles des positions gagnantes et perdantes suffisent à le démontrer :
Les positions de somme nulle se comportent donc exactement comme les positions perdantes : on ne peut que les quitter, on peut toujours y revenir, et la partie s’y termine. C’est ce que fait la machine ; quand c’est elle qui est en position perdante, elle joue un petit coup en attendant une erreur.
Rien n’empêche de vérifier la règle de Bouton par la force, en explorant toutes les parties possibles avec les deux règles du jeu de bâtonnets :
Un jeu est dit impartial quand les coups permis ne dépendent que de la position, et pas du joueur qui doit jouer : c’est le cas du jeu de bâtonnets et de Nim, pas des échecs, où chacun ne déplace que ses pièces. Dans les années 1930, Roland Sprague et Patrick Grundy démontrent, chacun de leur côté, que toute position d’un jeu impartial se comporte comme une rangée de Nim d’une certaine taille. Pour jouer à plusieurs jeux impartiaux à la fois, où l’on choisit à chaque tour dans lequel jouer, il suffit alors de faire la somme de Nim de ces tailles.
Dans l’arbre d’une partie, une même position peut apparaître à de nombreux endroits, atteinte par des suites de coups différentes. Plutôt que l’arbre, on dessine alors le graphe du jeu, appelé arène : un sommet par position, un arc par coup permis. Une position comprend aussi le joueur qui doit jouer, si bien que les sommets se répartissent en ceux d’Eve, qui commence, et ceux d’Adam, et que chaque arc va d’un sommet de l’un à un sommet de l’autre : le graphe est biparti. On se donne enfin l’ensemble $F$ des positions où Eve a gagné. C’est un jeu d’accessibilité : Eve veut amener la partie dans $F$, Adam veut l’en empêcher.
Prenons une variante du jeu de bâtonnets : un tas de $n$ allumettes, et chaque joueur peut prendre au plus le double de ce que l’adversaire vient de prendre. Au premier coup, Eve peut tout prendre sauf la totalité. Une position est un couple (allumettes restantes, maximum que l’on peut prendre), avec le joueur au trait, et Eve a gagné si la partie arrive en $(0, 0)$ avec Adam au trait.
L’ensemble des positions gagnantes pour Eve se construit de proche en proche, avec les deux mêmes règles qu’au jeu de bâtonnets. On part de $F$, puis on ajoute à chaque étape :
En notant $S_E$ et $S_A$ les sommets d’Eve et d’Adam et $\text{Succ}(s)$ les successeurs d’un sommet $s$, cela s’écrit
$$ \begin{array}{lll} \text{Attr}_0(F) &= &F \\ \text{Attr}_{i+1}(F) &= &\text{Attr}_{i}(F) \\ &&\cup \{s \in S_E \mid \text{Succ}(s)\cap \text{Attr}_i(F) \neq \varnothing \} \\ &&\cup \{s\in S_A \mid \text{Succ}(s)\subseteq \text{Attr}_i(F)\} \end{array} $$
La suite d’ensembles est croissante et ne peut pas dépasser l’ensemble des sommets : si le graphe est fini, elle finit par ne plus bouger. Sa limite est l’attracteur de $F$ pour Eve, noté $\text{Attr}(F)$ : c’est l’ensemble des positions d’où Eve est sûre de gagner.
Si le départ est dans l’attracteur, Eve a une stratégie gagnante, et même une stratégie sans mémoire : une règle qui, à chacun de ses sommets $s$, associe un coup $\sigma(s)$, sans se soucier du chemin qui y a mené. Il suffit de choisir pour $\sigma(s)$ un successeur dans l’attracteur, en prenant soin de le choisir parmi ceux ajoutés à une étape antérieure, pour se rapprocher de $F$ à chaque coup. Adam, lui, ne peut jamais en sortir. Et hors de l’attracteur, la situation est symétrique : c’est un piège pour Eve, Adam peut l’y maintenir indéfiniment.
Dans cette variante, Eve perd pour $n = 2, 3, 5, 8, 13$ : on reconnaît la suite de Fibonacci, d’où son nom de Nim de Fibonacci. Le programme ci-dessous calcule l’attracteur et le confirme bien au-delà. Pour éviter de réexaminer sans cesse les mêmes sommets, il part de $F$ et remonte les arcs à l’envers ; pour chaque sommet d’Adam, un compteur retient le nombre de ses successeurs pas encore dans l’attracteur, et ce sommet y entre quand le compteur tombe à zéro. Chaque arc n’est ainsi parcouru qu’une fois, et le calcul prend un temps proportionnel à la taille du graphe, comme un parcours.
Quand Eve gagne, une règle simple donne son coup : tout entier s’écrit d’une seule façon comme somme de nombres de Fibonacci non consécutifs (théorème de Zeckendorf, par exemple $12 = 8 + 3 + 1$), et il suffit de prendre le plus petit terme de cette somme, ici $1$.
Au Chomp, deux joueurs mangent tour à tour une tablette de chocolat rectangulaire dont le carré en bas à gauche est empoisonné. Chacun choisit un carré et le mange, avec tous ceux situés au-dessus et à sa droite ; celui qui doit manger le carré empoisonné a perdu.
Un théorème d’Ernst Zermelo (1913) assure que, dans un jeu fini à deux joueurs, sans hasard, à information complète et sans match nul, l’un des deux joueurs a une stratégie gagnante. Au Chomp, c’est toujours le premier, et l’argument est un vol de stratégie. Supposons que le second joueur ait une stratégie gagnante. Le premier mange seulement le carré en haut à droite ; le second répond par le coup que lui dicte sa stratégie. Mais ce coup emporte de toute façon le carré en haut à droite : le premier joueur aurait pu le jouer d’emblée, et appliquer ensuite la stratégie gagnante à la place du second. Les deux joueurs auraient alors une stratégie gagnante, ce qui est absurde.
On sait donc que le premier joueur gagne au Chomp, sans savoir en général quel premier coup jouer : pour le trouver, il faut calculer l’attracteur, et le graphe grossit vite avec la tablette.
Le graphe du morpion compte $5\,478$ positions, ce qui permet de calculer l’attracteur. Celui des échecs en compte de l’ordre de $10^{44}$ : aucun ordinateur ne le construira jamais. On revient alors à l’arbre de la partie, explorée à partir de la position actuelle.
Plutôt que « gagnante » ou « perdante », on attribue à chaque position une valeur du point de vue d’un joueur, disons les croix : $+1$ si elles gagnent, $-1$ si elles perdent, $0$ pour un match nul. Aux feuilles, la partie est finie et la valeur se lit sur la grille. Aux autres nœuds, on la déduit de celles des enfants : quand c’est aux croix de jouer, elles choisissent le coup de plus grande valeur, la valeur du nœud est donc le maximum de celles de ses enfants ; quand c’est aux ronds, ils choisissent le coup le pire pour les croix, la valeur du nœud est le minimum. C’est le principe du minimax, posé par John von Neumann en 1928. Les deux règles des positions gagnantes et perdantes en sont le cas particulier où les valeurs ne peuvent être que $+1$ ou $-1$ : un maximum vaut $+1$ si l’un des enfants vaut $+1$, un minimum vaut $+1$ si tous les enfants valent $+1$.
En appliquant le minimax à la grille vide, on trouve une valeur nulle : le morpion est un jeu nul, et deux joueurs parfaits font toujours match nul. Contre la machine ci-dessous, qui explore tout, on ne peut donc espérer mieux.
Pour choisir son premier coup, la machine examine plus d’un demi-million de positions, alors que le graphe n’en compte que $5\,478$ : l’arbre répète les mêmes positions, atteintes par des suites de coups différentes. Deux remèdes, déjà rencontrés :
Aux échecs, même l’élagage ne suffit pas : avec une trentaine de coups possibles à chaque tour et des parties de plusieurs dizaines de coups, l’arbre compte de l’ordre de $10^{120}$ feuilles (c’est le nombre de Shannon). On arrête donc l’exploration à une profondeur fixée, quelques coups à l’avance, et l’on remplace la valeur exacte des positions atteintes par une estimation, une heuristique : pour les échecs, un compte pondéré du matériel restant, corrigé par la sécurité du roi, le contrôle du centre ou la structure des pions. Au morpion, on peut compter les alignements encore possibles pour chacun : c’est ce que fait la machine dans ses deux derniers réglages. Avec un seul coup d’avance, elle ne voit pas venir les menaces ; avec deux, elle devient difficile à battre en examinant des milliers de fois moins de positions que l’exploration complète.
Deep Blue, qui bat le champion du monde Garry Kasparov en 1997, examinait 200 millions de positions par seconde avec alpha-bêta, à une profondeur typique de 6 à 16 coups, et parfois bien plus dans les situations tactiques. Au go, l’arbre est encore incomparablement plus touffu et les positions plus difficiles à évaluer : il faut attendre AlphaGo, en 2016, pour qu’une machine batte un des meilleurs joueurs du monde, Lee Sedol. Son évaluation des positions et le choix des coups à explorer ne sont plus écrits à la main, mais appris par des réseaux de neurones, entraînés sur des parties humaines puis sur des millions de parties jouées contre lui-même.
Deux complices sont interrogés séparément. Chacun peut se taire, c’est-à-dire coopérer avec l’autre, ou le dénoncer, c’est-à-dire trahir. On compte les gains en points : $3$ chacun s’ils coopèrent tous les deux, $1$ chacun s’ils se trahissent mutuellement, et quand l’un trahit un complice qui coopère, $5$ pour le traître et $0$ pour sa victime.
Quoi que fasse l’autre, trahir rapporte plus : $5$ au lieu de $3$ s’il coopère, $1$ au lieu de $0$ s’il trahit. Deux joueurs qui raisonnent ainsi trahissent tous les deux et gagnent $1$ chacun, alors qu’en coopérant ils auraient gagné $3$ : c’est le dilemme du prisonnier, formalisé en 1950. Les jeux précédents étaient à somme nulle, ce que l’un gagne l’autre le perd ; celui-ci ne l’est pas, et la coopération y profite aux deux.
Tout change si l’on joue de nombreuses fois de suite contre le même adversaire : trahir aujourd’hui peut coûter cher demain. En 1980, le politologue Robert Axelrod invite des spécialistes de la théorie des jeux à lui envoyer des programmes, et fait jouer chacun contre tous les autres, et contre lui-même, en matchs de $200$ tours. Le vainqueur est le plus court de tous, envoyé par le mathématicien et psychologue Anatol Rapoport : donnant-donnant (tit for tat), qui coopère au premier tour puis rejoue le dernier coup de l’adversaire. Un second tournoi, avec $62$ participants qui connaissaient le résultat du premier, donne le même vainqueur.
Donnant-donnant ne gagne jamais un match : au mieux, il fait jeu égal. Il gagne le tournoi parce qu’il obtient beaucoup de tous ses adversaires. Axelrod résume ses qualités en quatre mots : il est bienveillant, puisqu’il ne trahit jamais le premier, réactif, puisqu’il punit aussitôt une trahison, indulgent, puisqu’il recommence à coopérer dès que l’autre le fait, et lisible, puisque l’adversaire comprend vite qu’il vaut mieux coopérer avec lui. La simulation de l’évolution, où chaque stratégie se reproduit à proportion de ses gains, raconte une autre histoire. Dans une population de naïfs, les traîtres prospèrent d’abord ; mais en éliminant leurs proies, ils scient la branche sur laquelle ils sont assis, et ce sont les stratégies qui coopèrent sans se laisser exploiter, comme donnant-donnant, qui finissent par l’emporter. La coopération peut s’installer dans une population sans que personne ne l’impose.