Echec à Deep Blue
Le match d’échecs entre le champion du monde en titre Gary Kasparov et le super-ordinateur « Deep Blue » d’IBM a été largement commenté jusque dans la presse « populaire ». Vous vous souvenez sans doute que Kasparov, après avoir perdu sans appel la première partie a gagné les quatre suivantes. Nous n’allons pas ressasser l’éternelle discussion sur l’intelligence humaine et la stupidité artificielle (ou le contraire, je ne me souviens plus…) mais préciser quelques points techniques sur la programmation des jeux de stratégie en utilisant les échecs comme exemple. Les informations sur la programmation des échecs et « Deep Blue » sont tirées de l’article « Les impossibles en programmation des jeux » dans « Pour la Science » de juin 1995.
L’algorithme minimax.
Les programmes de jeu de stratégie utilisent tous un algorithme dit « minimax » pour évaluer le coup à jouer. Ils procèdent comme un joueur humain débutant en se « demandant » pour chaque coup : »si je joue ce coup, quelle sera la réponse de l’adversaire ? » En partant du principe que l’adversaire joue bien, il jouera le meilleur coup pour lui. Mon meilleur coup sera donc celui qui le forcera à jouer le plus mauvais pour lui, ou plus exactement le coup pour lequel la différence entre mon bénéfice et celui de l’adversaire sera le plus grand. Evidemment, pour juger quel coup l’adversaire jouera, il suffit au programme de renverser les rôles et d’examiner la situation qui résulterait pour l’adversaire d’un coup donné. On applique l’algorithme « récursivement » en considérant que le bénéfice des coups impairs (ceux du programme) doit être maximisé et celui des coups pairs (ceux de l’adversaire) minimisé.Si le programme trouve un coup tel que toute les réponses de l’adversaire mènent invariablement à sa perte, c’est gagné! Le problème, c’est que pour un jeu complexe comme les échecs, il est impossible d’évaluer tous les coups possibles jusqu’à la fin d’une partie.
L’explosion combinatoire.
En effet, l’application simple de l’algorithme « minimax » résulte dans une approche dite « force brute » qui consiste à analyser tous les coups possibles et les réponses à ces coups, puis les réponses à ces réponses etc. On doit donc explorer un « arbre » de coups. A chaque niveau d’analyse, chaque coup donne naissance à de nombreuses réponses possibles à analyser. Pour les échecs, le nombre de coups possibles selon les règles du jeu lors d’une partie « standard » tourne autour de 36 en moyenne. En évaluant un seul échange, on se retrouve avec 36×36=1296 situations à analyser. Un coup de plus et c’est 46656 puis 1’679’616 à la fin du deuxième échange déjà. « Deep Blue » applique « minimax » sur 11 coups ce qui mènerait à près d’un milliard de milliards de situations à évaluer.Ce phénomène est nommé « explosion combinatoire » : le nombre de calculs augmente comme une exponentielle et devient inimaginable : « Deep Blue » a beau évaluer près d’un milliard de coups à la seconde selon ses constructeurs (je doute toujours…), il lui faudrait 32 ans pour explorer l’arbre en entier sur 11 coups…A noter aussi qu’e mettant plein de processeurs en parallèle, on n’accélère qu’un tout petit peu la moulinette : il faudrait 1296 processeurs pour gagner deux coups de profondeur d’analyse dans un temps donné ou réduire à 10 jours l’analyse sur les 11 coups de « Deep Blue »…
L’élagage alpha-beta.
Pour limiter l’explosion combinatoire, une seule solution : limiter le nombre de coups à examiner. C’est là qu’interviennent les apôtres de l’intelligence artificielle : ils proposent tout naturellement de ne pas examiner plus avant les coups « stupides ». Oui mais voilà, qu’est-ce qu’un coup stupide ? C’est un coup qui provoque une telle perte pour le programme qu’il paraît impossible de gagner après ça. Par exemple si on s’aperçoit qu’en avançant tel pion, on sera condamné à perdre la reine quatre coups plus tard, on abandonne.Mais il faut se rappeller que le même algorithme « minimax » est utilisé pour évaluer les coups de l’adversaire. On part donc de l’idée que l’adversaire ne jouera pas de coups sucidaires. S’il en fait quand même, on étudiera la question à ce moment là…
La fonction d’évaluation.
Une autre conséquence du fait qu’on ne peut explorer l’arbre entier, c’est que l’on doit « juger » une situation intermédiaire, être capable de dire « cette situation vaut mieux pour moi que celle-ci ». Numériquement, il faut attribuer une « note » chiffrée à une situation sur l’échiquier. Et ça, c’est pas de la tarte. Si vous montrez un échiquier à un débutant, il va tout de suite appliquer « minimax » intérieurement pour vous dire si cette situation est bonne ou pas. C’est ce qu’on veut éviter avec le programme. On voudrait plutôt s’approcher du champion qui d’un seul coup d’œil vous dit si c’est bon ou pas. Bon, s’il y a un roi entouré de deux fous, deux tours et trois cavaliers ennemis, même moi je peux vous dire que c’est mal barré… Mais pour juger une situation de milieu de partie, tout l’a priori humain entre en jeu.Au niveau des grands programmes d’échecs, il est connu que, poussés au limites, c’est la fonction d’évaluation de leur(s) programmeur(s) qui transparaît. On doit donc associer de très bons joueurs d’échecs à l’écriture d’un programme.
Kasparov a (encore) gagné.
L’ancêtre de « Deep Blue » s’appelait « Deep Thought » (pensée profonde) et a été classé au niveau du 250ème joueur mondial en 1990. « Deep Blue » s’est mesuré au premier mondial, mais sa nette défaite montre qu’il n’est pas encore à la hauteur des tous premiers joueurs, surtout que Kasparov l’a eu comme un pro qu’il est. En effet, la connaissance de l’adversaire est essentielle aux échecs et il ne fait pas de doute que Kasparov est informé sur le mode de calcul des programmes. Il est clair que pendant la première partie il a testé les fonctions d’élagage en prenant des risques et certain qu’il a pu apprécier la « personnalité » de la fonction d’évaluation. Dans les parties suivantes, ses nombreux sacrifices ont à chaque fois servi à masquer des manoeuvres subtiles qui l’ont amené à la victoire.
Let’s Go!
Dans les années septante, un millionnaire américain a offert un prix aux auteurs des programmes qui deviendraient champions du monde avant l’an 2000 dans les trois jeux les plus répandus sur terre : le Backgammon, les Echecs et le Go.Au début des années 1980 déjà, un programme devenait champion de Backgammon. Dans ce jeu, l’aspect aléatoire introduit par les dés est extrêmement facile à prendre à compte par un ordinateur, mais un humain est en général très peu capable de calculer de complexes probabilités.En ce qui concerne les échecs, le suspens est certain. Les auteurs de « Deep Blue » vont tirer les enseignements du match contre Kasparov et revenir à la charge avec des moyens énormes et je dois dire que si je n’ai pas parié grand chose sur Kasparov ce coup-ci, je pense que le « Truc Blue » à venir a de grosses chances.Par contre, pas de souci en ce qui concerne le Go. Avec des pierres blanches et noires à poser où on veut sur un damier de 17×17=289 cases, l’explosion combinatoire est garantie sur facture, l’élagage quasi impossible (il n’y a pas de coup « bête » au Go…) . Le seul espoir est au niveau de la fonction d’évaluation, mais pour battre le champion du monde, il faudra faire une vraie « Intelligence artificielle ». Allez, je rajoute 100 balles à la prime pour celui qui fait un programme de Go champion du monde avant l’an 2100. Carrément.
Goulu le roi des fous.