Le jeu des échecs et sa programmation informatique
Comment les ordinateurs jouent-ils aux échecs, comment "pensent-ils" ? Dans notre réponse à cette question, nous allons rencontrer de gros chiffres - des chiffres très, très gros. Vous serez surpris.
Mais commençons par un module dont tous les programmes d'échecs ont besoin : le générateur de coups. Pour jouer, la machine doit connaître les règles du jeu, elle doit savoir comment les pièces se déplacent. Formuler ces règles est une tâche laborieuse - si vous n'y arrivez pas, les cavaliers sauteront de l'autre côté du plateau, ou les règles de roque seront transgressées. J'ai raconté l'histoire amusante d'un jeune génie des échecs, âgé de douze ans et déjà de la force d'un grand maître, qui a démontré l'incapacité des joueurs d'échecs (et programmeurs) à formuler correctement les règles de promotion, au moins verbalement.
Dans tous les cas, une fois que la machine a compris les règles des échecs, elle est capable de générer une liste de tous les mouvements légaux dans n'importe quelle position. Avec cela, il peut commencer un "look-ahead". C'est ce que font tous les programmes d'échecs - et d'ailleurs tous les humains - : si je joue ceci et lui joue cela, je peux jouer ceci et s'il joue cela je peux capturer son cavalier. Ça vous dit quelque chose ? Bien sûr, les machines le font à une vitesse fulgurante, et elles le font généralement pour toutes les combinaisons possibles de mouvements. Ce qui m'amène aux très grands nombres dont j'ai parlé et auxquels nous aurions affaire.
Beaucoup de gens connaissent un très grand nombre lié aux échecs. La légende raconte que le jeu a été inventé par Sissa ibn Dahir, et son roi, Shirham, était si reconnaissant qu'il a dit que son vizir pouvait avoir tout ce qu'il voulait comme récompense. "Juste un peu de blé," dit Sissa, "un grain sur le premier carré de la planche, deux sur le deuxième, quatre sur le troisième, et ainsi de suite." Le roi fut surpris par l'inexplicable modestie de ce souhait - jusqu'à ce qu'il ait calculé le nombre total de grains que Sissa allait recevoir : 18,446,744,073,709,551,615. C'est-à-dire 18½ quintillion (10^8), et il représenterait aujourd'hui la production mondiale de blé pendant plusieurs siècles. Écoutez Stephen Fry le décrire.
Sissa a apparemment compris la progression géométrique - comment les nombres augmentent exponentiellement lorsqu'ils sont multipliés par un facteur commun (définition approximative). Ceci joue un rôle dans la considération générale des échecs : Serons-nous un jour capables de résoudre le jeu ? Pouvons-nous obtenir une stratégie gagnante parfaite en examinant toutes les séquences de mouvements possibles ? La réponse est un non catégorique !
Jetons un coup d'oeil : dans une position d'échecs normale, un joueur aura, en moyenne, 40 coups possibles à choisir. A chacun d'eux, l'adversaire peut jouer l'une des 40 réponses différentes. Cela fait 1600 séquences différentes après un seul coup pour chaque camp. Et les chiffres augmentent de façon exponentielle : après deux coups de chaque côté, 102 millions de séquences différentes sont possibles. Après trois coups, il est de 4,1 milliards. Le nombre de Sissa est atteint après seulement six coups, et après sept coups nous approchons le nombre d'étoiles dans l'univers. Supposons que la partie d'échecs dure en moyenne 40 coups. A ce stade, le nombre de séquences a atteint 10^128. Comparé à cela, le nombre de particules dans l'univers connu, autour de 10^86, est complètement insignifiant. Vraiment.
Ainsi, le jeu ne sera jamais complètement résolu de cette façon - rien ne calculera jamais toutes les séquences de mouvements possibles. Mais ce n'est pas vraiment nécessaire. Si vous pouvez calculer chaque suite jusqu'à une profondeur limitée, vous commencez déjà à jouer à un jeu raisonnable. C'est exactement ce que font les ordinateurs : exécuter des séquences de mouvements à une profondeur donnée, évaluer la position résultante, varier systématiquement la séquence et comparer l'évaluation de toutes les positions à cette profondeur. En fin de compte, ils jouent le premier coup de la séquence qui mène à la position la plus favorable. C'est essentiellement ce que font aussi les humains. Mais ils le font à un rythme beaucoup plus lent que les ordinateurs. Un grand maître d'échecs va calculer une ou deux suites par seconde dans son esprit ; l'ordinateur peut en gérer quelques millions en même temps. Comment les humains peuvent-ils rivaliser ?
Intelligence contre force brute
La différence entre les humains et les ordinateurs est que les joueurs d'échecs expérimentés ne considèrent que les suites qui sont significatives - ils savent instinctivement qu'un grand nombre de coups peuvent être ignorés en toute sécurité. Ces mouvements ne mènent à rien. Ainsi, au lieu de vérifier toutes les suites possibles, les humains ne regardent que celles qui sont plausibles. Le facteur de ramification dans le look-ahead n'est pas 40, mais seulement quelques coups. Les ordinateurs, par contre, doivent généralement tout examiner.
Cette approche de "force brute" semblait vouée à l'échec. En effet, au début, lorsque les ordinateurs faisaient encore des recherches superficielles, ils jouaient comme des amateurs. Les programmeurs ont donc essayé de mettre en place un "élagage intelligent", de couper des branches moins significatives pour que le programme puisse naviguer dans un arbre de recherche plus mince et pénétrer plus profondément dans les positions.
Un tel exemple était MacHack, un programme d'échecs développé au MIT par Richard Greenblatt (assis ci-dessus avec cravate). Il a écrit un "générateur de mouvements plausible" qui limitait la ramification de l'ordinateur à 15 pour les deux premiers coups, et à 9 pour le reste de l'arbre. Ainsi, une recherche à cinq couches a donné 127 575 postes à évaluer, et non les 102 millions qu'exigeaient les programmes de force brute pure.
MacHack a atteint un solide niveau d'habileté d'amateur, et il a joué des centaines de parties contre des humains, dont trois, selon la rumeur, contre Bobby Fischer. Il était surtout célèbre pour avoir gagné une partie contre Hubert Dreyfus, un philosophe et critique d'intelligence artificielle qui avait prédit que les ordinateurs ne pourraient jamais battre un enfant de dix ans aux échecs. MacHack lui a donné tort.
J'ai visité l'équipe du MIT vers 1980, quand MacHack avait atteint une force de jeu de plus de 1500 points Elo et était, en fait, devenu un membre honoraire de la US Chess Federation. Greenblatt traversait une crise parce que son programme était encore trop sujet aux erreurs. Pour corriger cela, il avait conçu ce qu'il m'a décrit comme un " bloqueur de gaffes et un chercheur de brillance ". C'était un rack d'échecs matériel qui a exécuté une recherche de force brute parallèle à MacHack. Cheops, comme il l'avait appelé, était destiné à informer MacHack de tactiques que le programme heuristique aurait autrement manqué. Je ne sais pas jusqu'où il est allé, ni à quel point cette combinaison d'intelligence et de force brute s'est avérée utile.
Un autre effort (plus célèbre) pour utiliser la méthode intelligente aux échecs a été entrepris par l'ancien champion du monde (de 1948 à 1963, avec deux courtes pauses) Mikhail Botvinnik. Ingénieur électricien de profession, il rêvait de gérer l'économie soviétique en utilisant l'intelligence artificielle. Avec une équipe d'informaticiens, il a conçu un programme d'échecs hautement sélectif, PIONEER, qui a utilisé les principes généraux des échecs pour restreindre considérablement la recherche. Le projet souffrait d'un manque de puissance informatique en Union soviétique, mais il a fait l'objet d'une bonne publicité en Occident et a au moins produit un livre précurseur sur l'intelligence artificielle.
J'ai visité Botvinnik et son équipe à Moscou et je l'ai rencontré à plusieurs reprises, en Allemagne, aux Pays-Bas et aux Etats-Unis. Il était clairement douloureux pour lui qu'un programme soviétique rival, KAISSA, était beaucoup plus fort que Pioneer, et était, en fait, devenu le premier champion du monde d'échecs par ordinateur en 1974. Kaissa était un programme de force brute pure.
La raison pour laquelle les programmes non sélectifs ont gagné la journée est que les scientifiques ont trouvé un certain nombre de "trucs" qui leur ont permis de réduire le nombre de séquences qui devaient être prises en compte dans la recherche dans l'arbre sans affecter le résultat. L'élagage Alpha-Bêta en est un bon exemple. Les programmeurs se sont rendu compte que si vous avez un score final pour un coup, et commencez à en calculer un autre, dès que vous avez trouvé une ligne qui est inférieure à la première, vous pouvez abandonner cette branche de l'arbre de recherche. Il n'est pas nécessaire de perdre du temps à déterminer exactement à quel point le deuxième coup est pire. Ensuite, ils ont découvert que si vous avez ordonné la séquence de déplacements, le programme a fait une recherche basée sur une recherche précédente, moins profonde, et vous avez obtenu beaucoup plus de cut-offs. C'est ce qu'on appelle l'approfondissement itératif.
En utilisant cet algorithme et une douzaine d'autres algorithmes très intelligents, les programmes d'échecs ont été capables de chercher de plus en plus profondément, et de devenir de plus en plus forts. Toutes les tentatives pour définir de manière générale des coups "significatifs" dans les programmes d'échecs ont été abandonnées, la méthode "intelligente" (aussi connue sous le nom de "Shannon type B") de programmation des échecs a échoué. Et l'accélération spectaculaire du matériel informatique au fil des ans a contribué au triomphe de la méthode de la force brute. Il a permis aux programmes d'ordinateur de rivaliser et ensuite de surpasser complètement les capacités humaines aux échecs.
Fin de l'histoire ? Pas du tout. L'année passée a apporté un développement radicalement nouveau dans la programmation des échecs - un développement qui est pertinent non seulement pour le jeu mais pour l'humanité en général. C'est l'objet du dernier article...