Facteur de ramification : quand l’IA pionnière a transformé les échecs en logique symbolique

En 1950, Claude Shannon, chercheur aux Bell Labs, fit la démonstration d'une souris mécanique naviguant dans un labyrinthe. À chaque intersection, l'appareil faisait face à un facteur de ramification de trois, illustrant ainsi le principe de l'exploration par essais et erreurs. Pour Shannon et les premiers informaticiens, ce labyrinthe n'était pas une simple curiosité mécanique, mais un micro-monde contrôlé conçu pour analyser la manière dont une machine pouvait s'orienter parmi des choix limités grâce à la logique formelle.

L'explosion combinatoire des micro-mondes

Lorsque les chercheurs délaissèrent les labyrinthes simples pour se tourner vers le jeu d'échecs, la géométrie des choix s'élargit de manière spectaculaire. Selon les récits du Computer History Museum, Shannon calcula qu'un joueur dispose en moyenne d'un facteur de ramification de 38 options légales par coup. Sur une partie classique de 42 coups, représentant 84 tours de jeu au total, l'arbre de décision se déploie en environ 10^34 séquences de coups possibles.

Cette explosion de possibilités rendait l'exploration par force brute totalement irréalisable sur le matériel informatique des années 1950. Les chercheurs réalisèrent rapidement qu'évaluer chaque branche jusqu'à la fin de la partie épuiserait la mémoire et le temps de calcul bien avant d'achever la moindre analyse.

Élaguer l'arbre grâce aux systèmes de symboles

Pour surmonter cet obstacle combinatoire, les pionniers de l'intelligence artificielle Herbert Simon et Alan Newell introduisirent la recherche heuristique afin d'élaguer les arbres de décision. Plutôt que de vérifier chaque coup valide, les heuristiques appliquaient des règles empiriques inspirées de l'expertise humaine pour ignorer d'emblée les trajectoires peu prometteuses.

La méthode la plus marquante fut l'élagage alpha-bêta. En détectant très tôt qu'un adversaire pouvait facilement parer une ligne donnée, l'algorithme éliminait toutes les sous-branches découlant de ce coup sans même avoir à les calculer. Cette technique permettait de réduire le facteur de ramification effectif d'une position de 38 à 6, voire jusqu'à 3 dans les configurations les plus favorables.

Le match transatlantique de 1967

Entre 1959 et 1962, des étudiants du MIT — Alan Kotok, Elwyn Berlekamp, Michael Lieberman, Charles Niessen et Robert Wagner — développèrent un programme d'échecs sous la direction de John McCarthy. En exploitant l'élagage alpha-bêta, le logiciel atteignit un niveau suffisant pour battre des joueurs amateurs au moment où ses concepteurs obtinrent leur diplôme.

En 1967, McCarthy organisa une confrontation par correspondance en opposant une version améliorée du programme de Kotok à des chercheurs soviétiques de l'Institut de physique théorique et expérimentale de Moscou (ITEP). Menée par George Adelson-Velsky, l'équipe soviétique aligna son propre logiciel. Après neuf mois de compétition, le programme de l'ITEP s'imposa face à son rival américain sur le score de 3 à 1.

Approfondissement itératif et matériel dédié

Lors de leur conférence du prix Turing en 1975, Newell et Simon formalisèrent l'hypothèse des systèmes de symboles physiques. Selon cette théorie, l'esprit humain comme la machine produisent une forme d'intelligence en manipulant des structures symboliques. Le jeu d'échecs servit alors de laboratoire concret pour cette conception de la cognition.

Les perfectionnements algorithmiques s'enchaînèrent. En 1976, David Slate et Larry Atkins introduisirent la recherche par approfondissement itératif dans Chess 4.5. En étendant progressivement la profondeur d'exploration le long des lignes prometteuses, Chess 4.5 devint le premier programme informatique à remporter un tournoi d'échecs humain ouvert.

L'évolution du matériel accompagnât rapidement ces avancées logicielles. En 1977, aux Bell Labs, Ken Thompson et Joe Condon conçurent Belle, une machine spécifiquement dédiée aux échecs intégrant des cartes électroniques sur mesure et des bases de données de finales spécialisées.

Ces travaux pionniers imposèrent la recherche heuristique et la manipulation symbolique comme les piliers de l'IA classique. En modélisant les choix sous forme d'arbres de décision maîtrisables, les chercheurs démontrèrent l'efficacité d'une résolution de problèmes structurée bien avant que l'augmentation brute de la puissance de calcul ne vienne redéfinir les échecs électroniques.

Illustration éditoriale générée par IA ; ce n’est pas une photographie documentaire.

Source: AI and Play, Part 1: How Games Have Driven Two Schools of AI Research