L'élagage alpha-bêta est un algorithme de recherche dans un arbre qui cherche à diminuer le nombre de nœuds évalués par l'algorithme minimax dans son arbre de recherche. C'est un algorithme de recherche adversarial couramment utilisé pour la pratique machine de jeux combinatoires à deux joueurs tels que le Tic-tac-toe, les échecs et le Puissance 4. L'algorithme cesse d'évaluer un coup lorsqu'au moins une possibilité a été trouvée qui prouve que le coup est pire qu'un coup précédemment examiné, de sorte que de tels coups n'ont pas besoin d'être évalués plus avant. Lorsqu'il est appliqué à un arbre minimax standard, il retourne le même coup que minimax le ferait, mais élague les branches qui ne peuvent pas influencer la décision finale.
L'algorithme est un exemple classique d'une approche de branchement et de bornage dans Artificial intelligence, et il sous-tend de nombreux programmes de jeu, y compris les premiers ordinateurs d'échecs et les moteurs modernes. Ses gains d'efficacité permettent des recherches plus profondes dans le même budget computationnel, ce qui en fait une technique fondamentale dans la recherche adversarialle.
Histoire
John McCarthy, lors de l'atelier de Dartmouth en 1956, a rencontré Alex Bernstein d'IBM, qui écrivait un programme d'échecs. McCarthy a inventé la recherche alpha-bêta et l'a recommandée à Bernstein, mais Bernstein était « non convaincu ». Allen Newell et Herbert A. Simon, qui ont utilisé ce que McCarthy appelait une « approximation » en 1958, ont écrit que l'alpha-bêta « semble avoir été réinventé un certain nombre de fois ». Arthur Samuel avait une version précoce pour une simulation de dames. Richards, Timothy Hart, Michael Levin, et/ou Daniel Edwards ont également inventé l'alpha-bêta indépendamment aux États-Unis. McCarthy a proposé des idées similaires lors de l'atelier de Dartmouth et les a suggérées à un groupe de ses étudiants, y compris Alan Kotok au MIT en 1961. Alexander Brudno a indépendamment conçu l'algorithme alpha-bêta, publiant ses résultats en 1963. Donald Knuth et Ronald W. Moore ont affiné l'algorithme en 1975. Judea Pearl a prouvé son optimalité en termes de temps d'exécution attendu pour des arbres avec des valeurs de feuilles assignées aléatoirement dans deux articles. L'optimalité de la version randomisée de l'alpha-bêta a été montrée par Michael Saks et Avi Wigderson en 1986.
Idée Centrale
Un arbre de jeu peut représenter de nombreux jeux à somme nulle à deux joueurs, tels que les échecs, les dames et le reversi. Chaque nœud dans l'arbre représente une situation possible dans le jeu. Chaque nœud terminal ( résultat) d'une branche est assigné un score numérique qui détermine la valeur du résultat pour le joueur ayant le prochain coup.
L'algorithme maintient deux valeurs, alpha et bêta, qui représentent respectivement le score minimum que le joueur maximisant est assuré d'obtenir et le score maximum que le joueur minimisant est assuré d'obtenir. Initialement, alpha est l'infini négatif et bêta est l'infini positif, ce qui signifie que les deux joueurs commencent avec leur pire score possible. Chaque fois que le score maximum que le joueur minimisant(le joueur « bêta ») est assuré d'obtenir devient inférieur au score minimum que le joueur maximisant(le joueur « alpha ») est assuré d'obtenir (c'est-à-dire bêta < alpha), le joueur maximisant n'a pas besoin de considérer les descendants supplémentaires de ce nœud, car ils ne seront jamais atteints dans le jeu réel.
Pour illustrer avec un exemple de la vie réelle, supposons que quelqu'un joue aux échecs, et que c'est son tour. Le coup « A » améliorera la position du joueur. Le joueur continue de chercher des coups pour s'assurer qu'un meilleur n'a pas été manqué. Le coup « B » est également un bon coup, mais le joueur réalise ensuite qu'il permettra à l'adversaire de forcer un échec et mat en deux coups. Ainsi, les autres résultats de jouer le coup B n'ont plus besoin d'être considérés puisque l'adversaire peut forcer une victoire. Le score maximum que l'adversaire pourrait forcer après le coup B est l'infini négatif : une défaite pour le joueur. Ceci est inférieur à la position minimum qui a été précédemment trouvée ; le coup A ne résulte pas en une défaite forcée en deux coups.
Améliorations Par Rapport Au Minimax Naïf
Le bénéfice de l'élagage alpha-bêta réside dans le fait que des branches de l'arbre de recherche peuvent être éliminées. De cette manière, le temps de recherche peut être limité au sous-arbre « plus prometteur », et une recherche plus profonde peut être effectuée dans le même temps. Comme son prédécesseur, il appartient à la classe des algorithmes de branchement et de bornage. L'optimisation réduit la profondeur effective à légèrement plus de la moitié de celle du minimax simple si les nœuds sont évalués dans un ordre optimal ou quasi-optimal(le meilleur choix pour le côté en mouvement ordonné en premier à chaque nœud).
Avec un facteur de branchement( moyen ou constant) de b, et une profondeur de recherche de d plis, le nombre maximum de positions de nœuds feuilles évaluées(lorsque l'ordre des coups est pessimal) est O(b^d) - le même qu'une recherche minimax simple. Si l'ordre des coups pour la recherche est optimal(ce qui signifie que les meilleurs coups sont toujours recherchés en premier), le nombre de positions de nœuds feuilles évaluées est environ O(b 1 b 1 ... b) pour une profondeur impaire et O(b 1 b 1 ... 1) pour une profondeur paire, ou O(b^(d/2)) = O(sqrt(b^d)). Dans ce dernier cas, où la pli d'une recherche est paire, le facteur de branchement effectif est réduit à sa racine carrée, ou, de manière équivalente, la recherche peut aller deux fois plus profond avec la même quantité de calcul. L'explication de b1b1... est que tous les coups du premier joueur doivent être étudiés pour trouver le meilleur, mais pour chacun, seul le meilleur coup du second joueur est nécessaire pour réfuter tous les coups du premier joueur sauf le premier(et le meilleur) - l'alpha-bêta garantit qu'aucun autre coup du second joueur n'a besoin d'être considéré.
Lorsque les nœuds sont considérés dans un ordre aléatoire(c'est-à-dire que l'algorithme est randomisé), asymptotiquement, le nombre attendu de nœuds évalués dans des arbres uniformes avec des valeurs de feuilles binaires est Theta(((b-1+sqrt(b^2+14b+1))/4)^d). Pour les mêmes arbres, lorsque les valeurs sont assignées aux valeurs de feuilles indépendamment les unes des autres et que zéro et un sont tous deux également probables, le nombre attendu de nœuds évalués est Theta((b/2)^d).
Considérations D'Implémentation
En pratique, l'élagage alpha-bêta est souvent implémenté avec un approfondissement itératif, où la profondeur de recherche est augmentée de manière incrémentale. L'ordre des coups est critique pour atteindre des performances quasi-optimales ; les heuristiques courantes incluent l'examen des captures en premier, l'utilisation de coups tueurs, et l'emploi de tables de transposition. L'algorithme peut être étendu avec des techniques comme la recherche de quiescence pour éviter les effets d'horizon, et il forme la base pour des algorithmes plus avancés tels que la recherche de variation principale et le negascout. L'élagage alpha-bêta est largement utilisé dans les programmes d'échecs, y compris ceux qui fonctionnent sur des plateformes comme Chess computer systèmes, et il a été intégré dans divers cadres d'IA de jeu.
Héritage Et Impact
L'élagage alpha-bêta a eu un impact durable sur Artificial intelligence et la théorie des jeux. Il était un composant clé dans les premiers programmes d'échecs et reste pertinent dans les moteurs de jeu modernes, surtout pour les jeux avec de grands facteurs de branchement. Les améliorations d'efficacité de l'algorithme ont été étudiées de manière extensive, et ses principes ont influencé d'autres domaines de recherche et d'optimisation. Bien que des techniques plus récentes comme Machine learning et Deep learning aient transformé l'IA de jeu, l'élagage alpha-bêta sert toujours d'outil fondamental dans la recherche adversarialle, et son développement historique met en évidence la nature collaborative et itérative de la recherche en IA.