Bien souvent (à mon gout) les explications de l’algorithme alpha-beta manquent de détails. On comprend bien qu’il y a un gain par rapport au mini-max mais on ne sait pas trop comment le formaliser. Je vais donc essayer de synthétiser en détails !
Il faut bien comprendre que l’arbre des positions n’est pas construit dans un premier temps puis analysé dans un second temps. Ce serait très couteux en temps et en mémoire, ce n'est pas nécessaire et de toute façon le but de l'alpha-beta c'est d'en faire le moins possible. L'arbre est analysé au fur et à mesure qu’il est découvert. Ce qui signifie que l’analyse mini-max (ou alpha-beta) n’a qu’une vue partielle de l’arbre.
Par convention, la valeur d’une position dans le graphe est la valeur que lui attribue celui qui a le trait. Autrement dit la valeur d’une position est le gain qu’espère en tirer celui qui doit jouer à partir de cette position.
Étape 1
Vert
fait face à la position P0. Soit c’est la position de départ du jeu,
soit Rouge vient de jouer et laisse le trait à Vert. Quel gain Vert
peut-il espérer tirer de cette position ?
Vert analyse la position P1.1 résultant de son premier coup possible, V1.
Pour juger de la qualité de cette position P1.1, Vert se demande quelles sont les ripostes possibles de Rouge.
Il analyse le coup R1 de Rouge. Qui redonnerait le trait à Vert non plus en position P0 mais en position P2.1. Après analyse (récursive) de la position P2.1 Vert considère que cette position P2.1 vaut -5 points.
Mais, comme dans les jeux à somme nulle ce qui est bon pour l’un ne l’est pas pour l’autre, les -5 points pour Vert sont en fait +5 points pour Rouge. Donc pour le moment la position P1.1, vaut du point de vue de Rouge, +5 pts.
Puis Verts envisage le coup R2 de Rouge qui débouche sur la position P2.2 qui, du point de vue de Vert faut +1 points. Ce qui est mieux que les -5 pts de la position P2. Malheureusement pour Vert, entre R1 et R2 Rouge choisira le coup qui mène à la position la plus forte de son point de vue, donc R1. Donc la position P1.1 continue de garder un potentiel de +5 pour Rouge.
Enfin, Vert envisage le coup R3 de Rouge qui débouche sur la position P2.3 qui, du point de vue de Vert faut -7 points, et donc +7 points pour Rouge. Bien sûr Rouge préférera ce coup R3 au coup R1 jusqu’à maintenant retenu. Donc la valeur de la position P1.1 passe de +5 à +7.
Première synthèse : Si Vert joue le coup V1, la position P1.1 qui en résulte vaut, compte tenu de la meilleure riposte de Rouge, +7 points. Et donc -7 pour Vert ce qui est pour le moment la valeur de P0.
Étape 2: mini-max
Vert analyse maintenant son deuxième coup possible à savoir V2. Pour juger de la position P1.2 ainsi obtenue il va étudier les ripostes possibles de Rouge.
Si on faisait le même raisonnement pour P1.2 que pour P1.1, mais avec les valeurs ci-dessous, on trouverait qu’après avoir pris la valeur -3 puis la valeur +9 la valeur de la position P1.2 serait de +9 pour Rouge. Ce qui reviendrait à -9 points pour Vert. Et comme Vert a un le coup V1 qui vaut -7 il ne jouera jamais le coup V2 qui vaut -9 donc encore plus mauvais que V1.
Si on faisait ainsi on serait dans la pure logique du mini-max : chacun maximise ses gains que l’autre cherche à minimiser. Mais en appliquant exactement la même logique à P1.2 qu’a P1.1 on ne profite pas pendant l'analyse de P1.2 de ce que l’on a appris pendant l'analyse de P1.1.
Étape 3: alpha-beta
Reprenons l’analyse de P1.2. On sait qu’après l’analyse du coup V1 la position P0 vaut -7 et que ce que cherche Vert c’est un coup meilleur que -7. Donc tant que P1.2 à une valeur meilleure (du point de vue de Vert) que -7 c’est qu’on est en bonne voie pour que V2 remplace V1.
C’est ce qui ce passe après l’analyse de R4. La valeur de la position P2.4 est de +3 points pour Vert, donc de -3 points pour Rouge au niveau de P1.2, donc à nouveau de +3 points pour Vert (au niveau de P0). A ce stade la séquence (V2 ; R4) semble meilleure que (V1 ; R3).
Mais quand on analyse P2.5 découlant du coup R5 on se retrouve avec une valeur de P1.2 de +9 et donc de -9 pour Vert au niveau P0. Bien sûr jamais Vert ne jouera V2 s’il s’expose à une riposte de Rouge valant -9, alors que Vert a déjà une meilleure solution qui vaut -7.
Tout cela on le sait au moment où on découvre que V2 mène à une situation pire que ce que l’on obtiendrait avec V1. On peut donc arrêter d’analyser les autres coups découlant de P1.2 puisque déjà Rouge à la réponse qui tue au niveau de P1.2. Inutile de chercher et d'analyser les autres coups valides après R5.
Important: Si l’on avait analysé R5 en premier on aurait immédiatement abandonné l’analyse de P1.2. Mais si on avait découvert R5 en dernier on n’aurait fait aucune économie.
- L’ordre d’analyse des coups a donc un impact sur les possibilités d’élagage de cette méthode.
- De plus cette méthode n’est pas applicable pendant l’analyse du premier coup (V1) puisque on n’a aucun repère.
- Enfin l’élagage n’est possible que si on analyse à au moins 2 coups de profondeur puisque l’élagage a lieu dans l’analyse des ripostes en se basant sur ce que vaut la position initiale.
De bas en haut, puis de haut en bas :
Au début de l’analyse de P0 (coup V1) on a descendu l’arbre, puis on a analysé les feuilles, puis en remontant on a pu attribuer une valeur à chaque position en utilisant la méthode mini-max : Vert maximise ses gains alors que Rouge minimise les gains de Vert.
Mais dans la suite de l’analyse de P0 (coup V2) on peut, en descendant l’arbre, faire descendre l’information comme quoi Vert cherche un coup meilleur que -7 et que l’on doit abandonner l’analyse d’un coup de Vert dès que l’on sait que sa valeur serra inférieure à cette limite.
L’informatique n’aime pas les cas particuliers :
L’idée que pendant l’analyse du premier coup on ne puisse pas analyser les coups avec la même méthode que pour les autres coups est fort déplaisante à l’informaticien… On va donc harmoniser ces deux situations.
On va analyser le premier coup en faisant comme si l’on avait déjà en notre possession un coup minable dont la note est -1000. On va donc descendre l’arbre dès le premier coup en disant «
je cherche pour Vert meilleur que -1000 », tout comme on descend l’arbre au deuxième coup en disant «
je cherche un coup meilleur que -7 ». La tradition informatique appelle cette information ‘
alpha’ : «
Je cherche un coup meilleur que alpha ». La valeur initiale d’alpha doit représenter une valeur pire que le pire de tous les coups possible pendant le jeu. On aurait envie de dire moins l’infini, mais l’infini n’existe pas en informatique…
Et Rouge dans tout ça ?!
Nous avons raisonné en partant d’une position P0 où Vert avait le trait. Mais après le coup V1 c’est Rouge qui a le trait face à la situation P1.1. Rien n’empêche de raisonner à partir de P1.1 comme nous l’avons fait à partir de P0, mais en respectant le point de vue de Rouge, qui est l’opposé de celui de Vert.
Rouge descendra donc l’arbre en disant «
je suis à la recherche d’un coup meilleur que ‘beta’ ». On utilise ‘beta’ pour Rouge afin de ne pas le confondre avec le seuil ‘alpha’ de Vert.
Nous avons donc nos deux adversaires qui descendent l’arbre à la recherche d’un meilleur coup qu’alpha pour l’un, que beta pour l’autre.
Et voilà, vous avez l’algorithme alpha-bêta
01 fonction alpha_beta(Position, profondeur, α, β, couleur)
02 si est_terminal(Position, profondeur, couleur) alors
03 retourner évaluer(Position, couleur)
04 finsi
05
06 pour chaque Enfant de Position faire
07 score := − alpha_beta(Enfant, profondeur+1, −β, −α, -couleur)
08 si score ≥ β alors
09 retourner score # élagage α/β
10 finsi
11 si score > α alors
12 α = score # max du mini-max
13 finsi
14 finpour
15
16 retourner α
17 fin
Attention aux détails !
Ligne #03: l'évaluation de la position est faite du point de vue du joueur courant. Peut importe que ce soit le programme ou son adversaire.
Ligne #07; Notez bien les 4 changements de signes et le changement de position de
α et β.
Les 3 premiers changements signes viennent du fait que ce qui est bon pour l'un est mauvais pour l'autre. (- couleur voulant dire la couleur opposée)
