“Pour qu’un ordinateur gagne aux échecs, il suffit que celui-ci teste toutes les possibilités.”

7 min readNov 24, 2017

Une phrase déjà entendue maintes fois lors de discussions sans fondement : est-ce que l’ordinateur peut, ou devrait, utiliser un algorithme qui testera toutes les possibilités qui s’offriraient à lui lors d’une partie d’échecs?

On pourrait donner un autre titre à cet article : “Pourquoi a-t-on besoin de l’intelligence artificielle dans les jeux (observable)?”. Discutons-en!

Premièrement, nous allons expliquer ce qu’est un “facteur de branchement” un terme qui sera utilisé de nombreuses fois dans cet article.

Un facteur de branchement est, en mathématique / informatique, le nombre d’enfants disponibles dans un arbre de données pour chaque nœud.

Arbre avec un facteur de branchement de valeur 2

Concrètement, lorsque c’est au tour d’un joueur, il se trouve à un nœud (les ronds ci-dessus); les enfants, sont alors le nombre de possibilités accessibles pour passer à l’étape suivante. Pour le jeu “pile ou face”, le facteur de branchement sera alors de deux, étant donné que lorsque c’est au tour d’une personne de jouer, le lancer de pièce ne pourra donner que 2 possibilités : pile ou face.

Il est évident que dans les jeux, même simples, le nombre d’enfants disponibles peut être différent en fonction de la position où on se trouve. Pour l’illustrer, prenons le jeu “Taquin”, celui où vous devez glisser des pièces pour les remettre dans l’ordre.

A la position où il n’y a pas de pièce (la case noire), il est possible de faire deux déplacements, soit glisser la pièce numéro 7, soit glisser la pièce numéro 8.
Par contre, si le trou avait été à la position de la case portant le nombre 3, nous aurions eu alors 4 possibilités, glisser la pièce de gauche, de droite, du haut ou encore celle du dessous. Ainsi, en fonction de la position où le joueur se trouve, le facteur de branchement diffère. C’est pourquoi, pour chaque jeu, il existe un facteur de branchement moyen.

Maintenant que nous avons établi ce qu’est un facteur de branchement, nous pouvons comprendre ce que cela coûte de vérifier toutes les positions d’un jeu. Nous pourrons ainsi comprendre si la technique “brute force”, c’est-à-dire de vérifier toutes les possibilités, est une option envisageable.

Le Rubik’s Cube

Commençons par le Rubik’s Cube 3*3*3, un jeu que vous connaissez probablement déjà. Composé, par face de 3 rangées et 3 colonnes.
Calculons le facteur de branchement de celui-ci :

Le problème de dénombrement est assez simple : pour chaque face, nous pouvons à la position P, effectuer une rotation de 90°, 180° ou 270° (une rotation de 360° n’aurait pas d’intérêt puisqu‘elle nous ferait revenir à la position de départ). Il est donc possible de procéder à 3 mouvements par face, le jeu en est composé de 6.

6 faces * 3 rotations = un facteur de branchement de 18

Notez que le facteur de branchement pour le Rubik’s Cube est uniforme, il n’existe pas une position ou nous n’aurions pas le droit d’effectuer ces 18 mouvements.

Maintenant que ceci est établi, calculons le nombre de possibilités. Nous sommes au départ, et nous allons donc faire un mouvement et descendre sur un des enfants nœuds (cf. l’arbre), il existe alors 18 possibilités. Écrivons donc un tableau avec toutes ces possibilités :

Étapes => nombre de nœuds à vérifier
Étape 1 => 18
Pour la deuxième étape, il faut compter les 18 nœuds précédents auxquels s’ajoutent les 18² suivants
Étape 2 => 18 + 324 = 342
Étape 3 => 342 + 5832 = 6 174
4 => 6 174 + 104 976 = 111 150
5 => 111 150 + 1 889 568 = 2 000 718
6 => 2 000 718 + 34 012 224 = 36 012 942
7 => 36 012 942 + 612 220 032 = 648 232 974
8 => 648 232 974 + 11 019 960 576 = 11 668 193 550
9 => 11 668 193 550 + 198 359 290 368 = 210 027 483 918
10 => 210 027 483 918 + 3 570 467 226 624 = 3 780 494 710 542

Si la solution se trouvait à la 10e étape, l’algorithme de parcourt d’arbre devrait tester plus de trois mille milliards de possibilités. En admettant que l’ordinateur prendra 1 seconde pour parcourir 1 milliard de configurations (ce qui n’est pas jouable avec les ordinateurs personnels), il prendra plus de 3000 secondes pour trouver une solution.

Attention, il est bien évident qu’ici, les nœuds qui auraient déjà la même disposition qu’un nœud déjà exploré sont inclus dans le comptage. Le but est de donner un ordre de grandeur au problème. De plus, si nous voulions élaguer des branches de l’arbre (c’est à dire éliminer des possibilités enfants suite à une configuration existante déjà traitée) nous devrions aussi prendre en compte le stockage des informations pour chacune des dispositions.

Nous allons maintenant parler des jeux plus complexes comme le jeu d’échecs et celui de go ce dernier dont on parle tellement en ce moment.

Le jeu d’échecs a un facteur de branchement moyen de 35 [1] calculons ce que cela donne.

A la profondeur 10 il faudra explorer 2 839 681 099 207 260 nœuds
Alors qu’à la position 35 il faudra en parcourir 1.1349341905116*10⁵⁴ autrement dit : 1 134 934 190 511 600 000 000 000 000 000 000 000 000 000 000 000 000 000. En suivant la même logique qu’auparavant dans la vitesse d’exploration : si un ordinateur parcourt 10⁹ nœuds à la seconde, nous allons alors diviser ce nombre par 10⁹ * 3600 * 24 * 365 (heure*jour*nombre). Le résultat de ce calcul est

35 988 527 096 385 083 713 850 837 138 508 371 385 années

Une partie d’échec avec pendule [2] est limité dans le temps, chacun des joueurs a un temps pour déplacer ses pièces pour toute la partie (les temps peuvent varier: 1 min, 5 min, 30 min, …) c’est pour cela qu’ils doivent , à chaque mouvement, appuyer (frapper?) sur cette horloge afin que leur propre chrono s’arrête et que celui du joueur adverse continue, si vous n’avez plus de temps, vous avez perdu.

Dans ces conditions, il est facilement compréhensible que, même à faible profondeur (disons 6 coups d’avance, ce qui représente quand même 1 892 332 260 possibilités), il ne soit pas efficace de tester de manière “brute force” l’arbre jusqu’à ce niveau.

On pourrait se demander quel est le nombre moyen de mouvements total nécessaire afin de terminer une partie d’échecs. Selon la source trouvée sur un post de stackoverflow , où l’utilisateur Andrew Ng est allé tirer des statistiques de la “Mega Database 2017”, ce nombre est de 37.

Le jeu de go [3] est populaire en cette fin 2017; nous reparlerons en fin d’article de tout l’émoi qu’il suscite.

Maintenant que vous êtes familiarisé avec les facteurs de branchements, la “démonstration” sera facile à appliquer.

Le facteur de branchement du jeu de go est de 250. Reprenons les mêmes profondeurs estimées que dans le jeu d’échec :
Pour une profondeur de 10 il faudra parcourir 9,5750433374121*10²³ nœuds et pour une profondeur de 35 : 8,5043468599829*10⁸³ possibilités.

Afin de nous représenter cette quantité, rappelons que le nombre d’atomes total estimé dans l’univers est de 10⁸⁰ [4]

La moyenne de mouvements pour terminer une partie de go est de 210 [6]

Vous l’avez compris, vu le nombre de possibilités existantes, parcourir l’arbre des possibilités est quasi impossible en matière de temps. De plus, rappelons que nous n’avons pas pris en compte la place (stockage d’information) que cela demanderait de retenir chaque possibilité de la position des pions sur le plateau, c’est pourquoi la technique “brute force” n’est pas applicable.

Pourquoi nous parlons autant du jeu de go en ce moment ?
D’abord, en mai 2017 , un des tops champion mondial de go, Ke Jie, a été battu par AlphaGO. Vous pouvez lire l’article et même revoir la partie.
Ensuite, AlphaGo Zero fait surface, apprenant par lui-même (c’est-à-dire en jouant contre lui-même) tout ce qu’il doit savoir sur ce jeu. Énormément d’articles parlent de ce succès de l’intelligence artificielle, vous trouverez toute cette littérature sur votre moteur de recherche préféré.

Conclusion

Vous l’avez maintenant compris, pour qu’un ordinateur puisse gagner contre une personne entraînée dans ces disciplines, il ne peut pas se contenter de simplement tester naïvement toutes les possibilités. C’est pourquoi, nous avons besoin de techniques différentes appliquées par l’intelligence artificielle, telles que les Machine learning, deep learning, de metaheuristic, …
Ces sujets sont vastes, souvent compliqués. Le but de cet article était de comprendre les enjeux de ces techniques dont on parle tant.

“Pour qu’un ordinateur gagne aux échecs, il suffit que celui-ci teste toutes les possibilités.”

Le Rubik’s Cube

Conclusion

Sources

Written by Brieuc Barthélemy