Fonction d'évaluation de MinMax
kaisserr
Messages postés
52
Date d'inscription
Statut
Membre
Dernière intervention
-
kaisserr Messages postés 52 Date d'inscription Statut Membre Dernière intervention -
kaisserr Messages postés 52 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
Je viens de terminer la partie graphique d'un jeu d'échec avec les règles et tout , donc 2 personnes peuvent jouer avec mon jeu maintenant.
J'aimerais commencer la partie intelligence artificielle, en faisant mes recherches je sais que je dois utiliser l'algorithme minmax avec la coupure alpha-beta.
je cherche depuis deux jours à quoi consiste cette fonction d'évaluation,
je me demande si quelqu'un peut m'aider en me donnant un lien ou un bout de code pour commencer.
merci d'avance
Je viens de terminer la partie graphique d'un jeu d'échec avec les règles et tout , donc 2 personnes peuvent jouer avec mon jeu maintenant.
J'aimerais commencer la partie intelligence artificielle, en faisant mes recherches je sais que je dois utiliser l'algorithme minmax avec la coupure alpha-beta.
je cherche depuis deux jours à quoi consiste cette fonction d'évaluation,
je me demande si quelqu'un peut m'aider en me donnant un lien ou un bout de code pour commencer.
merci d'avance
A voir également:
- Algorithme min max
- Fonction si et - Guide
- Fonction miroir - Guide
- Fonction moyenne excel - Guide
- Evaluation pc - Guide
- Fonction remplacer sur word - Guide
9 réponses
Ok merci,
Comme c'est dans la fonction MinMax qu'on parcours l'arbre du jeu, alors si j'ai bien compris à chaque profondeur on fait appel à cette fonction récursive, elle nous renvoi une valeur, et avec une profondeur décrémenter on la rappel pour qu'elle nous donne une nouvelle valeur, jusqu'à ce qu'on termine toutes les profondeurs, on fait la somme et ainsi la fonction minmax retournera cette valeur somme?
Ou bien est ce que le traitement d'affectation de valeur sur les coups se trouvent à l'intérieur mm de la fonction de minmax?
merci d'avance
Comme c'est dans la fonction MinMax qu'on parcours l'arbre du jeu, alors si j'ai bien compris à chaque profondeur on fait appel à cette fonction récursive, elle nous renvoi une valeur, et avec une profondeur décrémenter on la rappel pour qu'elle nous donne une nouvelle valeur, jusqu'à ce qu'on termine toutes les profondeurs, on fait la somme et ainsi la fonction minmax retournera cette valeur somme?
Ou bien est ce que le traitement d'affectation de valeur sur les coups se trouvent à l'intérieur mm de la fonction de minmax?
merci d'avance
Si tu parles de la fonction heuristique, tu dois faire une fonction qui attribue un valeur arbitraire à chacune des branches de manière récursive (du bas vers le haut de l'arbre).
Un exemple serait de donner des valeurs du genre:
- Le joueur A mange un pion: +1
- Le joueur A mange une tour: +3
- Le joueur A mange la reine: +10
- Le joueur A se fait manger un pion: -1
- Le joueur A se fait manger une tour: -3
etc.
et de calculer la somme de l'étape actuelle et de ses appels récursifs (cette deuxième somme remonte naturellement grâce à la récursivité).
Une bonne référence si tu comprends l'anglais: https://en.wikipedia.org/wiki/Minimax
Également, pour le jeu d'échec avec la méthode minimax, tu dois absolument déterminer une profondeur de recherche maximale (5-6 niveau maximum, même que 3-4 serait sûrement déjà assez long) sinon, ton code va s'exécuter pendant littéralement des années.
Un exemple serait de donner des valeurs du genre:
- Le joueur A mange un pion: +1
- Le joueur A mange une tour: +3
- Le joueur A mange la reine: +10
- Le joueur A se fait manger un pion: -1
- Le joueur A se fait manger une tour: -3
etc.
et de calculer la somme de l'étape actuelle et de ses appels récursifs (cette deuxième somme remonte naturellement grâce à la récursivité).
Une bonne référence si tu comprends l'anglais: https://en.wikipedia.org/wiki/Minimax
Également, pour le jeu d'échec avec la méthode minimax, tu dois absolument déterminer une profondeur de recherche maximale (5-6 niveau maximum, même que 3-4 serait sûrement déjà assez long) sinon, ton code va s'exécuter pendant littéralement des années.
Ef fait, MinMax est la fonction qui est récursive, et elle doit appelé la fonction heuristique (qui n'est pas récursive). La fonction heuristique analyse chaque état du jeu (chaque coup) et lui donne une valeur.
Voici une image animé qui démontre MinMax: https://en.wikipedia.org/wiki/File:Plminmax.gif
Et voici la trace finale (avec d'autres valeurs): https://en.wikipedia.org/wiki/File:Minimax.svg
Il ne faut pas oublier que la fonction MinMax alterne entre trouver la valeur minimale et maximale à chaque niveau:
Niveau 0: Le joueur A tente de maximiser son coup. (max)
Niveau 1: L'adversaire tente de minimiser le coup du joueur A (min)
Niveau 2: Le joueur A tente de maximiser son coup. (max)
Niveau 3: L'adversaire tente de minimiser le coup du joueur A (min)
etc.
Si tu vas sur la page wikipedia du alpha-beta pruning, tu as du pseudo-code qui pourrait bien t'aider: https://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta
Voici une image animé qui démontre MinMax: https://en.wikipedia.org/wiki/File:Plminmax.gif
Et voici la trace finale (avec d'autres valeurs): https://en.wikipedia.org/wiki/File:Minimax.svg
Il ne faut pas oublier que la fonction MinMax alterne entre trouver la valeur minimale et maximale à chaque niveau:
Niveau 0: Le joueur A tente de maximiser son coup. (max)
Niveau 1: L'adversaire tente de minimiser le coup du joueur A (min)
Niveau 2: Le joueur A tente de maximiser son coup. (max)
Niveau 3: L'adversaire tente de minimiser le coup du joueur A (min)
etc.
Si tu vas sur la page wikipedia du alpha-beta pruning, tu as du pseudo-code qui pourrait bien t'aider: https://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta
Bonjour,
Non MinMax ne fait pas la somme.
Il faut une fonction MinMax (celle qui est récursive) et une fonction d'évaluation.
La fonction MinMax parcourt récursivement les différentes positions. Lorsqu'elle atteint la feuille (profondeur maximum atteint), ensuite chacun des noeuds prendra alternativement les min et max.
Tu peux même optimiser l'algorithme minmax en pratiquant l'élagage alpha beta.
Cdlt,
Non MinMax ne fait pas la somme.
Il faut une fonction MinMax (celle qui est récursive) et une fonction d'évaluation.
La fonction MinMax parcourt récursivement les différentes positions. Lorsqu'elle atteint la feuille (profondeur maximum atteint), ensuite chacun des noeuds prendra alternativement les min et max.
Tu peux même optimiser l'algorithme minmax en pratiquant l'élagage alpha beta.
Cdlt,
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
fiddy , j'ai voulu dire que c'est dans la fonction minmax qu'on fait la somme des évaluations.
merci Doctor C pour l'animation c'est claire et bien fait.
En fait je pense mon plus grand problème serait la création de cet arbre.
En créant mon jeu, j'ai juste une classe Plateau et une classe Coup mais je n'avais pas créer pour chaque composant(pion, reine...) une classe.
Est ce que vous pensez que ca me prendrais beaucoup de temps pour adapter mon code à la création de cet arbre.
Je fais mon programme en JAVA , en recherchant j'ai dois utiliser le JTREE, mais je n'ai aucune idée de comment commencer ceci.
Merci pour l'aide encore une fois
merci Doctor C pour l'animation c'est claire et bien fait.
En fait je pense mon plus grand problème serait la création de cet arbre.
En créant mon jeu, j'ai juste une classe Plateau et une classe Coup mais je n'avais pas créer pour chaque composant(pion, reine...) une classe.
Est ce que vous pensez que ca me prendrais beaucoup de temps pour adapter mon code à la création de cet arbre.
Je fais mon programme en JAVA , en recherchant j'ai dois utiliser le JTREE, mais je n'ai aucune idée de comment commencer ceci.
Merci pour l'aide encore une fois
ok ouai j'ai compris ceci , à présent je devrais passer à essayer de faire de bout de code pour la création d'arbre en java ( avec les jtree) , je me demande est ce que tout ca est dynamique, c'est à dire on doit faire bouger quelque chose et ajouter une branche à cet arbre, puis faire bouger l'adversaire et ajouter un fils....
et récursivement jusqu'à ce qu'on remonte à la racine.
L'avez vous déjà essayer en java?
Est ce que ca prend beaucoup de temps?
et récursivement jusqu'à ce qu'on remonte à la racine.
L'avez vous déjà essayer en java?
Est ce que ca prend beaucoup de temps?
En fait, tu n'as pas à coder un arbre dans ton code.
L'arbre que tu vois est en fait la trace de ta fonction récursive. Le premier noeud (niveau 0) est le premier appel de ta fonction minimax (contenant l'état actuel de la partie). Chaque noeud du niveau 1 représente les différents coups possibles à partir de l'état du niveau 0.
En gros, chaque noeud représente un appel de la fonction minimax et l'abre que tu vois n'est en fait qu'une représentation visuelle de la récursivité.
C'est la même chose que pour, par exemple, la fonction pour calculer un factorielle
Si tu fais la trace, tu vas voir un bel arbre se former mais il n'y en a pas dans le code.
Comme un de mes profs me disait encore et encore, il faut laisser la récursivité travailler d'elle-même.
L'arbre que tu vois est en fait la trace de ta fonction récursive. Le premier noeud (niveau 0) est le premier appel de ta fonction minimax (contenant l'état actuel de la partie). Chaque noeud du niveau 1 représente les différents coups possibles à partir de l'état du niveau 0.
En gros, chaque noeud représente un appel de la fonction minimax et l'abre que tu vois n'est en fait qu'une représentation visuelle de la récursivité.
C'est la même chose que pour, par exemple, la fonction pour calculer un factorielle
public int factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
Si tu fais la trace, tu vas voir un bel arbre se former mais il n'y en a pas dans le code.
Comme un de mes profs me disait encore et encore, il faut laisser la récursivité travailler d'elle-même.
Bonsoir Doctor C,
s'il n'y a pas la création d'un arbre derrière ça , alors comment évaluer les noeuds?
Pour l'évaluation je ne vois pas bien comment ca va se passer dans ce cas!!!
Par exemple je vais affecter des valeurs à mes pièces (1 pion,3 fou, 10 reine....)
Je connais le principe de la récursivité mais ce n'est pas claire comment ca va se passer dans mon cas...
merci d'avance
s'il n'y a pas la création d'un arbre derrière ça , alors comment évaluer les noeuds?
Pour l'évaluation je ne vois pas bien comment ca va se passer dans ce cas!!!
Par exemple je vais affecter des valeurs à mes pièces (1 pion,3 fou, 10 reine....)
Je connais le principe de la récursivité mais ce n'est pas claire comment ca va se passer dans mon cas...
merci d'avance
Effectivement, pas besoin d'arbre. Tout du moins dans l'immédiat.
Lorsque tu fais une récursivité, il y a empilement dans le pile des valeurs (ce qui revient à l'arbre).
L'arbre par contre peut être une bonne idée d'évolution pour stocker les positions (hashtable). Ainsi pas besoin de recalculer des positions par la suite.
Mais pour l'instant l'arbre tu en as absolument pas besoin.
Cdlt,
Lorsque tu fais une récursivité, il y a empilement dans le pile des valeurs (ce qui revient à l'arbre).
L'arbre par contre peut être une bonne idée d'évolution pour stocker les positions (hashtable). Ainsi pas besoin de recalculer des positions par la suite.
Mais pour l'instant l'arbre tu en as absolument pas besoin.
Cdlt,
en cherchant encore plus, je vois que la fonction minmax ou alphabeta prend en paramètre P qui peut être soit une feuille soit un noeud, si je n'ai pas un arbre fait au préalable, alors que dois je lui donner en paramètre?
Les algo données dans la littérature me font croire qu'il existe un arbre et qu'on donne à la fonction une branche....
Est ce que vous avez un bout de code en java , pour se baser ou démarrer avec ?
Les algo données dans la littérature me font croire qu'il existe un arbre et qu'on donne à la fonction une branche....
Est ce que vous avez un bout de code en java , pour se baser ou démarrer avec ?
Tu passes en paramètre un objet (l'échiquier) et la profondeur.
Tu parcours l'ensemble des coups possibles.
Tu simules le coup et tu rappelles la fonction avec la nouvelle position (appel récursif) en diminuant la prodonfeur.
Tu reviens en arrière.
Pas besoin d'arbre.
J'ai pas de bout de code java sous la main. Si je retrouve le projet que j'avais fait, je te posterai la fonction alphabeta (et minmax). Mais je te promets rien ;-)
Tu parcours l'ensemble des coups possibles.
Tu simules le coup et tu rappelles la fonction avec la nouvelle position (appel récursif) en diminuant la prodonfeur.
Tu reviens en arrière.
Pas besoin d'arbre.
J'ai pas de bout de code java sous la main. Si je retrouve le projet que j'avais fait, je te posterai la fonction alphabeta (et minmax). Mais je te promets rien ;-)
Bonjour les amis, je suis de retour encore à vous.
J'ai pu avancer dans mon projet et comprendre le principe de L'IA, mais vraiment je suis blogué depuis plusieurs jours sur un problème.
Ma fonction minmax ne me retourne pas le bon résultat et je n'arrives pas àn trouver ou est le problème, merci de me faire la remarque .
Voici la partie concernée de mon code.
Ca me prend tellement du temps et à la fin ca bloque le tout , parfois me retourne un mauvais coup...
merci d'avance
J'ai pu avancer dans mon projet et comprendre le principe de L'IA, mais vraiment je suis blogué depuis plusieurs jours sur un problème.
Ma fonction minmax ne me retourne pas le bon résultat et je n'arrives pas àn trouver ou est le problème, merci de me faire la remarque .
Voici la partie concernée de mon code.
public Coup minmax(Coup coup,int profondeur,MaFenetre fenetre)
{
return MaxMove(coup,profondeur,fenetre);
}
public Coup MaxMove(Coup coup,int profondeur,MaFenetre fenetre)
{
if(profondeur==0)
{
return evaluerPiece(coup);
}
else
{
ArrayList<Coup> listeCoups = new ArrayList();
Coup meilleurcoup= new Coup(0, 0);
Coup moncoup= new Coup(0, 0);
meilleurcoup.setValeur(0);
for(int i=0 ; i<8;i++)
{
for(int j=0 ; j<8 ;j++)
{
if(champs[getChamps(i,j)] != CV)
{
listeCoups=fenetre.getEchiquierCourant().coupPossiblesBlanc(i,j);
for(int k=0 ; k<listeCoups.size();k++)
{
fenetre.faireCoup((Coup)(Coup)listeCoups.get(k));
moncoup = MinMove((Coup)listeCoups.get(k),profondeur-1,fenetre);
fenetre.annulerCoup();
if(moncoup.getValeur() > meilleurcoup.getValeur())
{
meilleurcoup=moncoup;
}
}
}
}
}
return meilleurcoup;
}
}
public Coup MinMove(Coup coup , int profondeur,MaFenetre fenetre)
{
if(profondeur==0)
{
return evaluerPiece(coup);
}
else
{
ArrayList<Coup> listeCoups = new ArrayList();
Coup meilleurcoup= new Coup(0, 0);
Coup moncoup= new Coup(0, 0);
meilleurcoup.setValeur(0);
for(int i=0 ; i<8;i++)
{
for(int j=0 ; j<8 ;j++)
{
if(champs[getChamps(i,j)] != CV)
{
listeCoups=fenetre.getEchiquierCourant().coupPossiblesNoir(coup.getSourceLigne(), coup.getSourceColonne());
for(int k=0 ; k<listeCoups.size();k++)
{
fenetre.faireCoup((Coup)(Coup)listeCoups.get(k));
moncoup = minmax((Coup)listeCoups.get(k),profondeur - 1,fenetre);
fenetre.annulerCoup();
if(moncoup.getValeur() < meilleurcoup.getValeur())
{
meilleurcoup=moncoup;
}
}
}
}
}
return meilleurcoup;
}
}
Ca me prend tellement du temps et à la fin ca bloque le tout , parfois me retourne un mauvais coup...
merci d'avance
