Élagage alpha-bêta

L'élagage alpha-bêta accélère la recherche effectuée par un moteur d'échecs, un programme qui compare les coups et les réponses. La recherche peut être représentée comme un arbre: chaque nœud est une position et chaque branche un coup légal. Sans élagage, le programme examinerait de nombreuses continuations qui finiraient par se révéler inutiles.

La méthode maintient deux bornes pendant la recherche. Alpha est le meilleur résultat qu'un camp peut déjà garantir sur le chemin actuel. Bêta est une limite créée par une autre possibilité déjà offerte à l'adversaire. Dès qu'une continuation est si mauvaise qu'un joueur rationnel ne la choisirait jamais, l'approfondir ne peut plus modifier la décision au nœud supérieur.

La branche est arrêtée grâce à une borne logique dans l'arbre, et non simplement parce qu'un coup paraît peu séduisant. À profondeur égale et avec les mêmes évaluations à la limite de recherche, alpha-bêta renvoie le même choix qu'une recherche complète supposant que les deux camps jouent leurs meilleures réponses.

L'économie dépend fortement de l'ordre des coups. Tester tôt les coups forts établit plus vite des bornes utiles et permet d'arrêter davantage de branches sans les approfondir. Une fonction d'évaluation, qui attribue une estimation numérique à une position, fournit les valeurs aux points où la recherche à profondeur finie s'arrête.