Élagage Alpha-Beta

Qu'est ce que l'élagage Alpha-Beta ?

L'élagage Alpha-Beta c'est une amélioration de l'algorithme Minimax. Le principe de base c'est de parcourir un arbre de jeu pour trouver le meilleur coup possible, mais en évitant d'explorer les branches qui ne peuvent de toute façon pas changer la décision finale. Ça permet de gagner beaucoup de temps de calcul sans changer le résultat.

Pourquoi utiliser Alpha-Beta ?

Le problème avec Minimax c'est que sa complexité est exponentielle : avec un facteur de branchement $b$ et une profondeur $d$ , on doit évaluer $O (b^{d})$ nœuds. Ça devient vite ingérable sur des jeux un peu complexes.

Alpha-Beta est utile pour :

les jeux à deux joueurs comme les Échecs ou les Dames,
les jeux à information parfaite où chaque joueur voit tout l'état du jeu,
dès qu'on a une fonction d'évaluation pour noter les états non terminaux.

Avec un bon élagage, la complexité descend à $O (b^{d /2})$ , ce qui revient à pouvoir chercher deux fois plus profond pour le même coût.

Principe du Minimax

Minimax repose sur deux rôles qui alternent à chaque niveau de l'arbre :

MAX : le joueur veut maximiser son score.
MIN : l'adversaire veut minimiser le score de MAX.

La valeur d'un nœud est calculée récursivement :

$V (s) = ⎩ ⎨ ⎧ eval (s) max_{a} V (succ (s, a)) min_{a} V (succ (s, a)) si s est terminal si c’est le tour de MAX si c’est le tour de MIN$

Pseudocode Minimax

function minimax(nœud, profondeur, joueur_max) :
    si profondeur == 0 ou nœud terminal :
        retourner eval(nœud)
    si joueur_max :
        valeur = -∞
        pour chaque enfant de nœud :
            valeur = max(valeur, minimax(enfant, profondeur-1, False))
        retourner valeur
    sinon :
        valeur = +∞
        pour chaque enfant de nœud :
            valeur = min(valeur, minimax(enfant, profondeur-1, True))
        retourner valeur

Élagage α-β

L'idée c'est de garder deux bornes pendant toute la recherche :

α : le meilleur score que MAX a trouvé jusqu'ici (on commence à $- \infty$ ).
β : le meilleur score que MIN a trouvé jusqu'ici (on commence à $+ \infty$ ).

Dès qu'on a $α \geq β$ sur un nœud, ça sert à rien de continuer à explorer ses enfants : le résultat ne changera pas. On coupe la branche.

Pseudocode Alpha-Beta

function alpha_beta(nœud, profondeur, α, β, joueur_max) :
    si profondeur == 0 ou nœud terminal :
        retourner eval(nœud)
    si joueur_max :
        valeur = -∞
        pour chaque enfant de nœud :
            valeur = max(valeur, alpha_beta(enfant, profondeur-1, α, β, False))
            α = max(α, valeur)
            si α ≥ β :
                break  # coupure β
        retourner valeur
    sinon :
        valeur = +∞
        pour chaque enfant de nœud :
            valeur = min(valeur, alpha_beta(enfant, profondeur-1, α, β, True))
            β = min(β, valeur)
            si α ≥ β :
                break  # coupure α
        retourner valeur

Complexité

Cas	Complexité
Minimax sans élagage	$O (b^{d})$
Alpha-Beta (meilleur cas, ordre optimal)	$O (b^{d /2})$
Alpha-Beta (cas moyen, ordre aléatoire)	$O (b^{3 d /4})$

L'ordre dans lequel on explore les coups a beaucoup d'importance : si on regarde les meilleurs coups en premier, on génère plus de coupures et on va plus vite.

Limites

Même avec l'élagage, Alpha-Beta reste bloqué sur les jeux avec un très grand espace d'états. Au Go par exemple, le facteur de branchement est d'environ 250 avec des parties de 150 coups. Même $O (b^{d /2})$ c'est bien trop lourd.

C'est pour ça qu'on s'intéresse à des algorithmes comme MCTS, qui n'essayent pas d'explorer tout l'arbre mais utilisent des simulations aléatoires pour estimer quelles branches valent la peine d'être creusées.

Keyboard shortcuts

SAE