Discussion :

[Bathou]

Bonjour!!
Petite question sur l'algorithme negamax avec coupure alpha béta : quelles sont les deux conditions de coupure...?
je crois que c'est alpha>béta et...? si vous pouviez m'aider...
merki!!

[Danious]

La condition alpha>beta est pour l'algorithme minmax, et c'est une condition utilisée pour les deux coupures !

Regarde le lien :

http://fr.wikipedia.org/wiki/Image:A...ta_sample1.png

et plus particulièrement les deux algos de coupures alpha-beta pour minmax et negamax. Ca devrait t'éclairer.

[Matthieu Brucher]

http://fearyourself.developpez.com/t...l/sdl/morpion/
Les 2 dernières parties peuvent t'intéresser.

[ol9245]

http://fearyourself.developpez.com/t...l/sdl/morpion/
Les 2 dernières parties peuvent t'intéresser.

J'ai lu le tuto sur l'alpha beta.
Il y a une manière assez simple d'expliquer l'évolution de minimax vers alphabeta, qui n'est pas fournie dans le tuto. la voici :

Minimax évalue toutes les positions terminales de l'arbre(*). Or, l'homme ne fait pas ça : nous passons beaucoup de temp à réfléchir sur les bons coups (pour être certains qu'ils sont bons) mais les mauvais coups sont facile à trouver et à éliminer. Pourquoi ? parcequ'on n'a pas besoin de trouver LA meilleure parade à un coup dégueulasse. Il suffit d'en trouver une acceptable qui le disqualifie irémédiablement. C'est ce qu'on appelle l'élagage a posteriori, et c'est ce que fait alphabeta.

Je réfléchit sur le coup j : est-il meilleur que le coup i précédemment étudié ?
si une des réponses de l'adversaire à j lui garantit une position plus avantageuse que celle que je suis certain d'obtenir en jouant i, alors, je n'ai pas besoin d'étudier les autres coups de l'adversaire car je sais déja que le coup j est moins bon que i.

On doit bien comprendre que alphabeta donne toujours le même résultat que minimax. Il fait juste l'économie de l'exploratio des sous-arbres inutiles.

On voit aussi que plus le premier coup étudié par alpha beta est bon, plus les autres coups ont de chance d'être élagués rapidement -> le nombre de position terminale évaluée par alpha beta est minimale si les coups sont systématiquement explorés du meilleur au moins bon.

Pour exploiter cette propriété très puissante, il y a de nombreuses solutions :
- utiliser la fontion d'évaluation pour déterminer l'ordre des coups à soumettre à alphabeta, du meilleur au moins bon
- si un coup permet l'élagage d'une branche de l'arbre, c'est probablement que c'est un bon coup. On l'apelle le coup meurtier. C'est une bonne idée d'étudier ce coup là en priorité. exemple aux échecs : Blanc joue. Noir peut faire mat au prochain coup en jouant sa tour. en étudiant le mouvement d'un pion blanc, alphabeta découvre que Noir le fait mat en jouant sa tour. Ce n'est pas idiot d'étudier en priorité et systématiquement ce mouvement de tour comme réponse à tous les autres coups possibles de blanc : cela permettra d'élaguer toutes les branches qui ne gèrent pas cette menace de mat.

Il y a beaucoup d'autres manières d'optimiser alphabeta en choisissant correctement l'ordre des coups. C'est pour cela qu'il faut bien comprendre ce qu'il y a derrière en termes de logique de jeu : identifier les meilleurs coups d'abord pour consacrer moins e temps à éliminer les mauvais.

[EDIT] (*) Il s'agit de l'arbre des coups possibles. Aux positions terminales de cet arbre, la partie n'est pas nécessairement terminée. ne pas confondre position terminales e l'arbre minimax et position terminales e la partie en cours.

[mchk0123]

Quelques confusions.

On voit aussi que plus le premier coup étudié par alpha beta est bon, plus les autres coups ont de chance d'être élagués rapidement -> le nombre de position terminale évaluée par alpha beta est minimale si les coups sont systématiquement explorés du meilleur au moins bon.

Ce qui peut être trés difficile à évaluer. Autant une position de fin de jeu (par exemple pour les echecs) est facile à quantifier sous forme de fonction d'évaluation ; autant l'évaluation d'une position intermédiaire est loin d'être trivial, crois en mon expérience.

Pour exploiter cette propriété très puissante, il y a de nombreuses solutions :
- utiliser la fontion d'évaluation pour déterminer l'ordre des coups à soumettre à alphabeta, du meilleur au moins bon

Il y a comme un problème, la fonction d'évaluation peut trés bien être définie uniquement les noeuds terminaux (seul prérequis pour l'algorithme minmax). Du coup estimer si un mouvement est meilleur ou moins bon nécessite par récursion de parcourir tout l'arbre, ce qui revient au même qu'un algo alpha/beta classique.

- si un coup permet l'élagage d'une branche de l'arbre, c'est probablement que c'est un bon coup. On l'apelle le coup meurtier. C'est une bonne idée d'étudier ce coup là en priorité. exemple aux échecs : Blanc joue. Noir peut faire mat au prochain coup en jouant sa tour. en étudiant le mouvement d'un pion blanc, alphabeta découvre que Noir le fait mat en jouant sa tour. Ce n'est pas idiot d'étudier en priorité et systématiquement ce mouvement de tour comme réponse à tous les autres coups possibles de blanc : cela permettra d'élaguer toutes les branches qui ne gèrent pas cette menace de mat.

Ton approche nécessiterait le calcul d'une estimation de coup meurtrier pour toutes les noeuds descendants ; en soit cela prend déjà du temps. De plus je ne suis pas sur que statistiquement cela soit efficace car, la probabilité d'avoir un coup meurtrier (gardons l'exemple des echecs) est trés trés faible, donc on perdra trop de temps à estimer une situation peu probable, même si cette situation est trés économe en terme d'élagage de l'arbre.

[ol9245]

Je ne sais pas si il y a confusuion mais en effet, je crois pas qu'on parle de la même chose

- une fonction d'évaluation évalue toute positions possible dans un jeu et lui donne une note. Une note élevée indique que cette position semble favorable au camp A, une note faible indique que cette position semble favorable au camp B. la fonction d'évaluation ne "joue pas". Elle ne "Calcule" pas des coups e avance etc... la fonction d'évaluation "regarde" le jeu et le note selon des critères objectifs :
- un at-il déja gagné la partie
- qui a l'avantage matériel
et d'autres subjectifs
- combien de coups possibles (un camp qui a le choix de jouer de nombreux coups différents a souvent l'avantage)
- combien de pièces menacées, etc, etc.

- minimax explore tout l'arbre des possibilités de jeu à partir de la position initiale et ce jusqu'à une profonderur prédéterminée N, généralement pas très profonde en raison de l'explosion combinatoire. minimax évalue (par la fonction d'évaluation) toutes les positions terminales de l'arbre (qui ne sont pas nécéssairement des positions terminales du jeu) et détermine la branche de l'arbre qui LE conduit LUI à la meilleure position terminale possible AU SENS DE LA FONCTION D'EVALUATION en tenant compte que l'adversaire va riposter du mieux qu'il peut.

- alpha beta fait exactement la même chose et partage le même paradigme : trouver comment optimiser ma position au sens de la fonction d'évaluation avec une profondeur de N coups. alphabeta évalue moins de positions terminales de l'arbre et fournit toujours le même résultat que minimax, c'est à dire un résultat certain (au sens de la fonction d'évaluation).

Pour des jeux très très faciles genre tic-tac-toe (le morpion sur 3x3), la fonction d'évaluation peut être simplistissime : si noir a déja gagné : +1, si blanc a déja gagné : -1, sinon : 0. Pour exploiter une telle fonction d'évaluation, il faut un arbre assez profond pour toujours atteindre la fin du jeu. C'est un cas dégénéré du minimax/alpha beta dans lequel les positions terminales de l'arbre de réflexion sont aussi des positions terminales du jeu. Dans un jeu normal, rien ne distingue spécialement une position terminale de l'arbre de sa position racine : ce sont des positions qui peuvent, ou pas, arriver un jour dans un jeu. La fonction d'évaluation doit pouvoir les noter toutes.

Pour les vrais jeux, la qualité du jeu dépend à 90% de la finesse de la fonction d'évaluation, et à 10% de l'optimisation de l'alpha beta est des autres aspects. Les fontions d'évaluation sont en général de grosses fonctions, mais elles peuvent aussi être assez simple. Leur programmation nécessite dans tous les cas une excelente expertise du jeu. J'ai par exemple programmé un jeu d'awalé dans les années 90 après avoir appris ce jeu auprès de maitres africains, dans un village reculé de Côte d'Ivoire. Mon algo bat tous les jeux que j'ai pu trouver sur internet jusqu'à aujourd'hui. Pourquoi ? parceque sa fonction d'évaluation contient un "truc" (cherche awale sur DVP pour en savoir plus) qui est la transcription d'un mode de pensée typique des maitres qui m'ont appris à jouer.

Enfin pour répondre à l'une de tes dernières remarques, l'heuristique du coup meurtrier ne coute rien. il dit seulement que si un coup Meurtrier de B permet de couper une branche de A, alors, lors de l'études des autres coups non encore explorés de A, il est efficace d'étudier en priorité la réponse M.

Par généralisation de cet heuristique, on comprend facilement qu'il est préférable, comme je l'ai dit, d'étudier les coups du meilleur au moins bon.

Une des méthodes pour cela est de mémoriser l'arbre complet, puis, faire un alpha beta à 1 coup d'avance seulement, trier les coups selon le résultat de cet alpha beta, et utiliser cet ordre pour explorer l'arbre à 2 coups d'avance, et ainsi de suite. Cet optimisation conduit en apparence à explorer plus de positions terminales qu'un minimax mais c'est seulement en apparence car l'explosion combinatoire étant ce qu'elle est, il y a peu de positions non terminales dans un arbre minimax. Note que la mémorisation de l'arbre complet n'est pas strictement indispensable pour utiliser cet heuristique, mais elle est quanbd même vraiment logique.

de fil en aiguille on arrive à un niveau supplémentaire d'optimisation : après avoir joué mon coup, et l'adversaire ayant joué le sien, il me reste en mémoire un morceau d'arbre certes pas très profond, mais sur lequel j'ai déja une petite expertise des coups qui semblent les meilleurs. Cette expertise me permet de commencer un nouvel alpha-beta dans les conditions les plus propices possibles à un élagage efficace.

un cran plus lon vers l'optimisation : au lieu d'atendre la réponse de l'adversaire pour couper deux étages à mon arbre, je peux, dès que j'ai jouer, commencer à réfléchir sur le sous-arbre issu du coup que j'ai choisi. Plus l'adversaire va prendre de temps pour jouer son propre coup, plus je peux pendant ce temps là descendre mon alpha beta profondément.

Rien qu'avec ces optimisations relativement simpls de l'alpha beta, je peux obenir un programme qui a les propriétés suivantes :

- il contine à réfléchir après avoir joué, pendant que l'adversaire humain réfléchit à son coup.
- comme les coups supposés les meilleurs à l'instant t sont toujours explorés en premier, je peux piloter mon programme sur une durée de réflexion et non pas sur une profondeur d'arbre. A tout moment, j'ai en mémoire la meilleure expertise qu'il était possible d'obtenir pendant ce temps là. C'est là que l'alphabeta pend toute sa puissance par rapport au minimax (qui ne peut se décider qu'après avoir exploré tout l'arbre).

Ceci maitrisé, il est temps de passer à un autre étage de l'optimisation : l'élagage dit a priori. Là, oui, on rentre dans des trucs vraiment plus difficiles à maitriser.
OL

[PRomu@ld]

détermine la branche de l'arbre qui LE conduit LUI à la meilleure position terminale possible AU SENS DE LA FONCTION D'EVALUATION en tenant compte que l'adversaire va riposter du mieux qu'il peut.

En fait, on peu faire plus fin en ne respectant pas tout à fait ce point, en effet, si tu fais un choix qui peut te conduire à la victoire mais passe par un coup relativement délicat (ie: il peut te faire perdre), ça n'est peut-être pas un si bon choix que cela. Il faut pondérer cette exploration. Ca peut te permettre de déterminer l'agressivité de ton adversaire : S'il est agressif, il va jouer des coups relativement forts mais qui peuvent découvrir sa défense. (important aux échecs par exemple). Mais ceci est relativement difficile à évaluer (tout comme la fonction d'évaluation)

[mchk0123]

- une fonction d'évaluation évalue toute positions possible dans un jeu et lui donne une note. Une note élevée indique que cette position semble favorable au camp A, une note faible indique que cette position semble favorable au camp B. la fonction d'évaluation ne "joue pas".

Tu as tout à fait raison sur la forme, c'est juste que sur le fond, les algorithmes minmax et alpha beta ne nécessites la calculabilité de la fonction d'évaluation que sur les feuilles de l'arbre (qui, effectivement, ne sont pas nécessairement des positions de fin de jeu)

- minimax explore tout l'arbre des possibilités ... toutes les positions terminales de l'arbre (qui ne sont pas nécéssairement des positions terminales du jeu) ...

Pour des jeux très très faciles genre tic-tac-toe (le morpion sur 3x3), la fonction d'évaluation peut être simplistissime : si noir a déja gagné : +1, si blanc a déja gagné : -1, sinon : 0.

Tout à fait d'accord.

Dans un jeu normal, rien ne distingue spécialement une position terminale de l'arbre de sa position racine : ce sont des positions qui peuvent, ou pas, arriver un jour dans un jeu. La fonction d'évaluation doit pouvoir les noter toutes.

Je suis un peu plus réservé. Dans un jeu normal, comme le jeu d'echec, la fonction d'évaluation peut trés bien être totalement différente selon que l'on est en début de partie, milieu de partie ou fin de partie. Distinguer ces différentes situations est crucial car :
- les formules d'évaluation n'ont rien à voir l'une avec l'autre
- la calculabilité (coût en temps) est également différente

Typiquement, l'évaluation d'une position de milieu de jeu est trés couteuse et sans astuces de calcul connues.
C'est pour cela que je met un bémol à l'ordonnancement des positions en entrée de l'algo alpha/beta. Pour certains types de jeu, comme le jeu d'echec, il est plus éfficace, au vu de la combinatoire des noeuds fils, de commencer d'abord par une recherche des heuristiques à priori.

Enfin pour répondre à l'une de tes dernières remarques, l'heuristique du coup meurtrier ne coute rien. il dit seulement que si un coup Meurtrier de B permet de couper une branche de A, alors, lors de l'études des autres coups non encore explorés de A, il est efficace d'étudier en priorité la réponse M.

J'avoue que j'était limite sur mon argumentation contre le coup meurtrier.

Une des méthodes pour cela est de mémoriser l'arbre complet, puis, faire un alpha beta à 1 coup d'avance seulement, trier les coups selon le résultat de cet alpha beta, et utiliser cet ordre pour explorer l'arbre à 2 coups d'avance, et ainsi de suite. Cet optimisation conduit en apparence à explorer plus de positions terminales qu'un minimax mais c'est seulement en apparence car l'explosion combinatoire étant ce qu'elle est, il y a peu de positions non terminales dans un arbre minimax. Note que la mémorisation de l'arbre complet n'est pas strictement indispensable pour utiliser cet heuristique, mais elle est quanbd même vraiment logique.

L'ordonnancement des coups à étudier n'est pas une heuristique, mais plutôt une optimisation algorithmique.

[ol9245]

En fait, on peu faire plus fin en ne respectant pas tout à fait ce point, en effet, si tu fais un choix qui peut te conduire à la victoire mais passe par un coup relativement délicat (ie: il peut te faire perdre), ça n'est peut-être pas un si bon choix que cela. Il faut pondérer cette exploration. Ca peut te permettre de déterminer l'agressivité de ton adversaire : S'il est agressif, il va jouer des coups relativement forts mais qui peuvent découvrir sa défense. (important aux échecs par exemple). Mais ceci est relativement difficile à évaluer (tout comme la fonction d'évaluation)

si un sacrifice porte ses fruits dans le nombre de coups défini par la profondeur de l'arbre, minimax, comme alphabeta, vont le découvrir. d'autre part, quand on dit qu'alphabeta est optimum si les coups sont evalues du meilleur au moins bon, on reste dans le paradigme de l'alpha beta. dans l'exemple cité, le sacrifice est le meilleur coup et donc en l'étudiant en premier alphabeta converge plus vite versla solution du minimax. d'un point de vue pratique, il n'y aura qu'un seul sacrifice payant sur les quelques dizaines de milliers de positions a evaluer. donc l'existence possible de sacrifices payants ne ruine pas lîdée génégrale.
Par contre l'exemple a l'avantage de mettre en avant la difficulté d'identifier à l'avance le meilleur coup. d'ou l''idée de faire des alphabeta de profondeur croissante qui n'ont pour seul but que de classer les coups à envoyer à l'alphabeta de profondeur N+1.

[Pouf842]

Bonjour

Je me permets de remonter ce topic pour vous poser deux petites question à propos de cet algo :

Premièrement :

En essayant de bien comprendre l'algorithme alpha-bêta (je ne supporte pas de copier-coller du code que je ne comprend pas), j'ai fini par tenter de le réécrire moi-même. Et j'en suis arrivé à un algorithme légèrement différent, je dirais même plus simple, puisque je n'ai besoin que d'une valeur retenue (au lieu de alpha et beta), mais qui semble marcher exactement de la même manière. Seulement, j'ai du mal à croire qu'avec mes deux neurones et demi, j'ai pu simplifié un algorithme connu et utilisé depuis des années par des professionnels...

Donc je voudrais vous demander votre avis, si vous trouvez des erreurs, qu'en fait il ne marche pas dans tous les cas (j'ai testé avec quelques arbres), etc...

Alpha-bêta de Wikipedia :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fonction ALPHABETA(P, A, B) /* A < B */
   si P est une feuille alors
       retourner la valeur de P
   sinon
       Meilleur = –INFINI
       pour tout fils Pi de P faire
           Val = -ALPHABETA(Pi,-B,-A)
           si Val > Meilleur alors
               Meilleur = Valeur_du_noeud
               si Meilleur > A alors
                   A = Meilleur
                   si A > B alors
                       retourner Meilleur
       finpour 
       retourner Meilleur

Mon alphabeta :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Alphabeta(profondeur, MinimumDesFreres) // On passe à chaque noeud fils la valeur minimale de ses frères
{
        Si la profondeur est de 0
                Retourner MaValeur // Les feuilles de l'arbre ont une valeur fixée (ou calculée)
        Sinon
                MinimumDesFils = 30 000 // Initialisé à plus que le maximum possible
 
                Pour chaque noeud
                        ValeurDuNoeudFils = Alphabeta(profondeur - 1, MinimumDesFils) // On passe à chaque noeud le minimum de ses frères
 
                        Si ValeurDuNoeudFils < MinimumDesFils
                                MinimumDesFils = ValeurDuCoup // On garde la valeur minimale des noeuds fils
                        FinSi
 
                        Si ValeurDuNoeudFils < -MinimumDesFreres // Coupure alpha ou beta
                                Retourner -ValeuDuNoeudFils
                        FinSi
                 FinPour
         FinSi
 
        Retourner -MinimumDesFils  // La valeur du noeud vaut -(la valeur minimale de ses noeuds fils. Equivaut à valeur = Max de -(les valeurs des fils))
}

Deuxièmement : Je ne sais pas comment évaluer/noter une situation, donc comment donner une valeur à mes feuilles. En vrac, j'ai trouvé/glaner sur le net les idées suivantes :

1. L'adversaire est mat : score infini
2. L'adversaire est en échec : gros score
3. Je contrôle une case centrale (i.e. je peux l'atteindre en un coup) : x points
4. Je peux manger une pièce adverse : autant de points que vaut la pièce adverse
5. x points par pièce que je contrôle toujours (x étant la valeur de la pièce)

Mais sachant que j'ai trouvé ces idées par moi-même (en majorité), je ne sais pas si ça vaut vraiment quelque chose, et surtout s'il n y a pas beaucoup mieux. Quels sont les habitudes, pour ça ?

Merci

[Pouf842]

Up !

Personne ?

[Pouf842]

Toujours personne pour me répondre ?