Conditions préalables: Algorithme Minimax dans la théorie des jeux , Fonction d'évaluation en théorie des jeux
L'élagage alpha-bêta n'est pas réellement un nouvel algorithme, mais plutôt une technique d'optimisation pour l'algorithme minimax. Cela réduit considérablement le temps de calcul. Cela nous permet de chercher beaucoup plus rapidement et même d'accéder à des niveaux plus profonds dans l'arbre du jeu. Il coupe les branches de l'arbre du jeu qui n'ont pas besoin d'être recherchées car il existe déjà un meilleur coup disponible. On l'appelle élagage Alpha-Beta car il transmet 2 paramètres supplémentaires dans la fonction minimax, à savoir alpha et bêta.

Définissons les paramètres alpha et bêta.

Alpha est la meilleure valeur que le maximiseur peut actuellement garantir à ce niveau ou au-dessus.
Bêta est la meilleure valeur que le minimiseur peut actuellement garantir à ce niveau ou en dessous.

Pseudocode :

 function minimax(node, depth, isMaximizingPlayer, alpha, beta): if node is a leaf node : return value of the node if isMaximizingPlayer : bestVal = -INFINITY for each child node : value = minimax(node, depth+1, false, alpha, beta) bestVal = max( bestVal, value) alpha = max( alpha, bestVal) if beta <= alpha: break return bestVal else : bestVal = +INFINITY for each child node : value = minimax(node, depth+1, true, alpha, beta) bestVal = min( bestVal, value) beta = min( beta, bestVal) if beta <= alpha: break return bestVal>

 // Calling the function for the first time. minimax(0, 0, true, -INFINITY, +INFINITY)>

Expliquons clairement l'algorithme ci-dessus avec un exemple.

• L'appel initial commence à partir de UN . La valeur de alpha ici est -INFINI et la valeur de bêta est +INFINI . Ces valeurs sont transmises aux nœuds suivants de l'arborescence. À UN le maximiseur doit choisir un maximum de B et C , donc UN appels B d'abord
• À B le minimiseur doit choisir min de D et ET et donc appelle D d'abord.
• À D , il regarde son enfant gauche qui est un nœud feuille. Ce nœud renvoie une valeur de 3. Maintenant, la valeur de alpha à D est max( -INF, 3) qui vaut 3.
• Pour décider si cela vaut la peine de regarder son nœud droit ou non, il vérifie la condition beta<=alpha. C'est faux puisque beta = +INF et alpha = 3. On continue donc la recherche.
D regarde maintenant son enfant de droite qui renvoie une valeur de 5. D , alpha = max(3, 5) qui vaut 5. Maintenant la valeur du nœud D est 5 D renvoie une valeur de 5 à B . À B , beta = min( +INF, 5) qui vaut 5. Le minimiseur se voit désormais garantir une valeur de 5 ou moins. B appelle maintenant ET pour voir s'il peut obtenir une valeur inférieure à 5.
• À ET les valeurs de alpha et bêta ne sont pas -INF et +INF mais plutôt -INF et 5 respectivement, car la valeur de bêta a été modifiée à B et c'est quoi B transmis à ET
• Maintenant ET regarde son enfant gauche qui a 6 ans. ET , alpha = max(-INF, 6) qui vaut 6. Ici, la condition devient vraie. beta est 5 et alpha est 6. Donc beta<=alpha est vrai. Donc ça casse et ET renvoie 6 à B
• Notez que la valeur de ET C’est l’enfant qui a raison. Cela aurait pu être +INF ou -INF, cela n'aurait toujours pas d'importance, nous n'avons même jamais eu à le regarder car le minimiseur était garanti d'une valeur de 5 ou moins. Ainsi, dès que le maximiseur a vu le 6, il a su que le minimiseur ne viendrait jamais par là car il peut obtenir un 5 sur le côté gauche de B . De cette façon, nous n’avons pas eu à regarder ce 9 et avons donc économisé du temps de calcul.
E renvoie une valeur de 6 à B . À B , beta = min( 5, 6) qui est 5. La valeur du nœud B est aussi 5

Jusqu’à présent, voici à quoi ressemble notre arbre de jeu. Le 9 est barré car il n’a jamais été calculé.

B renvoie 5 à UN . À UN , alpha = max( -INF, 5) qui vaut 5. Le maximiseur a désormais la garantie d'une valeur de 5 ou plus. UN appelle maintenant C pour voir s'il peut obtenir une valeur supérieure à 5.
• À C , alpha = 5 et bêta = +INF. C appels F
• À F , alpha = 5 et bêta = +INF. F regarde son enfant de gauche qui est un 1. alpha = max( 5, 1) qui est toujours 5.
F regarde son enfant droit qui est un 2. La meilleure valeur de ce nœud est donc 2. Alpha reste toujours 5 F renvoie une valeur de 2 à C . À C , bêta = min( +INF, 2). La condition beta <= alpha devient vraie lorsque beta = 2 et alpha = 5. Donc ça casse et il n'est même pas nécessaire de calculer l'intégralité du sous-arbre de g .
• L'intuition derrière cette rupture est qu'à C le minimiseur avait une valeur garantie de 2 ou moins. Mais le maximiseur avait déjà la garantie d'une valeur de 5 s'il choisissait B . Alors pourquoi le maximiseur choisirait-il C et obtenir une valeur inférieure à 2 ? Encore une fois, vous pouvez voir que ces 2 dernières valeurs n'avaient pas d'importance. Nous avons également économisé beaucoup de calculs en sautant un sous-arbre entier.
C renvoie désormais une valeur de 2 à UN . Par conséquent, le meilleur rapport qualité-prix à UN est max( 5, 2) qui est un 5.
• La valeur optimale que peut obtenir le maximiseur est donc 5.

Voici à quoi ressemble notre arbre de jeu final. Comme vous pouvez le voir g a été barré car il n’a jamais été calculé.

RPC

>

image comme arrière-plan en CSS

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

stdin en c

>

>

The optimal value is : 5>