L'algorithme Minimax vu précédemment analysait tous les coups jouables de chacun des joueurs.
Ce type d'algorithme est très vorace en temps de calcul.
En effet, dans le jeu CRESUS, qui pourtant est très peu gourmand de ce point de vue, chacun des joueurs a, à son tour de jeu, un nombre de cases possibles qui varie de 8 (pire cas pour le seul premier coup) à une, selon la position (nombre de pièces non vides autour du jeton).
Si on suppose une moyenne de 4 possibilités par joueur, ce qui semble raisonnable en début de partie, on devrait analyser 4^prof feuilles de l'arbre pour creuser à une profondeur prof.
Par exemple, creuser de 40 coups (enlever la moitié seulement des pièces de monnaies) nécessiterait le cacul de 10^24 feuilles approximativement.
Même en disposant d'un ordinateur calculant mille milliards de feuilles par seconde, il faudrait environ mille milliards de secondes, à savoir plus de trente mille ans..
On conçoit aisément que pour creuser le plus profond possible, il faut éviter, autant que faire se peut, d'analyser tous les coups possibles.
La question est donc : peut-on obtenir le même résultat (ressortir le meilleur score au sens de notre heuristique ou stratégie) sans pour autant visiter toutes les feuilles de l'arbre ?
La réponse est bien évidemment oui et c'est ce que fait l'algorithme ALPHABETA.
Bien avant l'AlphaBeta, les chercheurs avaient remarqué que l'on pouvait éviter de balayer tout l'arbre, mais c'est réellement l'AlphaBeta qui a bien formalisé cet apport.
On considère que l'AlphaBeta a été décrit d'abord par Brudno, en 1963, mais la version expliquée ici, en notation Négamax est celle de Knuth et Moore.
Pour comprendre son fonctionnement, considérons le sous-arbre suivant (juste une partie d'un arbre plus complet).
|
o Joueur B
|-ß
+--+--+
| |-x<=-ß
o Joueur A
-ß |x>=ß
+-----------+
| | |
x>=ß ? ?
Feuilles inutiles
Le joueur B a dejà analysé complètement une des branches du noeud en haut. Appelons '-beta' le résultat de l'évaluation de cette sous branche, vue du point de vue du joueur B (On est en notation négamax...).
Le joueur B cherche maintenant à évaluer l'intérêt d'un autre de ses coups possibles, lui aussi issu de cette position (de ce noeud).
Il joue ce coup et passe le trait au joueur A.. en le prévenant qu'il a déjà trouvé une ligne de valeur '-beta'.
Pour le joueur A, de son propre point de vue, celà signifie que le joueur B peut, s'il le souhaite, choisir une ligne dont la valeur est beta... (Tout le monde suit encore ou je dois recommencer l'explication du négamax ?)
Maintenant, le joueur A va commencer à estimer chacun de ses coups possibles, en maximisant la note d'evaluation issue de ses sous-branches.
Ce qui est important c'est de constater que si le joueur A remonte une note d'évaluation supérieure ou égale à beta, il est inutile qu'il continue à explorer les coups suivants !
Pourquoi?
Simplement parce que si A trouve une réponse supérieure ou égale à beta, alors B, qui n'est pas si bête, préfèrera choisir l'autre ligne, de valeur beta, qu'il connait déjà et qui est meilleure pour lui.
Vu du joueur A, la valeur beta représente une note que le joueur B peut obtenir par ailleurs, contre toute attente, à savoir sans que le joueur A ne puisse s'y opposer.
Egaler ou améliorer cette note est inutile, à moins que le joueur B ne soit suicidaire (ce qui m'étonnerait de la part d'un ordinateur).
En réalité, on va faire redescendre à chacun des joueurs non pas une mais deux notes : ce sont les valeurs alpha et beta qui sont à l'origine du nom de l'algorithme : AlphaBeta.
La note alpha représente la meilleure note que le joueur (celui qui a le trait en notation négamax) a déjà trouvée, contre toute attente (l'adversaire ne peut s'y opposer).
La note beta représente, comme déjà annonçé, la meilleure note (du point de vue du joueur) que son adversaire peut jouer sans que lui, le joueur, ne puisse s'y opposer.
L'objectif du joueur est donc clair : faire mieux que alpha (donc trouver une meilleure suite encore) mais sans égaler ou dépasser beta (car alors cette suite est condamnée).
Vous trouverez un exemple en pseudo-code de l'algorithme AlphaBeta sur le Listing 5.
PS : les listings plus complets, en Pascal, se retrouvent dans l'unité JEU.PAS fournie en annexe.
Certains se demanderont peut-être à quoi peut bien servir la valeur alpha ?
En réalité, pour le joueur qui a le trait cette valeur ne sert à rien, dans le sens où elle ne provoque pas de coupure (elle ne permet pas de diminuer le nombre de coups du joueur).
Mais après qu'un joueur aie joué un coup, et passé le trait à l'autre, il devient l'adversaire... Et donc sa valeur alpha devient alors une valeur beta pour l'autre et peut ainsi provoquer une coupure (et vice versa : la valeur beta devient une valeur alpha).
La valeur alpha est donc très utile, car elle peut provoquer des coupures, mais à un niveau un peu plus profond dans l'analyse de chaque sous-branche.
Historiquement l'algorithme AlphaBeta n'a pas été décrit en notation Négamax, mais en double récursion (comme notre première version du minimax). Il y avait donc des coupures alpha et des coupures beta selon que c'était l'ordinateur ou le joueur humain qui avait le trait.
Vous trouverez souvent l'algorithme AlphaBeta décrit de cette façon.
En notation négamax (rappel notation non-raciste où l'on ne s'occupe plus de la couleur noire ou blanche du joueur ni de son statut d'ordinateur ou d'humain), il n'y a à proprement parler que des coupures beta.
En pratique, l'intérêt de l'AlphaBeta est non négligeable...
L'algorithme permet effectivement de réduire de beaucoup le nombre de feuilles explorées de l'arbre de jeu.. mais d'autant plus si on l'a mis en bonne condition.
En effet, revenons à notre joueur A qui évalue chacun de ses coups possibles, connaissant la valeur beta à ne pas dépasser.
Le nombre de sous-branches à ne pas explorer sera d'autant plus élevé que le joueur A a trouvé une valeur supérieure à beta très tôt dans la série de ses coups jouables.
Si la première suite de A explorée est déjà supérieure ou égale à beta, aucune autre ne sera testée. Par contre si on n'explore cette suite qu'en dernier alors que toutes les autres donnent un résultat inférieur à beta, c'est frustrant ! On se rend compte, mais un peu tard, qu'on vient de perdre du temps à visiter des branches inutiles.
C'est pour celà qu'il est primordial de ne pas tester chacun des coups possibles d'un joueur dans un ordre quelconque ! Mieux vaut commencer par les coups qui sont à priori les meilleurs, car ils ont plus de chance de provoquer une coupure.
Vous constaterez, sur le pseudo code décrit dans le listing de l'AlphaBeta, l'instance 'Cherche Et Classe' qui a pour but de trier les coups afin de les explorer dans un ordre judicieux.
Dans le cas de CRESUS, j'ai choisi de prendre d'abord les cases dont la valeur (pièce de monnaie) est la plus importante, qui sont à priori celles qui rapporteront le plus d'argent au joueur.
Moyennant cette précaution, l'algorithme AlphaBeta est vraiment plus efficace que le minimax.
Par exemple, pour CRESUS, les tests montrent qu'en moyenne calculer à 10 coups de profondeur avec l'AlphaBeta prend moins de temps que 6 coups avec le minimax..
En théorie, on peut montrer que le parcours de l'arbre est optimal lorsque le meilleur coup est toujours analysé en premier (si par exemple la routine Cherche Et Classe est parfaite).
On appelle cet arbre l'arbre minimal, et l'on peut montrer que dans le cas d'une divergence W (nombre de coups possibles à chaque noeud par joueur) et une recherche à une profondeur P, le nombre de feuilles vaut (réf Pearl) :
2 WP/2 - 1 à comparer avec WP du minimax.
Avec notre exemple dejà cité (W=4), on obtient
| Profondeur | Minimax | AlphaBeta |
| 6 | 4096 | 129 |
| 8 | 65536 | 513 |
| 10 | 1048576 | 2049 |
Bien que l'arbre minimum ne soit jamais atteint en pratique, on comprenda aisément l'intérêt des coupures AlphaBeta...
Pour reprendre le cas d'un hypothétique ordinateur évaluant mille milliards de feuilles par secondes, avec un AlphaBeta optimal, l'ordinateur parviendrait à résoudre le problème de 40 coups en 2 secondes !
Lorsque la routine "cherche et classe" n'est pas optimale, par exemple dans le cas d'un tirage aléatoire des coups à jouer, l'évolution du nombre de feuilles avec la profondeur suit une loi proportionnelle à W^3P/4 de toute façon plus favorable que le minimax.
L'ordinateur mettrait alors 11 jours pour évaluer les 40 coups.