La notion d’intelligence artificielle est un concept dont on retrouve les traces jusqu’à plus de 1000 ans avant notre ère, mais qui connut surtout une progression fulgurante à partir du XIXe siècle avec les travaux de nombreux mathématiciens et ingénieurs qui commencèrent à en formaliser les principes. Ensuite, une convergence d’idées novatrices au début du XXe siècle noua un lien étroit avec ce domaine dès qu’il apparut que le cerveau était composé de neurones traitant des impulsions électriques. La théorie de l’information et des signaux de Claude Shannon et la théorie du calcul d'Alan Turing laissaient ainsi clairement entrevoir la possibilité de réaliser un des grands rêves de l’homme: la création d’une machine pensante. Dans ce contexte, il n’est donc pas étonnant que le développement de l’intelligence artificielle aille de pair avec l’essor de l’informatique.

La voie algorithmique et symbolique

Il est toutefois intéressant de noter que les premières tentatives de création d’IA ont été complètement à contrecourant du chemin choisi par l’évolution. Tous les animaux, du plus simple au plus élaboré, jouissent de réseaux neuronaux leur permettant de prendre toutes sortes de décisions complexes pour assurer leur subsistance. Cela est vrai même pour ceux que nous considérons comme les plus “stupides” sous prétexte qu’ils ne semblent pas disposer de la moindre once d’imagination. Pour autant, cela ne les empêche pas d’engendrer un vaste répertoire de comportements sophistiqués dont nous aurions bien du mal à en comprendre les mécanismes.

Mais la “noble et supérieure” pensée humaine, elle, est fortement associée à ses capacités d’abstraction, de raisonnement et de manipulation symbolique. Or il se trouve que la manipulation de symboles est assimilable à un calcul et celui-ci peut facilement être automatisé sur un ordinateur. C’est dès lors de cette manière que sont apparues les premières IA, sous la forme de programmes manipulant des symboles abstraits censés représenter les problèmes à résoudre. L’intelligence venait alors moins de la machine elle-même que de ses concepteurs, puisque ce sont ces derniers qui incorporaient toutes leurs connaissances et méthodes de raisonnement en créant une longue suite d’automatismes et de liens entre des symboles intrinsèquement vides de sens.

L’IA est ainsi un domaine où l’on se préoccupe moins de définir ce qu’est l’essence de l’intelligence que de construire un processus qui se comporte comme tel. Mais quoi qu’il en soit, il apparut surtout très tôt que de nombreux problèmes de la vie réelle ne pouvaient pas se résoudre facilement avec des algorithmes, c’est-à-dire avec des procédures manipulant une poignée de symboles ou d’information au travers de quelques règles rigides. Il fut alors évident que la création d’une véritable intelligence était un défi largement sous-estimé.

Malgré tout, il existe des domaines qui, par leur nature déterministe et bornée, se prêtent très bien à l’approche algorithmique et symbolique. Une bonne partie des jeux de société, particulièrement les jeux de stratégie pure [1]Un jeu de stratégie pure est un jeu où chaque joueur dispose de toute l'information relative aux événements du jeu, comme par exemple dans le jeu d'échec ou de dames. , en sont les fiers représentants. Comme ce sont souvent des disciplines qui requièrent beaucoup d’intelligence et de pratique pour un être humain, mais que leurs règles et objectifs sont parfaitement clairs, ils ont été choisis depuis toujours comme étalon de mesure pour noter les progrès réalisés en IA. Ils permettent en fait de s’abstraire de toutes sortes de problèmes pour lesquels les règles sont implicites, les objectifs totalement flous et où les performances peuvent largement dépendre des circonstances ; c’est-à-dire comme la quasi-majorité des situations à laquelle l’être humain et le reste du règne animal sont confrontés quotidiennement.

Le jeu d’échecs a été longtemps considéré comme la référence pour confronter l’intelligence humaine aux machines, avec un premier papier de Shannon sur ce thème en 1949. Et même si les premières tentatives affichaient des performances médiocres, les algorithmes qui ont été exploités dans ce jeu et bien d’autres ont été améliorés petit à petit au fil des décennies de recherches sur le sujet. L’approche de base la plus utilisée dans ces algorithmes est sans aucun doute quelque chose qui s’apparente à “si je joue ce coup, alors mon adversaire pourrait jouer tel ou tel coup, ce qui me permettrait de etc.”. Il s’agit en somme d’évaluer de manière combinatoire un maximum de possibilités endéans un temps limité. Mais si l’homme ne peut égaler une IA en termes de vitesse de calcul et d’exploration, il s’avéra aussi que la rapidité ne fait pas tout.

Pour comprendre cette problématique, il est bon de partir de deux jeux aux antipodes en termes de complexité combinatoire: le tic-tac-toe (jeu du morpion) et le go. Si l’on examine le nombre de configurations différentes que peut prendre le plateau de jeu, le tic-tac-toe se réduit à environ un millier de possibilités. Étant donné qu’un ordinateur de bureau moderne peut facilement évaluer cent-mille positions par seconde sans transpirer, le jeu peut être plié en un centième de seconde. Quel que soit le coup que vous jouez, la machine a pu l’anticiper et en tenir compte pour élaborer son déplacement précédent. Ayant une vue totale sur tous les possibles, l’ordinateur pourra jouer parfaitement et ne commettre aucune erreur stratégique.

Mais si nous regardons au jeu de go et à ses $10^{170}$ configurations différentes, le tableau est tout autre. Cette valeur est si démesurée que pour se le représenter il faut la comparer à ceci: prenez chaque atome de l’univers (environ $10^{80}$) et pour chacun d’eux imaginez qu’il renferme un autre univers comprenant lui aussi $10^{80}$ atomes. Et là vous êtes encore un peu en dessous du compte. Il va s’en dire que traiter ce nombre gargantuesque d’éventualités est hors de portée de n’importe quel ordinateur s’il se contente de les énumérer.

Avec “seulement” $10^{47}$ combinaisons, le jeu d’échecs est beaucoup plus abordable, mais requiert néanmoins énormément de savoir-faire et d’euristiques pour en venir à bout. Et la clé pour y parvenir, étant donné que l’arbre du possible est trop grand pour le parcourir entièrement, consiste à pouvoir évaluer intelligemment l’état de n’importe quelle position intermédiaire au cours d’une partie. Imaginons ainsi disposer d’un oracle qui, pour chaque configuration du plateau, vous retourne un nombre entre 0 et 1 pour vous indiquer quelles sont vos chances de remporter la partie en jouant parfaitement par la suite. Il va s’en dire que disputer un affrontement devient alors beaucoup plus facile, car il nous suffit de tester une poignée limitée de coups d’avance pour sélectionner celui qui maximise le résultat renvoyé par l’oracle.

L’image ci-dessous, reprise d’un article sur freecodecamp, illustre le principe sur un exemple artificiel où les blancs doivent définir leur prochain mouvement. L’idée consiste à choisir la branche qui maximise le score à venir, sachant que l’adversaire essaiera, lui, de le minimiser.

Bien sûr, un tel oracle n’existe pas, mais il est possible de s’en approcher par la construction de ce que l’on appelle une fonction d’évaluation. Un exemple élémentaire pour le jeu d’échecs pourrait consister à simplement attribuer un score pour chaque pièce (la reine ayant le score le plus grand, le pion le plus petit) et à faire la somme de celles encore présentes sur l’échiquier. Cette fonction est évidemment bien plus complexe dans un programme de jeu d’échecs moderne, mais l’idée est bien là.

C’est alors sur base de cet algorithme, de beaucoup d’optimisation, d’un ordinateur surboosté et d’une fonction d’évaluation soigneusement étudiée que DeepBlue put battre le meilleur joueur d’échecs du monde, Garry Kasparov, en 1997. Certes, il n’est plus possible de jouer parfaitement, à cause de l’horizon de calcul qui se voile rapidement au plus on essaie d’anticiper les coups d’avance, mais cette problématique est suppléée par l’intuition et l’expertise que les concepteurs peuvent apporter dans leur fonction d’évaluation.

Malheureusement, il s’agit d’une arme à double tranchant, car la qualité de jeu d’une telle approche repose entièrement sur la possibilité d’ultimement incorporer tout le savoir-faire d’un joueur expérimenté dans ladite fonction. Cela s’avère être une étape qui est non seulement délicate, mais qu’il faut aussi recommencer pour chaque nouveau problème du fait de sa spécificité. De plus, il n’est tout simplement pas toujours envisageable de produire une fonction d’évaluation correcte, et c’est pour cette raison que le jeu de go est resté longtemps dominé par la supériorité de l’intuition humaine.

La voie connexionniste

Comme beaucoup d’autres problèmes, le jeu de go ne se résout pas facilement avec une approche purement algorithmique. Et il faut même ajouter à cela que de nombreux problèmes se résolvent d’ailleurs très bien sans avoir recours à aucun mécanisme de conceptualisation élaboré. Par exemple, le règne animal s’est très vite doté d’un système visuel performant, capable de traiter des images complexes tout en étant accessible aux animaux les plus simples. La clé de cette réussite tient dans l’architecture neuronale développée par le règne animal et qui, même avec très peu de neurones, est apte à associer un comportement approprié en réponse à un stimulus (visuel ou autre) donné.

Ce genre de système ne requiert aucunement d’appliquer une méthode de raisonnement rigoureuse pour trouver la solution optimale à un problème. Il s’agit plutôt de déterminer le plus vite possible une bonne réponse comportementale vis-à-vis d’une situation qui peut souvent être létale. Et aussi sophistiqués que soient les cerveaux de l’espèce humaine, c’est avant tout par dessus ce type de mécaniques que les couches de réflexion élaborées de nos néocortex ont été construites. Les animaux disposent ainsi tous de cette capacité intuitive façonnée par des millions d’années d’évolution, difficile à retranscrire en matière d’algorithmes, et qui leur permettent de progresser aisément dans un monde à priori hostile et en perpétuel changement.

L’équivalent de ce paradigme dans le domaine informatique est ce que l’on appelle l'apprentissage automatique, ou “machine learning”. L’idée est ici, non pas de construire des algorithmes sur mesure pour résoudre un problème, mais plutôt d’échafauder des algorithmes qui se nourrissent de données et d’exemples pour découvrir par l’expérience quelle est la meilleure réponse à une situation donnée. Cette discipline a engendré de nombreuses techniques dans le champ des mathématiques et statistiques, mais ce sont surtout les méthodes basées sur les réseaux de neurones profonds qui ont permis dernièrement de réaliser les avancées les plus spectaculaires.

L’un des premiers succès de l’approche connexionniste dans le domaine des jeux de société remonte à 1992 et au travail de Gerald Tesauro sur le jeu de Backgammon. L’idée consistait à utiliser un petit réseau de neurones pour déterminer les statistiques du prochain coup à jouer, et d’entrainer le programme au cours de parties où la machine s’affronte elle-même. Ce programme s’est alors hissé au rang des meilleurs joueurs du monde, une première pour ce genre de compétitions.

Beaucoup de jeux exigent avant tout une très bonne lecture des évènements plutôt que de capacités de raisonnement avancées. Il s’agit de jeux où la difficulté première ne vient pas d’un problème d’explosion combinatoire comme dans le paragraphe précédent, mais plutôt du fait que les joueurs n’ont pas accès à toute l’information nécessaire pour raisonner parfaitement. Le jeu de poker en est le parfait exemple, et c’est seulement en 2017 que de vraies percées permirent à la machine de se hisser au niveau des meilleurs joueurs mondiaux. Celles-ci furent accomplies en utilisant des techniques de deep learning afin d’estimer au mieux les actions à prendre en réponse à celles des autres joueurs.

Le nombre d’actions qui s’offrent au joueur de poker est minime, se limitant à se coucher, à suivre ou à relancer. Mais le but n’est certainement pas d’essayer d’anticiper des dizaines de coups à l’avance ce que vont faire les adversaires, il s’agit plutôt de comprendre ce qu’ils dissimulent comme cartes dans leurs mains étant donné leur stratégie de jeu et les choix qui en découlent. L’optique est ainsi bien différente, car tout l’art du poker consiste à tromper l’ennemi en bluffant et, inversement, à découvrir ce que les autres vous cachent.

Dans le contexte de l’apprentissage automatique, la sous-discipline ayant pour but l’apprentissage par un agent autonome des meilleures actions à prendre en fonction de l’état de son environnement s’appelle l'apprentissage par renforcement ("reinforcement learning"). Et tout comme pour l’algorithmique, il s’agit d’une discipline qui s’étend bien au-delà du domaine ludique des jeux de société.

Une combinaison redoutable ?

L’approche exclusivement algorithmique est puissante pour raisonner sur la meilleure stratégie permettant de résoudre un problème, mais souffre aussi d’une limitation résultant de sa démarche purement abstraite. Contrairement à l’espèce humaine dont les couches évoluées de pensées sont bâties par-dessus nos capacités intuitives à comprendre et analyser le monde réel, un algorithme “raisonne” seulement en termes de symboles synthétiques définis par son concepteur. Et malheureusement, beaucoup de situations ne se laissent pas facilement capturer par cette simplification quelque peu limitante. L’immense difficulté à écrire un algorithme accomplissant une tâche de reconnaissance visuelle ou proposant une bonne fonction d’évaluation de l’état d’un jeu de go n’en est qu’un exemple parmi d’autres.

L’approche connexionniste, s’inspirant des fonctions cérébrales du règne animal, permet à l’heure actuelle de créer des IA extrêmement performantes pour une tâche unique donnée, dépassant même parfois les aptitudes humaines. Mais au-delà du calcul élaboré qu’elles exécutent, elles sont incapables de la moindre faculté de raisonnement. Ce qu’elles réalisent s’apparente plutôt à détricoter un stimulus sensoriel complexe pour le transformer en une valeur utile quelconque.

Néanmoins, un axe intéressant initialement proposé par DeepMind au travers de son IA AlphaGo, consiste à conjuguer les qualités de ces deux approches algorithmique et connexionniste. C’est par ce biais qu’ils ont réussi l’exploit de créer une IA qui se révèle finalement être supérieure au meilleur joueur de go du monde. L’idée consiste ainsi à toujours parcourir un arbre d’exploration combinatoire, mais en guidant la recherche au travers de l’intuition générée par un réseau de neurones. Cela permet de se passer de la fameuse et délicate fonction d’évaluation, car c’est ici le réseau neuronal, entrainé sur des milliers de parties contre lui-même, qui se charge de déterminer si une situation de jeu est avantageuse ou pas. C’est ce même réseau qui évite à l’algorithme de devoir estimer des myriades de coups possibles, la plupart du temps médiocres, mais de plutôt focaliser son attention sur les plus pertinents.

La voie proposée par DeepMind, quoiqu’artificielle et limitée à un seul jeu à la foi, tente ainsi de se rapprocher davantage de l’intelligence humaine. Certes, la quête d’une véritable IA, capable de raisonner en toutes circonstances et de faire face à de nouveaux problèmes promet d’être encore longue. Mais il est indéniable que le domaine des jeux offre un cadre extrêmement favorable à son éclosion.

Conclusion

Le domaine des jeux de société, et des jeux en général, n’a pas qu’un but divertissant. Car au travers de toutes sortes de règles plus ou moins complexes, ils permettent d’offrir un environnement idéal où humains comme IA peuvent se confronter et se mesurer l’un à l’autre. Il autorise ainsi à la recherche scientifique de se frotter à des défis toujours plus grands pour améliorer les performances de leurs machines.

Dans ce contexte, le but de ce projet consiste principalement à tirer parti des dernières avancées dans le domaine pour proposer des IA pouvant jouer à toutes sortes de jeux de société. L’idée est de voir s’il est possible de construire une sorte de partenaire solide à affronter, tout en étudiant les détails des meilleurs algorithmes disponibles. L’accent est mis particulièrement sur des méthodes dites générales, en ce sens qu’elles peuvent s’appliquer à toute une classe de jeux à la fois, sans qu’il soit nécessaire d’écrire du code spécifique au jeu lui-même (en dehors des règles qui le codifient naturellement).

Dans le prochain chapitre, nous reviendrons sur les objectifs de haut niveau, ainsi que sur l’architecture et les choix de conception sélectionnés pour y arriver.