Bonjour 

Je programme actuellement une IA d'échec.

Pour ce faire, je me suis appuyé sur le tuto de l'algo Min-Max présenté sur ce site.

Mon IA est bien fonctionnelle mais au-delà d'une profondeur de recherche de 4, le temps de calcul devient trop important.

J'ai donc regarder du côté de l'élégage alpha-beta pour pouvoir couper certaines branches.

Une fois mis en place, j'ai pu effectivement constater une baisse du nombre de feuilles explorées. A titre d'exemple, au bout d'une dizaine de coup et pour une profondeur égale à 2, le min-max classique explore 5226 feuilles alors que le min-max alpha-beta en explore 4669.

Afin de couper un maximum de branches, j'ai trié par ordre décroissant de valeur les nœuds MIN.

J'ai effectivement pu vérifier une baisse (mais bien trop peu significative). Toujours à titre d'exemple, pour une profondeur 2 et après une dizaine de coups joués chacun, voici le nombre de feuille explorées selon les 3 algos :

min-max alpha-beta avec tri decroissant au nœud MIN : 4624

min-max alpha-beta : 4669

min-max : 5226

Mes questions par rapport à cela sont les suivantes :

Ces « chiffres » vous semblent-ils normaux ? Je me pose cette question parce que je n'arrive toujours pas à dépasser une profondeur égale 4 (qui demande déjà quelques secondes de calculs). J'ai l'impression que mon algo alpha-beta ne coupe pas autant de branches qu'il le devrait.

Que pourrais-je faire pour améliorer cet algorithme alpha-beta ?

Cordialement

Bonjour,

Alors j'ai implémenté des algo d’échec il y a longtemps... Il me semble que si l'algo minmax trouve un coup en n nœuds, alpha beta devrait trouver en 1+2sqrt(n) nœuds ( http://www-public.tem-tsp.eu/~gibson/Teaching/CSC4504/ReadingMaterial/KnuthMoore75.pdf ). Donc les chiffres que tu donnent ne semblent pas correspondre.

Rien que la, il va falloir que tu regardes ce qui ne va pas...

Ensuite, oui il existe des moyens d'optimiser l'algo, notamment le problème d'horizon (avoir une profondeur fixe pose des problèmes d'optimisation) etc... Jette un oeil sur l'iteratif deepening, l'élagage de futilité et la quiescence

Merci pour ta réponse.

Au de ce que tu me dis, j'ai effectivement mal du implémenter la partie convernant l'alpha-beta

J'ai essayé de traduire mes fonctions en une sorte de langage naturel (pour que ce soit plus facilement lisible).

A chaque fois, mes fonctions retournent le coup à jouer, la valeur de ce coup, alpha et beta

score, coup, alpha, beta= Max(2, -infini, +infini,  null) ;



Max (int profondeur, int alpha, int beta, Coup coup){
        meilleur_coup
        meilleur_score = -infini        

        if (profondeur == 0 OU finDePartie)
                calcul et retourne le score associé a cette position


        Pour tous les coups possibles classés par ordre  décroissant de score
                score, coup, alpha, beta = Min (profondeur-1, alpha, beta, coup) 
                si score > meilleur_score
		 score = meilleur_score
                           meilleur_coup = coup
                si meilleur_score > beta
                           retourner score, coup, alpha, beta
                alpha = Maximum(alpha, meilleur_score)

       retourner score, coup, alpha, beta
}




Min (profondeur, alpha, beta, coup){
        meilleur_coup
        moins_bon_score = +infini       

        if (profondeur == 0 OU finDePartie)
                calcul et retourne le score associé a cette position


        Pour tous les coups possibles classés par ordre  décroissant de score
                score, coup, alpha, beta = Max (coup, profondeur-1, alpha, beta) 
                si score < moins_bon_score
                            score = moins_bon_score
                            meilleur_coup = coup
                si moins_bon_score < alpha
                            retourner score, coup, alpha, beta
                beta = Minimum(moins_bon_score, beta)
      retourner score, coup, alpha, beta
} 

Voyez-vous un problème dans la conception de mes fonctions ?

-
Edité par Bibblon 22 avril 2016 à 3:18:43

Mmmh, je ne me rappelle plus de l'algo exactement, mais voici une doc qui pourrait t'aider : http://www.lamsade.dauphine.fr/~cazenave/papers/berder00.pdf