L'alpha-bêta
Nous avons vu que la méthode du Minimax nous permettait de remonter avec certitude le meilleur choix, mais nous n'avons pas résolu le problème du nombre gigantesque de possibilités à examiner.
Faut-il examiner toutes les solutions ? Et bien je vous rassure tout de suite : non, il existe une méthode miracle qui permet d'élaguer à coup sûr dans l'arbre touffu des possibilités : il s'agit de l'alpha-bêta.
Le principe est le suivant : si, sur un coup, l'adversaire a une possibilité de réponse qui rend ce coup mauvais, il est inutile d'examiner les autres possibilités de réponse à ce même coup, puisqu'il ne les choisira que si elles sont pires.
Ceci n'est peut-être pas très clair, aussi nous illustrer le propos par l'exemple que vous avez studieusement préparé pour cette leçon (après la leçon de la dernière fois).
Examinons le schéma n° 6 bis (qui est le même que le 6 pour ceux qui ne l'auraient pas remarqué, ce qui signifierait qu'ils n'auraient peut-être pas été aussi studieux que je l'espérais).
Schéma n° 6 bis
L'ordinateur examine, comme on le lui a appris, la première extrémité de branche. Il trouve 2, qu'il remonte en C1. La valeur suivante est 1, l'ordinateur juge inutile de la remonter puisque C1 est un niveau maximisant et que la valeur actuelle, 2, est supérieure. La valeur suivante est 5, qu'on remonte en C1 et qui prend la place de 2.
L'examen de la branche issue de C1 est terminé, nous pouvons remonter provisoirement la valeur 5 en B1, et examiner la branche issue de C2.
La première valeur trouvée est 6, que l'on remonte provisoirement en C2. C'est à ce point qu'intervient alpha-bêta. En effet, C2 est un niveau "maximisant" (l'ordinateur choisit, et prend la meilleure solution). Donc la valeur qui sera retenue sera au moins égale au 6 déjà trouvé.
Par contre, le niveau B1 est un niveau minimisant (l'adversaire choisit, et prend la plus mauvaise solution vue de l'ordinateur). La valeur issue de C2 (6 ou plus) ne sera jamais retenue puisque la valeur issue de C1 (5) est inférieure. Il est donc inutile de poursuivre plus avant l'examen des autres branches issues de C2.
De même, la première branche issue de C3 donne 8, ce qui implique que l'ordinateur n'ira jamais dans cette direction (il préférera la branche C1). Cela élimine donc cette branche.
Nous avons donc terminé l'examen des branches issues de B1. Retenons 5 comme valeur d'évaluation que nous remontons provisoirement en A.
Nous examinons les branches issues de B2, en commençant par C4. L'examen des 3 valeurs est nécessaire, et nous remontons en C4 la valeur la plus élevée, 4.
B2 étant un niveau minimisant, nous en déduisons que la valeur définitive sera inférieure ou égale à 4.
A est par contre un niveau maximisant, qui a déjà provisoirement la valeur 5. La valeur issue de B2 (4 ou moins) ne présentera donc pas d'intérêt, car si l'ordinateur s'oriente vers là, il sait que l'adversaire peut l'amener à une position de valeur 4 (ou moins). La branche B2 peut d'ores et déjà être éliminée, car moins intéressante que B1, qui, si l'adversaire répond au mieux, amènera au pire à une position valant 5.
De même, les valeurs 2, 1, 3 issues de C7 permettent de remonter 3 en B3, et d'éliminer B3 pour les mêmes raisons sans poursuivre l'examen des autres parties de cette branche.
Au total, nous avons examiné 11 positions, sur 27 possibles, soit un gain de 60%, et nous avons trouvé 16 positions inutiles à étudier, leurs valeurs ne changeant pas le choix final. Pour ceux qui attendent le résultat de l'exercice du précédent chapitre, je peux donc dire que 16 est la bonne réponse, et je félicite les heureux gagnants.
L'exemple que nous avons choisi était particulièrement favorable, puisque les "bonnes" valeurs étaient trouvées dès le début (en fait, nous devions arriver au résultat en un nombre d'évaluations compris entre 11 et 27). L'alpha-bêta permet toujours un gain de temps plus important quand les solutions les meilleures sont examinées d'abord. Cette propriété est utilisée par d'autres algorithmes, qui cherchent à ordonner les solutions selon leur valeur probable avant de les examiner vraiment. Plusieurs méthodes sont utilisées pour cela, mais je n'en citerai que deux :
* La méthode des coups meurtriers, qui consiste à essayer en premier les coups qui ont déjà, dans d'autres branches, permis des élagages alpha-bêta. Ce sont souvent des départs de combinaison, que l'on retrouve plusieurs fois sauf si l'on bouche le "trou", et il est naturel de chercher à savoir si le mouvement que l'on a fait maintient ou élimine la menace qui existait auparavant ; s'il la maintient, cela permet d'éliminer rapidement la branche.
* La recherche itérative, sur laquelle je reviendrai plus tard, dans le cadre d'un autre de ses avantages.
Le gain final dans le cas d'un arbre ordonné est appréciable : si d est le nombre de branches par niveaux, et p le nombre de niveaux, le nombre minimal d'évaluations est de l'ordre de 2 d p/2, alors que le nombre maximal d'évaluations (correspondant à toutes les branches) est d p (soit un gain de 0,5 d p/2).
Le gain généralement constaté se situe entre les deux, et est d'autant plus important que le nombre de niveaux examinés est élevé.
Différents essais effectués sur DAMES 2020, puis sur QUIDAM, qui effectuent des évaluations jusqu'à des niveaux 20, me font estimer le gain moyen à plus de 80% du temps de calcul.
Quelle a été la démarche ? Et bien nous avons arrêté les calculs lorsque les valeurs remontées ont été inférieures à une borne minimale (appelée alpha) aux niveaux maximisants (choix du coup du ressort de l'ordinateur), ou supérieures à une borne maximale (appelée bêta) aux niveaux minimisants (choix du coup du ressort de l'adversaire).
Je vous conseille, pour bien comprendre cette démarche fondamentale, de faire plusieurs essais avec des valeurs différentes en bout d'arbre, et éventuellement de comparer à des évaluations menées sans effectuer d'élagage alpha-bêta, pour vérifier que l'élagage ne perturbe absolument pas le résultat.
D'autres types d'élagages sont possibles, mais ils sont moins "logiquement purs" que alpha-bêta.
Certains peuvent néanmoins le compléter, et nous examinerons plus loin ceux qui peuvent être mis en jeu avant l'évaluation statique (donc pendant la démarche dynamique), que nous appellerons élagages préalables.