Puisque nous parlons ces temps-ci d’Intelligence Artificielle et qu’un peu de nostalgie a commencé de poindre dans ces lignes, autant lui laisser libre cours une bonne fois avant de passer à autre chose, d’autant que les concepts que nous évoquerons conservent tout leur intérêt aujourd’hui.

L’un des enjeux qui se posait au chercheur en Intelligence Artificielle des années 1980, lequel ne visait à rien de moins que formaliser le raisonnement humain, était celui du langage informatique à utiliser dans ses expérimentations avec les ordinateurs. Le top du top, c’était d’inventer son propre langage – ce dont nous ne nous privâmes pas.

La grande majorité des langages de programmation sont dits impératifs : on explique à l’ordinateur ce qu’il doit faire, pas à pas et dans tous les cas possibles. On repose pour cela sur un répertoire d’instructions – des actions que l’ordinateur est censé savoir effectuer – ainsi que sur des structures de contrôle permettant d’enchaîner et de répéter ces opérations en fonction du résultat de certains tests. Nous en avons vu un exemple appliqué au dessin de fractales, où il s’agissait d’avancer, de tourner, de baisser ou lever le crayon. Parfois, dans les langages qu’on appelle assembleurs, les instructions données à l’ordinateur sont d’un niveau de détail extrême et concernent directement le matériel sous-jacent : « charge le contenu de l’adresse mémoire XXX dans le registre ABC et décale tous les bits de deux rangs vers la droite ». Le plus souvent, cependant, l’ordinateur manipule des concepts (on parle d’objets) plus proches de l’activité humaine : « envoie un mail à chaque client pour annoncer notre promotion sauf s’il a acheté le même produit dans les deux dernières semaines ». Dans tous les cas, le programmeur indique à l’ordinateur ce qu’il doit faire, et prend toute la responsabilité du résultat obtenu.

À côté de cette classe (très majoritaire) de langages informatiques en existe une autre, celle des langages dits déclaratifs. Ici, on ne décrit pas à l’ordinateur ce qu’il doit faire : on lui décrit le résultat final que l’on cherche à obtenir, et on compte sur lui pour l’atteindre. La description du résultat attendu doit être précise et sans équivoque, mais (en théorie) n’est pas censée apporter la moindre indication quant à la manière d’obtenir ce résultat. Dans le champ de concepts couvert par un langage déclaratif, l’ordinateur est censé savoir se débrouiller par lui-même. Pour cela, bien entendu, il s’appuie sur un algorithme, lui-même écrit généralement dans un langage impératif de plus bas niveau ; mais au lieu de résoudre un problème précis, cet algorithme (invisible à l’utilisateur du langage déclaratif qu’il sert) résout une large classe de problèmes.

Si vous dites à votre chauffeur de taxi « prenez l’avenue de Villiers jusqu’à la place du Maréchal-Juin, puis la rue de Courcelles, traversez le périph et prenez la première à droite », vous employez un langage impératif. Vous êtes de ce fait seul comptable du résultat – de l’atteinte de votre destination et du temps nécessaire pour y parvenir. Si vous lui dites en revanche « je vais rue d’Alsace à Levallois », vous employez un langage déclaratif. Le chauffeur (ou, de plus en plus souvent, son GPS) prend la responsabilité des choix nécessaires.

Une partie de la recherche en IA consistait à inventer des langages déclaratifs et des algorithmes associés permettant à l’ordinateur de traiter les énoncés qu’on lui soumettait via ces langages afin d’obtenir le résultat voulu. Quand cela marchait, il était difficile de ne pas trouver le programme sacrément malin.

On trouvait et on trouve toujours d’innombrables déclinaisons de cette notion de déclarativité, se traduisant par de nombreux formalismes pour représenter les résultats à obtenir, et tout autant d’algorithmes pour y arriver. On citera la programmation fonctionnelle, qui date des années 1960 et fait un retour foudroyant depuis quelques années, car elle se prête particulièrement bien aux architectures de calcul modernes, ainsi que la programmation logique, qui exprime le résultat souhaité sous forme d’énoncés logiques, et dont l’algorithme associé date de 1965. Un langage (en partie) déclaratif, SQL, est à l’œuvre depuis les années 1970 dans l’accès aux bases de données, et votre GPS s’appuie également sur un langage déclaratif – des jeux d’équations linéaires – dont l’algorithme associé, appelé Simplexe, existe depuis 1947.

La France fut à la pointe en matière de programmation logique via le langage Prolog, inventé au début des années 1970 par Alain Colmerauer. Une extension intéressante de ce courant, à laquelle votre chroniqueur eut le privilège de contribuer, est ce qu’on appelle la programmation logique par contraintes. L’idée est de décrire ce que vous cherchez à obtenir sous forme d’énoncés logiques appelés contraintes et que la solution à trouver se doit de respecter.

Un exemple classique et ludique est le fameux problème des huit reines. Vous cherchez à placer huit reines sur un échiquier, de façon qu’aucune d’elles ne puisse en prendre un autre. Cela signifie que deux reines ne doivent jamais se trouver sur la même ligne, sur la même colonne ou sur la même diagonale. Peut-on y arriver ? Oui, de multiples façons ; il existe 92 solutions, 12 si l’on tient compte des symétries. Pour autant, elles ne sont pas si faciles à trouver à la main. Même en plaçant systématiquement chaque reine sur une colonne et une ligne inoccupées, il y a plus de 40 000 manières de le faire, dont la plupart violent la condition sur les diagonales.

En programmation logique par contraintes, vous décrivez les conditions à respecter, et vous laissez le programme se débrouiller pour trouver les solutions. Vous représentez une position possible des reines par une liste de huit nombres entre un et huit : le premier nombre indique la ligne de la reine placée sur la première colonne, le deuxième la ligne de sa voisine de droite, etc. Cette représentation impose déjà que deux reines ne peuvent être placées sur la même colonne. Vous spécifiez ensuite que tous ces nombres doivent être deux à deux différents (afin que deux reines ne soient jamais sur la même ligne), mais aussi que la distance entre les lignes associés à deux colonnes doit être différente de la distance entre ces colonnes (pour éviter que deux reines puissent se prendre en diagonale). C’est tout, et de ce fait le programme est très court, concis, lisible.

Efficace ? C’est ici que l’algorithme sous-jacent intervient. S’il est naïf, ça se passera mal. Vous pourriez, bien, sûr, choisir une ligne pour chaque reine, tester si les conditions sont respectées, puis essayer une autre combinaison en cas d’échec. Mais vous risquez d’effectuer plus de 16 millions d’essais infructueux avant de trouver une solution. C’est considérable, et ça l’était encore plus à l’époque. Les algorithmes que nous mettions au point étaient plus malins que cela : ils pouvaient propager les contraintes, c’est-à-dire tirer parti le plus intelligemment possible de toute l’information apportée par un choix partiel. Si vous avez placé la première reine sur la première ligne, vous savez qu’aucune autre reine ne pourra aller là : vous pouvez donc éliminer le nombre 1 du domaine de valeurs possibles pour chacune des autres reines. Mais vous savez aussi que la deuxième reine ne pourra pas aller sur la deuxième ligne ; elle ne pourra être placée que sur la troisième ligne ou plus haut. Vous déduisez ainsi des zones interdites pour chacune des reines restantes ; puis vous choisissez une case licite où placer la deuxième reine (par exemple) et vous recommencez. Le jeu est d’exploiter au mieux l’information disponible pour éliminer les fausses pistes le plus tôt possible. Pour autant, vous ne voulez pas non plus nuire à la généralité de votre langage en recourant à des techniques ad-hoc, trop spécifiques ; l’élégance formelle reste un facteur important à prendre en compte.

Ce jeu, nous fûmes nombreux à le jouer à l’époque. Notre logiciel Charme, développé au laboratoire d’Intelligence Artificielle de Bull, et premier produit commercial du genre, fut rapidement poursuivi et parfois dépassé par nos concurrents d’autres labos ; il se basait bien entendu lui-même sur des travaux universitaires antérieurs. Tout ce monde-là rivalisait d’astuce pour résoudre plus vite que le voisin le problème des 8, des 32, des 64 reines… Et nous étions payés pour ça, pas pour faire cliquer des gens sur une publicité. Pur bonheur.

Que reste-t-il de toute cela ? Bien peu peut-être, mais pourtant cela compte. Les problèmes soumis à la programmation par contraintes sont le plus souvent très difficiles ; le nombre de solutions à tester augmente exponentiellement avec la taille des données, et on atteint vite des limites pratiques. Pire encore, il existe des situations sur-contraintes dans lesquelles aucune solution n’est possible, et pour lesquelles on cherche plutôt une solution « pas trop mauvaise ». D’autres techniques, comme le recuit simulé, se révèlent souvent plus efficaces en pratique, et le bon vieux Simplexe reste incontournable. En attendant que les ordinateurs quantiques rendent (peut-être) tout cela obsolète… Il n’en reste pas moins que le travail mené par toute une génération de jeunes chercheurs et ingénieurs se retrouve encore, compressé peut-être, fossilisé diraient les amers, sublimé diront les optimistes dont je suis, en fondation pour la suite de l’aventure – qui reste toujours aussi excitante.

Yannick Cras
Le nombre imaginaire