Alpha Bêta

L’élagage alpha-bêta est une technique qui permet d’accélérer la recherche du meilleur coup dans un jeu à deux joueurs, comme les échecs, le dames, ou le tic-tac-toe. Un jeu à deux joueurs peut être représenté par un arbre, où chaque nœud est une position du jeu, et chaque branche est un coup possible. La racine de l’arbre est la position actuelle, et les feuilles sont les positions finales, où le jeu est terminé. Chaque feuille a une valeur, qui indique le résultat du jeu pour le joueur qui commence : une valeur positive signifie une victoire, une valeur négative signifie une défaite, et une valeur nulle signifie une égalité. L’objectif est de trouver le coup qui mène à la feuille avec la valeur la plus élevée. Pour cela, on utilise un algorithme appelé minimax, qui consiste à explorer l’arbre en alternant les rôles de maximiseur et de minimiseur.

Le maximiseur cherche à maximiser la valeur du jeu, et le minimiseur cherche à minimiser la valeur du jeu. A chaque nœud, on calcule la valeur du jeu en fonction des valeurs des nœuds fils, en appliquant la règle suivante : si c’est le tour du maximiseur, on choisit la valeur maximale parmi les fils, et si c’est le tour du minimiseur, on choisit la valeur minimale parmi les fils. L’élagage alpha-bêta est une amélioration du minimax, qui permet d’éviter d’explorer des branches inutiles, c’est-à-dire qui ne vont pas changer la valeur du jeu. Pour cela, on utilise deux paramètres, appelés alpha et bêta, qui représentent respectivement la meilleure valeur trouvée par le maximiseur et la meilleure valeur trouvée par le minimiseur. A chaque nœud, on compare la valeur du jeu avec alpha et bêta, et on coupe la branche si on trouve une contradiction. Par exemple, si on trouve une valeur supérieure à bêta, cela signifie que le minimiseur ne va jamais choisir cette branche, car il a déjà trouvé une valeur plus petite.

De même, si on trouve une valeur inférieure à alpha, cela signifie que le maximiseur ne va jamais choisir cette branche, car il a déjà trouvé une valeur plus grande. L’élagage alpha-bêta permet de réduire le nombre de nœuds à explorer, et donc de gagner du temps et de la mémoire.

Exemple :

Imaginez que vous jouez au jeu du pile ou face, où le joueur qui commence choisit pile ou face, et le joueur qui suit doit deviner le résultat du lancer de pièce. Vous voulez savoir quelle est la meilleure stratégie à adopter, en supposant que votre adversaire joue aussi de manière optimale. Vous pouvez utiliser l’élagage alpha-bêta pour cela. Voici comment procéder :

• Vous représentez le jeu par un arbre, où chaque nœud est une situation du jeu, et chaque branche est un choix possible. La racine de l’arbre est la situation initiale, où aucun choix n’a été fait. Les feuilles sont les situations finales, où le jeu est terminé. Chaque feuille a une valeur, qui indique le résultat du jeu pour vous : +1 pour une victoire, -1 pour une défaite, et 0 pour une égalité. Voici un exemple d’arbre pour le jeu du pile ou face
• Vous initialisez alpha à -∞ et bêta à +∞. Vous commencez par le nœud racine, qui est votre tour. Vous explorez les nœuds fils, en choisissant le meilleur choix pour vous, et en coupant les branches inutiles. Vous obtenez le schéma suivant
• Vous commencez par le nœud B, qui est le tour de votre adversaire. Il a deux choix possibles : deviner pile ou deviner face. Vous explorez les nœuds fils, en choisissant le meilleur choix pour votre adversaire, et en coupant les branches inutiles. Vous obtenez le schéma suivant
• Vous remontez au nœud B, qui a la même valeur que son meilleur fils, c’est-à-dire -1. Vous mettez à jour la valeur de A, qui est le maximum entre sa valeur actuelle et la valeur de B, c’est-à-dire -1. Vous mettez aussi à jour alpha, qui est le maximum entre sa valeur actuelle et la valeur de A, c’est-à-dire -1. Vous obtenez le schéma suivant
• Vous passez au nœud C, qui est le tour de votre adversaire. Il a deux choix possibles : deviner pile ou deviner face. Vous explorez les nœuds fils, en choisissant le meilleur choix pour votre adversaire, et en coupant les branches inutiles. Vous obtenez le schéma suivant
• Vous remontez au nœud C, qui a la même valeur que son meilleur fils, c’est-à-dire +1. Vous mettez à jour la valeur de A, qui est le maximum entre sa valeur actuelle et la valeur de C, c’est-à-dire +1. Vous mettez aussi à jour alpha, qui est le maximum entre sa valeur actuelle et la valeur de A, c’est-à-dire +1. Vous obtenez le schéma suivant
• Vous avez exploré tous les nœuds fils de A, et vous avez trouvé la meilleure valeur pour A, qui est +1. Vous avez donc trouvé le meilleur choix pour vous, qui est de choisir face. Vous pouvez couper les autres branches, car elles ne vont pas changer la valeur du jeu. Vous obtenez le schéma final suivant :

Retourner à l'index du lexique