Idée reçue : Tout ce que produit un ordinateur est prévisible

Octobre 2011 : le centre de recherche Inria Grenoble Rhône-Alpes participe au projet MathsC2+ et accueille pendant deux jours 35 élèves de 4e des collèges de la région.

L’une des sessions proposées a pour objectif de faire retrouver par les élèves une stratégie gagnante au jeu de Nim. La première partie de la session d’une heure et demie est ainsi consacrée à faire jouer plusieurs parties par les élèves groupés par quatre. Les allumettes sont fournies par le centre de recherche (sur quelle ligne budgétaire ?) et précautionneusement rendues inutilisables à d’autres fins par l’ablation de leur extrémité soufrée (une activité particulièrement apaisante et très appréciée par l’animateur dans un emploi du temps trépidant). Il s’agit ensuite de représenter une partie de Nim comme un chemin dans un graphe, objet mathématique présenté de façon intuitive aux élèves qui s’en saisissent rapidement ; puis de déterminer une stratégie gagnante, c’est-à-dire une stratégie qui amène le joueur qui débute à gagner systématiquement, quelles que puissent être les décisions de son adversaire, stratégie qui pourrait être inscrite dans un programme.

Le jeu de Nim est souvent pris comme exemple. Ici, avec une classe à Nancy. © Inria

À ce stade, l’animateur développe l’argumentaire partagé par tous ses collègues informaticiens : l’ordinateur ne fait strictement que ce que le programme a prévu qu’il fera, programme conçu par des humains en vue de résoudre une classe de problèmes. L’orateur évite soigneusement l’usage des mots « stupide » ou « bête » pour rendre compte de cette mécanique du calcul, car qualifier un ordinateur de stupide ou de bête serait se placer, de fait, dans le registre d’une mesure de l’intelligence, un débat qu’il s’agit à l’évidence de ne pas aborder. Donc, répète-t-il dans la crainte de ne pas avoir été suffisamment compris et appliquant le principe que la répétition serait à la base de la pédagogie, un ordinateur ne fait que ce que qu’on (les concepteurs du programme) a prévu qu’il fasse.

C’est à ce moment qu’Émilie (12 ans ? 13 ans ?), les yeux pétillants, bondit de sa chaise, lève le doigt (un geste fort judicieusement interprété par l’orateur comme la manifestation d’une demande de prise de parole) et enchaîne rapidement : « Mais alors, pourquoi l’ordinateur arrive à nous battre dans un jeu, si tout est prévu à l’avance ? ».

« Ne jamais sous-estimer son auditoire !» s’exclame tout d’abord l’animateur, in petto évidemment. Certes, la question ne le déstabilise qu’un moment, mais quand même…

Et d’expliquer que la stratégie du jeu de Nim est telle qu’elle assure la victoire à celui qui commence, y compris l’ordinateur, et que la connaissance par son adversaire de la stratégie et du programme qui la réalise n’y change rien.

Mais Émilie insiste : « Et pour d’autres jeux ? ».

…

Reprenons. Les circuits des ordinateurs exécutent fidèlement les programmes qui leur sont soumis. Appliquées sur un jeu de données, les instructions du programme se déroulent de façon complètement prévisible et produisent des résultats parfaitement reproductibles : une autre exécution du même programme sur les mêmes données produira, fort heureusement, les mêmes résultats. Mais cette prévisibilité est toute théorique.

En pratique, la complexité des programmes et l’efficacité des processeurs sont telles qu’il est impossible de prédire les résultats d’un programme un tant soit peu compliqué. Et c’est là que réside bien entendu tout l’intérêt du recours à l’ordinateur et à ses programmes : calculer vite et correctement.

Août 2010 : les deux informaticiens Alexander J. Yee et Shigeru Kondo battent le record de calcul de la valeur de π avec 5 000 milliards de décimales. Il est peu probable que la parfaite connaissance de leur algorithme ait permis aux auteurs du programme d’anticiper le résultat…

Mais revenons à nos jeux.

Juillet 1997 : le programme et la machine DeepBlue battent le maître d’échecs Garry Kasparov, à la suite, semble-t-il, d’une bévue de ce dernier. Juin 2005 : le programme et la machine Hydra battent le numéro 1 britannique des échecs Michael Adams. Au-delà de la discussion sur l’« intelligence » de ces programmes « stupides » et des conditions de la compétition, nous retiendrons que, G. Kasparov et M. Adams étant tous deux des champions d’échecs, les meilleurs programmes d’échecs gagnent contre n’importe quel autre joueur humain, y compris par conséquent contre les personnes qui les ont conçus et développés (les maîtres d’échecs ne sont pas les développeurs de ces programmes). Ces concepteurs et programmeurs connaissent les algorithmes mis en œuvre dans ces programmes gagnants, ainsi que l’intégralité de leur code. Ils disposent donc de la connaissance nécessaire pour prédire les coups que le programme jouerait en réponse aux leurs. Et pourtant…

En cette année 2012, où est célébré le centenaire de la naissance d’Alan Turing, il est intéressant de rappeler que celui-ci, grand amateur d’échecs, écrivit en mai 1952 un programme de jeu. Comme il ne disposait pas d’un ordinateur pour le faire tourner, il simulait les parties « à la main », c’est-à-dire en suivant les instructions une à une. Chaque coup prenait ainsi une demi-heure. Le prix à payer serait encore bien supérieur, de plusieurs ordres de grandeur, s’il s’agissait de s’assurer la victoire en disposant du listing du programme Hydra et de le dérouler « à la main »…

Avec les ordinateurs actuels, qui doivent beaucoup à Turing, vous pouvez vivre l’expérience qui consiste à vous faire battre par un programme de jeu que vous auriez vous-même conçu et dont vous connaîtriez et comprendriez tous les composants. Vous pouvez vous y essayer en vous lançant dans le développement d’un programme qui joue par exemple à Othello ou à l’awélé, voire au jeu de Hex (contrairement à une autre idée reçue, il n’est pas indispensable de disposer d’une salle de bains au pavage hexagonal pour s’adonner à ce jeu de stratégie).