Les connaissances maintenant nécessaires!
La nouvelle version 18 offre de toutes nouvelles possibilités pour l'entraînement et l'analyse: analyse stylistique des joueurs, recherche de thèmes stratégiques, accès à 6 milliards de parties LiChess qui permet une préparation optimale contre les futurs adversaires, téléchargement des parties sur chess.com avec API intégrée, moteur cloud intégré et bien plus encore.
.
Cet article est reproduit avec la permission de Spiegel Online où il apparut pour la première fois. Il a été demandé à l'auteur de décrire le développement de la programmation dans les échecs à partir de son vécu. Il ne s'agit donc pas ici d'un traité académique, mais d'un récit personnel, qui pourra servir de guide dans l'une des plus grandes entreprises scientifiques de notre époque.
L'aventure de la programmation dans les échecs - 2e partie:
Fat Fritz 2.0 est la dernière version du révolutionnaire Fat Fritz, basé sur les fameux algorthmes AlphaZero. Les analyses atteignent un niveau jamais atteint. Un must pour les joueurs de tous niveaux.
Comment les ordinateurs jouent-ils aux échecs, comment "pensent-ils"? Dans notre réponse à cette question, nous allons rencontrer de grands nombres - certains très, très grands nombres. Vous serez surpris.
Mais commençons par un module dont tous les programmes d'échecs ont besoin: le générateur de coups. Pour pouvoir jouer, la machine doit connaître les règles du jeu, elle doit savoir comment les pièces se déplacent. La formulation de ces règles est une tâche minutieuse - si vous n'y parvenez pas, les ♘♞ sautent par-dessus le bord de l'échiquier pour passer de l'autre côté, ou les règles du roque sont violées. J'ai raconté aileurs l'histoire amusante d'un jeune génie des échecs, âgé de douze ans et déjà Grand Maître, qui a démontré l'incapacité des joueurs d'échecs (et des programmeurs d'échecs) à formuler correctement les règles de promotion, au moins verbalement.
En tout cas, une fois que la machine a compris les règles, elle est capable de générer une liste de tous les coups légaux dans n'importe quelle position. Elle peut ainsi commencer à "regarder en avant". C'est ce que font tous les programmes d'échecs - et d'ailleurs tous les humains -: si je joue ceci et qu'il joue cela, je peux jouer ceci et s'il joue cela, je peux capturer son ♞. Cela vous semble familier? Bien sûr, les machines le font à une vitesse fulgurante, et elles le font généralement pour toutes les combinaisons de coups possibles. Ce qui nous amène aux très grands nombres dont je parlais en introduction.
Beaucoup de gens connaissent un très grand nombre lié aux échecs. La légende veut que le jeu ait été inventé par Sissa ibn Dahir, à qui son roi, Shirham, fut si reconnaissant qu'il a dit à son vizir qu'il pouvait avoir tout ce qu'il voulait comme récompense. "Juste un peu de blé", disait Sissa, "un grain sur la première case du plateau, deux sur la deuxième, quatre sur la 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 recevrait: 18'446'744'073'709'551'615. C'est-à-dire 18½ quintillion (10^8), ce qui représente aujourd'hui la production mondiale de blé pendant de nombreux siècles! Écoutez Stephen Fry décrire le phénomène:
Sissa a apparemment compris la progression géométrique - comment les nombres croissent de façon exponentielle lorsqu'ils sont multipliés par un rapport commun (définition approximative). Cela joue un rôle dans la considération générale des échecs : Serons-nous un jour capables de trouver une solution au jeu, c'est-à-dire en déduire une stratégie gagnante parfaite en examinant chaque séquence de coups possible? La réponse est un non retentissant!
Inspiré par AlphaZero, Komodo 14 calcule comme nulle autre programme d'échecs!
Considérons cela de plus près: dans une position normale aux échecs, un joueur aura, en moyenne, 40 coups possibles à choisir. À chacun d'eux, l'adversaire peut jouer une des 40 réponses différentes. Cela donne 1600 séquences différentes après un seul coup pour chaque côté. Et les chiffres augmentent de façon exponentielle: après deux coups pour chaque côté, 102 millions de séquences différentes sont possibles. Après trois coups, il y en a 4,1 milliards, soit plus que l'âge d'un humain compté en secondes. Le nombre de Sissa est atteint après seulement six coups, et après sept nous approchons le nombre d'étoiles dans l'univers. Supposons qu'une partie d'échecs dure en moyenne 40 coups. À ce stade, le nombre de séquences a atteint 10^128. Par rapport à cela, le nombre de particules dans l'univers connu, autour de 10^86, est totalement insignifiant!
Le problème ne sera donc jamais complètement résolue de cette façon, puisque rien ne pourra jamais calculer toutes les séquences de coups 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 niveau raisonnable. C'est exactement ce que font les ordinateurs: ils exécutent des séquences de coups à une profondeur donnée, évaluent la position qui en résulte, font varier la séquence de façon systématique et comparent l'évaluation de toutes les positions à cette profondeur. À la fin, ils jouent le premier coup de la séquence qui mène à la position la plus favorable. C'est essentiellement ce que font également les humains. Mais ils le font à un rythme bien plus lent que les ordinateurs. Un Grand Maître d'échecs calculera une ou deux suites par seconde; l'ordinateur peut en gérer quelques millions en même temps. Alors comment les humains peuvent-ils rivaliser ?
Houdini 6 continues where its predecessor left off, and adds solid 60 Elo points to this formidable engine, once again making Houdini the strongest chess program currently available on the market.
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 ont un sens - ils savent instinctivement qu'un grand nombre de coups peuvent être ignorés sans risque, car ces coups ne mènent à rien. Donc, au lieu de vérifier toutes les suites possibles, les humains ne regardent que celles qui sont plausibles. Le facteur de ramification dans le regard vers l'avenir n'est pas 40, mais seulement quelques coups. Les ordinateurs, en revanche, doivent généralement tout examiner.
Cette approche par la "force brute" semblait vouée à l'échec. En effet, dans les premiers temps, lorsque les ordinateurs faisaient encore des recherches superficielles, ils jouaient comme des amateurs. Les programmeurs ont donc essayé de mettre en œuvre un "élagage intelligent", de couper les branches les moins significatives afin que le programme puisse naviguer dans un arbre de recherche plus fin, et pénétrer plus profondément dans les positions.
C'est ce que MacHack, un programme d'échecs développé au MIT par Richard Greenblatt (assis, avec une cravate), était capable de faire. Le programmeur a écrit un "générateur de coups plausibles" qui limitait la ramification de l'ordinateur à 15 sur les deux premiers coups, et à 9 pour le reste de l'arbre. Ainsi, une recherche sur cinq demi-coups donnaient 127 575 positions à évaluer, et non les 102 millions que les programmes de force brute pure exigeaient.
MacHack a atteint le niveau d'un fort amateur, et il a joué des centaines de parties contre des humains, dont trois, dit-on, contre Bobby Fischer. Il est surtout connu pour avoir gagné une partie contre Hubert Dreyfus, un philosophe et critique de l'intelligence artificielle qui avait prédit que les ordinateurs ne seraient jamais capables de battre un enfant de dix ans aux échecs. MacHack lui a prouvé qu'il avait tort.
J'ai rendu visite à l'équipe du MIT vers 1980, lorsque MacHack avait atteint une force de jeu de plus de 1500 points Elo et était devenu... membre honoraire de la Fédération américaine des échecs. Greenblatt traversait une petite crise parce que son programme était encore trop sujet aux erreurs. Pour y remédier, il avait conçu ce qu'il m'a décrit comme un "bloqueur de bévues et un chercheur de coups brillants". Il s'agissait d'une armoire raccordée à MacHack et contenant un programme qui effectuait une recherche de force brute en parallèle. Cheops, comme il l'avait nommé, était destiné à alerter MacHack sur les tactiques que le programme heuristique aurait autrement manqué. Je ne sais pas quelle a été au final l'utilité de cette combinaison d'intelligence et de force brute.
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. Il était ingénieur en électricité de profession et 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 très sélectif, PIONEER, qui utilisait les principes généraux des échecs pour restreindre drastiquement la recherche. Le projet souffrait d'un manque de puissance informatique en Union soviétique, mais il a été bien connu à l'Ouest et a au moins produit un ouvrage de référence sur l'intelligence artificielle.
J'ai rendu visite à Botvinnik et à son équipe à Moscou et je l'ai rencontré à plusieurs reprises, en Allemagne, aux Pays-Bas et aux États-Unis. Il était clairement douloureux pour lui qu'un programme soviétique rival, KAISSA, soit bien plus fort que Pioneer. Kaissa était un programme de pure force brute, qui devint, en 1974, le premier ordinateur champion du monde d'échecs.
Le chef de l'équipe de programmation de Pioneer Boris Stilman (à gauche), et Mikhail Botvinnik. Nous avons passé une journée intéressante ensemble à la datcha de Botvinnik près de Moscou au début des années 1980. | Photo: Frederic Friedel
Les programmeurs ont gagné le match d'échecs contre l'intelligence humaine grâce à un certain nombre d'"astuces" qui leur ont permis de réduire le nombre de séquences à prendre en compte dans l'arbre de recherche sans affecter la qualité du résultat. La taille Alpha-Beta en est un bon exemple. Si vous avez un score final pour un coup, et que vous commencez à en calculer un autre, dès que vous avez trouvé une ligne 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 inférieur. Les programmeurs ont ont ensuite découvert que si vous ordonniez la séquence de coups que le programme recherchait en se basant sur une recherche précédente, moins profonde, vous obteniez un nombre de seuils nettement plus élevé. C'est ce qu'on appelle l'approfondissement itératif.
Grâce à cet algorithme et à une douzaine d'autres, les programmes d'échecs ont pu effectuer des recherches de plus en plus profondes, et devenir de plus en plus puissants. Toutes les tentatives de définition générale des coups "significatifs" dans les programmes d'échecs ont été abandonnées, la méthode "intelligente" (également connue sous le nom de "type B de Shannon") de programmation des échecs ayant échoué. Et l'accélération vraiment spectaculaire du matériel informatique au fil des ans a contribué au triomphe de la méthode de la force brute. Elle a permis aux programmes informatiques de rivaliser rapidement, puis de dépasser complètement les capacités humaines aux échecs. Ce phénomène a été décrit dans mon article précédent.
Fin de l'histoire? Pas du tout. Avec l'avènement d'AlphaZero a eu lieu 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 le sujet du prochain article qui mettra un terme à cette enquête-témoignage sur l'histoire de la programmation aux échecs.
Publié pour la première fois en allemand dans Spiegel Online: Siege durch brutale Gewalt. ChessBase is a cooperation partner of DER SPIEGEL.ChessBase travaille en partenariat avec DER SPIEGEL.
Le duo parfait pour développer de nouvelles idées, obtenir des analyses précises et organiser un entraînement ciblé et continu!
ChessBase Account Abonnement Premium annuel
Pour ne rien manquer des événements échiquéens et profiter des multiples applications développées par ChessBase, ouvrez un compte Premium annuel! Non seulement vous ne payez que dix mois au lieu de douze, mais vous recevez encore un treizième mois gratuit!
