Bonjour à toutes et à tous,

je suis actuellement en train de faire un jeu de puissance 4 en orienté objet, et je voulait implémenter l'algorithme du MinMax pour mon IA (ce qui est déjà fait). Seul bémol, mon IA joue un peu n'importe quoi, ne cherche pas à me bloquer, et avec une profondeur de 4, je gagne facilement... Je pense avoir bien coder mon algorithme mais j'ai un doute sur mes fonctions d'évaluations... Cela fait plus d'une semaine que je cherche à résoudre mon problème, mais rien à faire. Si vous arrivez à trouver ce qui ne va pas, je vous serai extrêmement reconnaissant, car à l'heure actuelle, le tabouret et la corde me guettent...

Je vous remercie d'avance pour le temps que vous consacrerez à la lecture et la compréhension de mon code :

int Jeu::nbJetonsAlignes(Grille& G, Jetons& joueur, const int& nb){
    int somme=0;
    matrice M=G.get_matrice();
    char symbole=joueur.get_symbole();
    //horizontal
    for (unsigned int i=0; i<M.size(); i++){
        for (unsigned int j=0; j<M[0].size()-nb+1; j++){
            int nb_alignes=0;
            int rang=0;
            bool fini=false;
            while ((rang<=nb)&&(fini==false)){
                if (M[i][j+rang]==symbole){
                    nb_alignes++;
                    if (nb_alignes==nb){
                        fini=true;
                    }
                }
                else{
                    fini=true;
                }
                rang++;
            }
            if (fini && nb_alignes==nb){
                somme++;
            }
        }
    }
    //test vertical
    for (unsigned int i=0; i<M.size()-nb+1; i++){
        for (unsigned int j=0; j<M[0].size(); j++){
            int nb_alignes=0;
            int rang=0;
            bool fini=false;
            while ((rang<=nb)&&(fini==false)){
                if (M[i+rang][j]==symbole){
                    nb_alignes++;
                    if (nb_alignes==nb){
                        fini=true;
                    }
                }
                else{
                    fini=true;
                }
                rang++;
            }
            if (fini && nb_alignes == nb){
                somme++;
            }
        }
    }
    //test diagonal 1
    for (unsigned int i=0; i<M.size()-nb+1; i++){
        for (unsigned int j=0; j<M[0].size()-nb+1; j++){
            int nb_alignes = 0;
            int rang=0;
            bool fini = false;
            while (rang <=nb&& fini == false){
                if (M[i+rang][j+rang]==symbole){
                    nb_alignes++;
                    if (nb_alignes == nb){
                        fini=true;
                    }
                }
                else{
                    fini=true;
                }
                rang++;
            }
            if (fini && nb_alignes == nb){
                somme++;
            }
        }
    }
    //test diagonal 2
    for (unsigned int i=0; i<M.size()-nb+1; i++){
        for (unsigned int j=0+nb-1; j<M[0].size()+1; j++){
            int nb_alignes = 0;
            int rang=0;
            bool fini=false;
            while ((rang<=nb)&&(fini==false)){
                if (M[i+rang][j-rang]==symbole){
                    nb_alignes++;
                    if (nb_alignes==nb){
                        fini=true;
                    }
                }
                else{
                    fini=true;
                }
                rang++;
            }
            if (fini && nb_alignes==nb){
                somme++;
            }
        }
    }
    return somme;
}

int Jeu::nbJetonsCentre(Grille& G, Jetons& joueur){
    matrice M=G.get_matrice();
    int compteur{0};
    int centre=M[0].size()%2;
    char symbole=joueur.get_symbole();
    for (unsigned int i=0; i<M.size(); ++i){
        if (M[i][centre]==symbole){
            compteur+=1;
        }
    }
    return compteur;
}

int Jeu::score(Grille& G, Jetons& ordi, Jetons& adversaire){
    int s=0;

    s+=(nbJetonsAlignes(G,ordi,1)*1);
    s+=(nbJetonsAlignes(G,ordi,2)*5);
    s+=(nbJetonsCentre(G,ordi)*25);
    s+=(nbJetonsAlignes(G,ordi,3)*50);
    s+=(nbJetonsAlignes(G,ordi,4)*1000);

    s-=(nbJetonsAlignes(G,adversaire,1)*1);
    s-=(nbJetonsAlignes(G,adversaire,2)*5);
    s-=(nbJetonsCentre(G,adversaire)*25);
    s-=(nbJetonsAlignes(G,adversaire,3)*50);
    s-=(nbJetonsAlignes(G,adversaire,4)*1000);

    return s;
}

int Jeu::gagnant(Grille& G, Jetons& adversaire, Jetons& ordi){
    int gagnant{3}; //3=match nul
    matrice M=G.get_matrice();
    if (G.gagner(G.gagnerEnColonne(adversaire),G.gagnerEnLigne(adversaire),G.gagnerEnDiagonale(adversaire))==1){
        gagnant=1;
    }
    if (G.gagner(G.gagnerEnColonne(ordi),G.gagnerEnLigne(ordi),G.gagnerEnDiagonale(ordi))==1){
        gagnant=2;
    }
    else{
        for (unsigned int i=0; i<M.size(); ++i){
            for (unsigned int j=0; j<M[0].size(); ++j){
                if (M[i][j]==' '){
                    gagnant=0;
                    break;
                }
            }
        }
    }
    return gagnant;
}

int Jeu::evaluerJeu(Grille& G, Jetons& adversaire, Jetons& ordi){
    int etat{0};
    int nb_jetons{0};
    matrice M=G.get_matrice();
    for (unsigned int i=0; i<M.size(); ++i){
        for (unsigned int j=0; j<M[0].size(); ++j){
            if (M[i][j]!=' '){
                nb_jetons+=1;
            }
        }
    }
    int vainqueur=gagnant(G,adversaire,ordi);
    if (vainqueur!=0){
        if (vainqueur==1){
            etat=-1000+nb_jetons;
        }
        if (vainqueur==2){
            etat=1000-nb_jetons;
        }
        if (vainqueur==3){
            etat=0;
        }
    }
    else{
        etat=score(G,ordi,adversaire);
    }
    return etat;
}

int Jeu::IA(Grille G, Jetons adversaire, Jetons ordi, const int& profondeur){
    matrice M=G.get_matrice();
    int maxi{-10000};
    int evaluation{0};
    int colonneGagnante{0};
    for (unsigned int j=0; j<M[0].size(); ++j){
        if (G.colonnePleine(j+1)==0){
            G.deposerJetonIA(ordi,j+1);
            evaluation=valeurMin(G,adversaire,ordi,profondeur-1);
            if(evaluation>maxi){
                maxi=evaluation;
                colonneGagnante=j+1;
            }
            G.annulerJetonColonneIA(j+1);
        }
    }
    return colonneGagnante;
}

int Jeu::valeurMin(Grille F, Jetons adversaire, Jetons ordi, const int& profondeur){
    int mini{10000};
    int evaluation{0};
    matrice M=F.get_matrice();
    if ((profondeur==0)||(gagnant(F,adversaire,ordi)!=0)||(F.grillePleine()!=0)){
        mini=evaluerJeu(F,adversaire,ordi);
    }
    else{
        for (unsigned int j=0; j<M[0].size(); ++j){
            if (F.colonnePleine(j+1)==0){
                F.deposerJetonIA(adversaire,j+1);
                evaluation=valeurMax(F,adversaire,ordi,profondeur-1);
                if (evaluation<mini){
                    mini=evaluation;
                }
                F.annulerJetonColonneIA(j+1);
            }
        }
    }
    return mini;
}

int Jeu::valeurMax(Grille F, Jetons adversaire, Jetons ordi, const int& profondeur){
    int maxi{-10000};
    int evaluation{0};
    matrice M=F.get_matrice();
    if ((profondeur==0)||(gagnant(F,adversaire,ordi)!=0)||(F.grillePleine()!=0)){
        maxi=evaluerJeu(F,adversaire,ordi);
    }
    else{
        for (unsigned int j=0; j<M[0].size(); ++j){
            if (F.colonnePleine(j+1)==0){
                F.deposerJetonIA(ordi,j+1);
                evaluation=valeurMin(F,adversaire,ordi,profondeur-1);
                if (evaluation>maxi){
                    maxi=evaluation;
                }
                F.annulerJetonColonneIA(j+1);
            }
        }
    }
    return maxi;
}

- Faire des test unitaire

- Utiliser le débogueur

Problème Résolu !!!

Je te remercie bacelar, en testant le score que renvoyait la fonction score pour chaque colonne, et en testant avec une profondeur de 1, j'ai pu remarquer qu'en fait, mon score ne faisait que croître au fur et a mesure qu'on testait les colonnes. En fait, ma fonction annulerJetonColonne n'annulait pas vraiment le jeton déposé (erreur de ma part dans la fonction, je pensais avoir bien fait) et donc mon score ne pouvait qu'augmenter puisqu'il augmentait le score de l'IA, qui jouait du coup à l'opposer de moi, c'est à dire là ou tout ses jetons étaient alignés.

J'avais déjà essayé avec le débogueur mais sans plus.

Tu me libère d'un poids énorme !!! 

Merci merci merci =)

-
Edité par Makinetoche 3 décembre 2019 à 12:39:04

Alors petit retour d'expérience sur ce post pour partager du coup un autre problème qui est apparu après mon message de la veille :

Le test unitaire m'a effectivement permis de régler un énorme problème (celui de la fonction qui n'annulait finalement pas le jeton).

Après cela, mon IA jouait mieux, mais j'avais remarquer que même avec une profondeur 5, il me laissait de temps en temps gagner quand j'avais 3 jetons alignés (ce qui n'est pas normal du tout avec cette profondeur là me direz vous, même une profondeur 2 est censé me bloquer puisqu'il va accéder au tour d'après à l'avance et voir que je vais possiblement faire le puissance 4, et donc jouer en priorité sur la colonne où je vais possiblement jouer mon 4 ième et dernier jeton)

Alors j'ai refait un test unitaire mais cette fois-ci,  sur les fonctions IA, valeurMin et valeurMax, avec profondeur 2 pour n'avoir que 49 valeurs à vérifier... et là, édifiant fut ma stupéfaction lorsque j'eusse remarqué qu'il évalua mon puissance 4 (qui vaut -1000 + le nombre de jetons) à seulement... -109 !!!!

Donc voilà, j'ai continuer mes tests unitaires plus en profondeur jusqu’à remarquer que la fonction gagnant me retournait toujours... 0. Et ce même en détectant que je gagnerai !!!

J'ai donc réfléchi pendant 30 minutes au pourquoi du comment ce retour de la part de cette fonction, tout essayé, pour qu'en fait, le problème vienne finalement... des If.... --'

Au diable j'ai mis "if...if...else..." au lieu de "if...else if...else"... 

Je n'aurais jamais deviner cela tout seul, je ne pensais pas que dans une suite de if, une simple "else" avant de recommencer un "if" pouvait autant être cancérigène...

M'enfin, au bout d’innombrables heures passés sur cette algorithme, voilà que j'aperçois enfin la lumière au bout du tunnel...

Donc de nouveau Bacelar... merci =)

Pensez à bien vérifier les warning et à utiliser les analyseurs statiques de code qui peuvent facilement détecter des mauvaises utilisations des structures du code même si elles sont syntaxiquement correctes.

J'ai tendance à utiliser des switch à la place d'une cascade de if-else.

Factorisez votre code pour que ces cascades ne fassent que quelques lignes (en tout! pas pour chaque if) pour qu'elles soient lisibles.

Ici, des switchs ne sont pas applicables.

Par contre, il ne faut pas hésiter à extraire les fonctions de comptage de pions alignés. D'ailleurs, pas besoin de tout tester. Il suffit de tester quel est le nombre de pions alignés si on joue dans une colonne donnée. Cf mon expérience très similaire: https://github.com/LucHermitte/tictactoe/blob/master/tictactoe.cpp