Élagage alpha-bêta
Quelles branches puis-je ignorer sans changer la réponse ?
Un minimax qui cesse d’explorer une branche dès qu’il est prouvé qu’elle ne vaut pas mieux qu’une branche déjà trouvée. Le même coup, après bien moins de positions.
Résultat. La racine vaut 3, la même réponse que le minimax, avec 6 feuilles regardées sur 9. Les coupes ne sautent que du travail qui ne pouvait pas changer la réponse.
L’alpha-bêta garde deux nombres pendant la recherche. Alpha est le meilleur score dont le camp qui choisit est déjà sûr ; bêta est le meilleur score dont l’adversaire est déjà sûr. Ensemble ils forment une fenêtre.
Si une branche ne peut mener qu’en dehors de cette fenêtre, personne de sensé ne laisserait la partie y arriver : l’adversaire a déjà mieux ailleurs. Les coups restants de cette branche ne sont jamais regardés. Le résultat est exactement celui du minimax, jamais une approximation.
Le gain dépend de l’ordre dans lequel les coups sont essayés. Si les bons coups viennent d’abord, les coupures arrivent tôt ; s’ils viennent en dernier, rien n’est économisé. Avec un ordre parfait, il examine environ la racine carrée des positions du minimax, donc il peut chercher environ deux fois plus profond pour le même effort.
Chargement de la démo…
Puissance 4 avec l’alpha-bêta sélectionné. Appuyez sur « Comparer les algorithmes ici » en cours de partie : le minimax et l’alpha-bêta choisissent la même colonne, après des nombres de positions très différents.
- 01Lancer le minimax en transmettant alpha (au départ moins l’infini) et bêta (au départ plus l’infini).
- 02À votre tour, relever alpha dès qu’un meilleur score est trouvé ; au tour de l’adversaire, abaisser bêta.
- 03Dès qu’alpha est au moins égal à bêta, s’arrêter : l’adversaire ne laissera jamais cette branche se produire.
- 04Ordonner les coups pour que les meilleurs probables viennent d’abord, comme le centre à Puissance 4 ou les coins à Othello. Plus le bon coup vient tôt, plus on coupe.
function alphabeta(position, depth, alpha, beta, me):
if game_over(position) or depth == 0: return evaluate(position, me)
if turn(position) == me:
best = -infinity
for m in ordered_moves(position):
best = max(best, alphabeta(play(position, m), depth - 1, alpha, beta, me))
alpha = max(alpha, best)
if alpha >= beta: break # cut-off
return best
else:
best = +infinity
for m in ordered_moves(position):
best = min(best, alphabeta(play(position, m), depth - 1, alpha, beta, me))
beta = min(beta, best)
if alpha >= beta: break # cut-off
return bestAu pire, pas mieux que le minimax. Avec les meilleurs coups essayés d’abord, c’est environ la racine carrée de ce coût. Un bon ordre des coups fait l’essentiel du chemin.
- Renvoie exactement le coup du minimax.
- Permet souvent de chercher deux fois plus profond dans le même temps.
- Ne coûte que quelques comparaisons et un ordre des coups.
- Sans bon ordre des coups, le gain est faible.
- Toujours exponentiel : les grands jeux ont encore besoin d’une fonction d’évaluation et d’une limite de profondeur.
- Elle doit voir toute la fenêtre, donc elle se parallélise mal.
- 01MorpionLe même jeu parfait que le minimax avec bien moins de positions ; la démo affiche les deux comptes côte à côte.
- 02HEXNe cherche que les cases proches des pierres existantes, les meilleures d’abord selon l’évaluation par connexion la plus courte, donc les coupures arrivent tôt.
- 03OthelloLes coups sont essayés coins d’abord, puis bords, donc une mauvaise branche est vite abandonnée.
- 04Puissance 4La colonne centrale est essayée en premier, car elle participe au plus d’alignements.