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!!
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Algorithme alpha béta
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!!
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.
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.Envoyé par Miles
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.
Quelques confusions.
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.
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.
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.
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
Répondre avec citation
Partager