IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

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

Intelligence artificielle Discussion :

Algorithme alpha-bêta : pseudo code


Sujet :

Intelligence artificielle

  1. #1
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut Algorithme alpha-bêta : pseudo code
    Bonjour,

    Je voudrais une explication par rapport à ce code :

    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
     
     
    int alphabêta(int depth, int alpha, int bêta)
    {
       if (game over or depth <= 0)
          return winning score or eval();
       move bestmove ;
       for (each possible move m) {
          make move m;
          int score = -alphabêta(depth - 1, -bêta, -alpha)
          unmake move m;
          if (score >= alpha){
             alpha = score ;
             bestMove = m ;
             if (alpha >= bêta)
                break;
          }
       }
       return alpha;
    }
    En première lecture je pensais à une erreur d'indentation en ligne 6 , mais j'ai trouvé la même chose en différents endroits sur internet.
    Je ne comprend pas : la première fois que l'on appelle alphabeta() on ne passe pas dans le if ligne 4 donc on commence systématiquement par jouer "bestmove" mais d'où sort-il ? On n'a pas encore déterminé m !

    Je vous remercie par avance pour une explication éclairée

  2. #2
    Membre actif

    Homme Profil pro
    Étudiant
    Inscrit en
    Juillet 2014
    Messages
    103
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juillet 2014
    Messages : 103
    Points : 224
    Points
    224
    Par défaut
    Bonjour,

    Ligne 5 : En premier lieu je dirais qu'il y a un problème par rapport à ce code, je n'ai jamais vu de return a or b si a et b ne sont pas des booléens...

    Ensuite, comme votre variable bestmove est utilisée dans votre boucle, il faut la déclarer avant la boucle, dans laquelle sa valeur sera affectée.

    L'indentation du code semble donc correcte. Sinon je vous recommande un article de wikipedia qui m'a été très utile dans mes études et que je trouve un peu plus clair :

    http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta

  3. #3
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    OK,

    C'est possible qu'il y ait un problème par rapport à ce code, mais comme je l'ai dit j'ai trouvé des choses identiques sur internet.

    C'est un pseudo code proche du langage C puisque la fonction est typée en int, c'est le langage avec lequel je travaille.
    Mais cela ne sert à rien que je commence à coder tant que je n'aurais pas compris l'algo !
    Je ne m'étais pas arrêté sur la ligne 5 mais c'est vrai que ce n'est pas logique : il ne faut pas prendre "or" comme un opérateur !
    En ligne 5 je comprends qu'il faut retourner le résultat de la fonction eval() donc un int.

    Pour moi "move bestmove" (ligne 6) c'était jouer le meilleur coup parmi les m explorés et déterminé justement par l'algo : voir bestmove = m en ligne 13.

    Ensuite, comme votre variable bestmove est utilisée dans votre boucle, il faut la déclarer avant la boucle, dans laquelle sa valeur sera affectée.
    Je ne suis pas d'accord avec cette phrase : comment affecter cette variable avant l'appel à la fonction alphabeta() ?
    Aucun algo alpha-beta en negamax n'a besoin d'une telle variable.

    Revenons à wikipédia (merci pour le lien):
    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
     
    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 = Val
                   si Meilleur > A alors
                       A = Meilleur
                       si A ≥ B alors
                           retourner Meilleur
                       finsi
                   finsi
               finsi 
           finpour 
           retourner Meilleur
       finsi
    fin
    A partir de ce pseudo-code je voudrais faire apparaître les notions de simuler le coup et de déjouer le coup (exploration de l'arbre) ainsi que celle de jouer le meilleur coup une fois déterminé.
    Ces 3 notions existent dans le premier pseudo-code indiqué et c'est pour cela que j'ai retenu celui-ci.
    Selon wikipédia il me manque le pseudo-code qui appelle la fonction alphabeta() pour jouer le coup.

    Merci si vous pouvez me donner le complément

  4. #4
    Membre actif

    Homme Profil pro
    Étudiant
    Inscrit en
    Juillet 2014
    Messages
    103
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juillet 2014
    Messages : 103
    Points : 224
    Points
    224
    Par défaut
    Citation Envoyé par nanosoft Voir le message

    OK,

    Je ne suis pas d'accord avec cette phrase : comment affecter cette variable avant l'appel à la fonction alphabeta() ?
    Aucun algo alpha-beta en negamax n'a besoin d'une telle variable.
    En fait, la variable bestmove est affectée pendant l'appel suivant à la fonction alphabeta() ; ensuite elle persiste durant toute l'exécution de l'intégralité du code. En effet, alphabeta() est une fonction récursive qui va être initialisée au sommet et s'appeler elle-même jusqu'à la condition d'arrêt.

    Citation Envoyé par nanosoft Voir le message

    Selon wikipédia il me manque le pseudo-code qui appelle la fonction alphabeta() pour jouer le coup.

    Merci si vous pouvez me donner le complément
    Le pseudo-code dont vous avez besoin ici n'est donc autre que la fonction alphabeta(P,A,B) elle-même, initialisée pour tous les fils P du sommet de votre arbre, et avec A = - inf et B = + inf.

    Hope it helps !

  5. #5
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Merci mais je voudrais savoir si le premier pseudo-code de la discussion est correct ou non.
    Et s'il n'est pas correct, cela serait super que quelqu'un puisse le corriger.

    En l'état je ne le comprends pas puisqu'on commence par jouer le meilleur coup avant l'exploration et avant toute récursivité !

    En fait, la variable bestmove est affectée pendant l'appel suivant à la fonction alphabeta()
    Mais au premier appel : elle n'est pas affectée !!!!

  6. #6
    Membre éclairé
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Janvier 2010
    Messages
    434
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Janvier 2010
    Messages : 434
    Points : 654
    Points
    654
    Par défaut
    Bonjour,

    Un if qui n'a pas d'accolade donc pas de corp.
    le ; signifie la fin de l'instruction ça revient donc à écrire ceci.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
       if (game over or depth <= 0) return winning score or eval();
       move bestmove ;
    Il n'y a donc pas de probléme d'indentation.

  7. #7
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Bonjour jouana,

    Tout à fait d'accord et c'est bien là ce que je ne comprends pas :
    la première instruction au premier appel de alphabeta() est "move bestmove" ! ?

  8. #8
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    C'est juste une déclaration : "move bestmove;" déclare une variable appelée "bestmove" de type "move".

    --
    Jedaï

  9. #9
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Bonjour,

    Merci Jedai, je vois une autre piste mais je ne comprends toujours pas tout.
    Vous confirmez que ce pseudo code est correct ?
    Une fonction récursive est assez difficile à tester unitairement, je ne voudrais pas partir sur une mauvaise base

    Ce que je voudrais savoir maintenant c'est à quel moment on exploite cette variable bestmove (c'est à dire jouer réellement le coup) ?
    On est bien d'accord que bestmove représente le coup à jouer parmi les coups m qui ont été explorés (il est déterminé en ligne 13) et , durant l'exploration, les coups sont joués puis déjoués systématiquement.
    A quel moment on joue LE coup ? est-ce à l'extérieur de alphabeta() (bestmove serait une variable globale) ?

    EDIT :
    Avec cette nouvelle vision je suis retourné sur internet et il semblerait que cela soit la bonne piste.
    Sur ce lien :
    http://pageperso.lif.univ-mrs.fr/~li...i/MinMaxL2.pdf
    On trouve :
    Il est nécessaire de retourner non seulement le score mais en plus le meilleur coup (en général, on décide de passer une variable par adresse qui contiendra le meilleur coup).
    Dans ce cas dans le jeu, au moment de jouer : on appelle alphabeta() puis ensuite on joue "bestmove".

    J'aimerais bien avoir l'avis et la confirmation d'un "expert"

  10. #10
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Bonjour,

    Je voudrais savoir si l'implémentation en C de l'algo est correcte :
    Code C : 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
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    long int algoA_B(int prof, int jouR, long int alpha, long int beta)
    {
        long int score=0;
        long int retour;    // le retour de la fonction
        int libre=1;        // si il est possible de mettre un pion en x => libre = 1
        int i=1;            // le x à jouer (1 à 7)
        int fin=0;          // flag de fin du jeu (toutes les colonnes sont pleines)
     
        if (gameovera || prof<=0)
        {
            retour = valCoup(jouR);          // heuristique d'évaluation
        }
        else
        {
            for(i=1;i<8;i++)                    // pour tous les coups possibles
            {
                libre=test_libre(i);            // on teste si l'on peut mettre un pion dans cette colonne
                if (libre)
                {
                    simule(i, jouR);            // on joue le coup pour jouR
                    score = -algoA_B(prof-1, 3-jouR, -beta, -alpha); // autre joueur (jouR = 1 ou 2)
                    efface(i);                  // on annule le coup
                    if (score>=alpha)
                    {
                        alpha = score;          // le meilleur coup jusqu'à maintenant
                        bestmove = i;           // le x à jouer
                        if (alpha>beta) break;  // inutile de poursuivre
                    }
                }
     
                else fullCol[i]=1;              //cette colonne est pleine
     
            }
            retour = alpha;                     // on retourne alpha
            fin = testCol();                    // teste si toutes les colonnes sont pleines
            if(fin) gameovera=1;
        }
     
        return retour;
    }

    elle est appelée ainsi :
    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    algoA_B(6, coul(joueurCour), -1000000, 1000000);
        joue_coup(bestmove);

    Merci pour toute aide.

  11. #11
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Bonjour,

    Je n'ai pas encore réussi à faire une implémentation correcte :

    La fonction algoA_B() renvoie une valeur mais elle ne retourne pas le coup à jouer. Jouer "bestmove" comme je l'ai indiqué ne marche pas, cela revient à jouer le dernier coup exploré.

    J'envisage, lors d'un coup à jouer, d'appeler plusieurs fois la fonction algoA_B() pour chaque coup jouable (n coups) : j’obtiens alors n valeurs de retour de la fonction et je joue en définitive le coup ayant conduit à la valeur la plus forte.

    Est-ce la bonne façon de faire ?

  12. #12
    Membre actif

    Homme Profil pro
    autodidacte
    Inscrit en
    Mars 2011
    Messages
    95
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autodidacte

    Informations forums :
    Inscription : Mars 2011
    Messages : 95
    Points : 207
    Points
    207
    Par défaut
    Citation Envoyé par nanosoft Voir le message
    Bonjour,

    Je voudrais savoir si l'implémentation en C de l'algo est correcte :
    Code C : 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
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    long int algoA_B(int prof, int jouR, long int alpha, long int beta)
    {
        long int score=0;
        long int retour;    // le retour de la fonction
        int libre=1;        // si il est possible de mettre un pion en x => libre = 1
        int i=1;            // le x à jouer (1 à 7)
        int fin=0;          // flag de fin du jeu (toutes les colonnes sont pleines)
    
        if (gameovera || prof<=0)
        {
            retour = valCoup(jouR);          // heuristique d'évaluation
        }
        else
        {
            for(i=1;i<8;i++)                    // pour tous les coups possibles
            {
                libre=test_libre(i);            // on teste si l'on peut mettre un pion dans cette colonne
                if (libre)
                {
                    simule(i, jouR);            // on joue le coup pour jouR
                    score = -algoA_B(prof-1, 3-jouR, -beta, -alpha); // autre joueur (jouR = 1 ou 2)
                    efface(i);                  // on annule le coup
                    if (score>=alpha)
                    {
                        alpha = score;          // le meilleur coup jusqu'à maintenant
                        bestmove = i;           // le x à jouer
                        if (alpha>beta) break;  // inutile de poursuivre
                    }
                }
    
                else fullCol[i]=1;              //cette colonne est pleine
    
            }
            retour = alpha;                     // on retourne alpha
            fin = testCol();                    // teste si toutes les colonnes sont pleines
            if(fin) gameovera=1;
        }
    
        return retour;
    }
    1) L'algo est complexe.
    2) Splitter la fonction en sous fonctions serait bien aussi (règle d'or)

    Peut-être essayer d'écrire l'invariant serait utile. Dans ce cadre, tu t'apercevras que efface(i) devrait être placé das le else de if (score > alpha)
    Le but est de retenir les coups supérieurs et d'oublier les inférieurs :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    if (libre)
                {
                    simule(i, jouR);            // on joue le coup pour jouR
                    score = -algoA_B(prof-1, 3-jouR, -beta, -alpha); // autre joueur (jouR = 1 ou 2)
    /* efface (i) , ancienne version */
                    if (score>=alpha)
                    {
                        alpha = score;          // le meilleur coup jusqu'à maintenant
                        bestmove = i;           // le x à jouer
                        if (alpha>beta) break;  // inutile de poursuivre
                    }
                    else efface(i);                  // on annule le coup
                }
    EDIT placement d'un commentaire dans le code proposé
    Toujours à adapter le problème à la structure de la machine, mais se soigne pour faire l'inverse.

  13. #13
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Bonjour,

    Merci pour cette réponse lautrec1, (c'est une réponse à ma question du 01/09) quel est ton avis pour ma question d'hier ?

    L'algo n'est pas très complexe, il est calqué sur ce pseudo-code :
    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
    int alphabeta(int profondeur, int alpha, int beta)
    {
      if (game_over or profondeur <= 0)
        return eval();
      move meilleur_coup;
      for (chaque coup possible m) 
      {
        jouer le coup m;
        int score = -alphabeta(profondeur - 1, -beta, -alpha);
        annuler le coup m;
        if (score >= alpha)
        {
          alpha = score ;
          meilleur_coup = m ;
          if (alpha >= beta)
            break;
        }
      }
      return alpha;
    }
    Je ne comprend pas la proposition suivante :
    Dans ce cadre, tu t'apercevras que efface(i) devrait être placé das le else de if (score > alpha)
    Dans le pseudo-code le jeu et le "déjeu" encadrent très clairement la ligne 9 (appel récursif).

    Cela me ramène à ma question de départ : Ce pseudo-code EST-IL CORRECT ?

    Et s'il est correct comment joue t-on le meilleur coup puisque l'on déjoue systématiquement ?

    Dans l'implémentation que j'ai faite : simule() et efface() sont en fait des manipulations sur un tableau image qui part de la situation du tableau de jeu réel.
    Je retrouve bien mon tableau de départ après un appel à la fonction algoA_B() et ses simulations en profondeur.
    J'ai fait des traces sur les retours de valCoup() et cela a l'air correct.

    Je m'orienterais bien vers l'algo de wikipédia mais la fonction donnée renvoie une valeur. Comment joue t-on le coup ? et quel coup ?
    Je retombe sur ma question d'hier avec le pseudo-code actuel ...

  14. #14
    Membre actif

    Homme Profil pro
    autodidacte
    Inscrit en
    Mars 2011
    Messages
    95
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autodidacte

    Informations forums :
    Inscription : Mars 2011
    Messages : 95
    Points : 207
    Points
    207
    Par défaut
    Citation Envoyé par nanosoft Voir le message
    Bonjour,

    Merci pour cette réponse lautrec1, (c'est une réponse à ma question du 01/09) quel est ton avis pour ma question d'hier ?
    De rien, ton problème m'intéresse.
    Je ne comprend pas la proposition suivante :
    Dans le pseudo-code le jeu et le "déjeu" encadrent très clairement la ligne 9 (appel récursif).
    Tu as raison de ne pas comprendre l'algo wiki ma fait mieux saisir le problème.

    Cela me ramène à ma question de départ : Ce pseudo-code EST-IL CORRECT ?
    Et s'il est correct comment joue t-on le meilleur coup puisque l'on déjoue systématiquement ?
    [QUOTE=nanosoft;7894194]
    A part make move m et umake move m et le break qui tient lieu de return alpha. C'est presque l'algo NegaMax de Aho et Ullman que retrouves en 2è position sur Wiki.
    La seule différence est qu'une structure globale garde la trace des mouvements successifs dans ton pseudocode..
    Mets les bestMove successifs dans une pile globale (ou les printf dans un premier temps), tu auras la suite des mouvements optimaux.

    Dans l'implémentation que j'ai faite : simule() et efface() sont en fait des manipulations sur un tableau image qui part de la situation du tableau de jeu réel.
    Je retrouve bien mon tableau de départ après un appel à la fonction algoA_B() et ses simulations en profondeur.
    J'ai fait des traces sur les retours de valCoup() et cela a l'air correct.
    Bravo

    Bonne suite. Donne-nous des nouvelles

    Citation Envoyé par nanosoft Voir le message
    Bonjour,

    Merci pour cette réponse lautrec1, (c'est une réponse à ma question du 01/09) quel est ton avis pour ma question d'hier ?
    De rien, ton problème m'intéresse.
    Je ne comprend pas la proposition suivante :
    Dans le pseudo-code le jeu et le "déjeu" encadrent très clairement la ligne 9 (appel récursif).
    Tu as raison de ne pas comprendre l'algo wiki ma fait mieux saisir le problème.

    Cela me ramène à ma question de départ : Ce pseudo-code EST-IL CORRECT ?
    Et s'il est correct comment joue t-on le meilleur coup puisque l'on déjoue systématiquement ?

    A part make move m et umake move m et le break qui tient lieu de return alpha, c'est le code qui provient de la page suggérée par jimmy.
    Mais ce wiki m'a l'air complexe de nouveau. Je propose une alternative plus bas.

    La seule différence globale est qu'une structure globale garde la trace des mouvements successifs dans ton pseudocode..
    Mets les bestMove successifs dans une pile globale (ou les printf dans un premier temps), tu auras la suite des mouvements optimaux.

    Tu peux trouver un algorithme beaucoup plus clair sur wiki chessprogramming :
    http://chessprogramming.wikispaces.com/Alpha-Beta

    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
    23
    24
    25
    26
    27
    28
    alpha et beta sont des lower et upper bounds sur le score final.
    
    //optimiser le coup du joueur blanc
    int alphaBetaMax( int alpha, int beta, int depthleft ) {
       if ( depthleft == 0 ) return evaluate();
       for ( all moves) {
          score = alphaBetaMin( alpha, beta, depthleft - 1 ); //voir la réponse du joueur noir
          if( score >= beta ) // l'upperbound peut être au moins augmentée
             return beta;   // on choisit le coup qui augmente l'upperbound
          if( score > alpha ) // sinon, si on a trouvé le moyen de faire mieux que la lower bound, 
             alpha = score;  //alors on a au moins une nouvelle lower bound égale au score évalué et on renvoie cette valeur
       }
       return alpha;
    }
     
    //optimiser pour le joueur noir
    int alphaBetaMin( int alpha, int beta, int depthleft ) {
       if ( depthleft == 0 ) return -evaluate();
       for ( all moves) {
          score = alphaBetaMax( alpha, beta, depthleft - 1 ); //voir la réponse du joueur blanc
          if( score <= alpha ) //la lowerbound peut être au moins diminuée
             return alpha; // on choisit le coup qui diminue la lowerbound
          if( score < beta ) // sinon, si on a trouvé le moyen de diminuer l'upper bound, 
             beta = score; //on a donc une nouvelle upper bound égale au score évalué et on renvoie cette valeur
       }
       return beta;
    }
    Il faut bien sûr appeler mone et unmove autour de l'appel récursif.

    Bonne suite. Donne-nous des nouvelles
    Toujours à adapter le problème à la structure de la machine, mais se soigne pour faire l'inverse.

  15. #15
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    Mai 2012
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : Mai 2012
    Messages : 13
    Points : 33
    Points
    33
    Par défaut
    Bonjour,

    Je m'interroge sur l'algorithme que tu as présenté le 01/09/2014.

    Tout d'abord, 7 colonnes, éventuellement pleines, ça sent le puissance 4...
    J'ai lu l'algo sous cette angle et ce d'autant plus que j'en ai fait un il y a une dizaine d'années.

    Donc :
    Question :
    Quelle est l'utilité de la ligne 31 (else fullCol[i]=1; ) et de gameover ?
    Si tu as besoin d'un indicateur des colonnes pleines l'occupation de la dernière case de chaque colonne ne suffit-elle pas ?
    De plus, j'ai l'impression que fullCol et gameover sont des variables globales. On peut donc légitimement se demander quand reviens-tu en arrière ?
    Suis le raisonnement suivant :
    Tu lances ton algo à 6 coups de la fin (plus que 6 cases vides et une profondeur de 6 ou plus). Lors de la première décente, le jeu est plein quant a été évalué la toute première variante de 6 coups. Donc fullCol[i] == 1 pour tout i ! Et gameover = 1.
    Quand il (l'algo) sera remonté au niveau 1 et qu'il voudra évaluer le deuxième coup, il n'en fera rien car le jeu et officiellement plein d'après tes deux indicateurs.
    Sauf si tu les corriges dans efface(i). Mais je trouve dangereux de ne pas donner à une opération et à son inverse la même visibilité.

    Première remarque :

    Cella a déjà été relevé mais je reviens sur la variable globale bestmove. Si tu utilises la même variable pour tous les niveaux de recherche cela ne peut pas marcher. Supposes que ton meilleur coup soit le premier envisagé. Au niveau 1, il n'y aura jamais de réaffectation. Mais quand tu vas évaluer les autres branches, il va y avoir, aux niveau inférieurs, de multiples affectations de meilleur coup qui vont donner à ta variable bestmove une valeur presque aléatoire quand ton niveau un va répondre.

    Soit tu utilises une pile comme cela a déjà été proposé, soit ta fonction doit retourner deux valeurs (un tableau int[] ?) soit tu gères le premier niveau différemment des suivants car au final, tu n'as besoin de conserver le meilleur coup pour pouvoir le jouer qu'au premier niveau. La seule chose qui t’intéresse au niveau 2 et suivant c'est l'évaluation de la grille.

    Deuxième remarque :

    Bon, là c'est du gagne petit. Mais pourquoi un >= en lieu et place d'un > dans if (score>=alpha) ?
    Entre deux coup qui valent alpha autant garder le premier non ?

  16. #16
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Bonjour,

    Merci pour vos réponses, cela m’encourage à continuer.
    J’ai failli abandonner car j’ai un algo perso (sans exploration d’arbre) qui marche assez bien.

    Bien sur ce n’est pas l’arme ultime d’un mini-max avec une profondeur conséquente … mais il est plus rapide !
    Oui, il s’agit bien d’un Puissance4 et déjà je ne gagne pas à tous les coups lorsque je joue contre l’I.A.

    N’empêche que je n’ai toujours pas la réponse à ma question ! Pseudo-code correct ?

    Tu peux trouver un algorithme beaucoup plus clair sur wiki chessprogramming :
    Je ne sais pas s’il est plus clair mais en Negamax il est différent :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int alphaBeta( int alpha, int beta, int depthleft ) {
       if( depthleft == 0 ) return quiesce( alpha, beta );
       for ( all moves)  {
          score = -alphaBeta( -beta, -alpha, depthleft - 1 );
          if( score >= beta )
             return beta;   //  fail hard beta-cutoff
          if( score > alpha )
             alpha = score; // alpha acts like max in MiniMax
       }
       return alpha;
    }
    On commence par comparer score à beta et non à alpha.
    Quel est le bon ?

    Quelle est l'utilité de la ligne 31 (else fullCol[i]=1; ) et de gameover ?
    J’ai évolué depuis que j’ai posté ce premier code, dans la fonction final() j’évalue si un joueur a gagné, si la profondeur est atteinte ou si toutes les colonnes sont pleines (les colonnes sont actualisées en fonction de simule() et efface().
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
        if (final(prof, jouR))                     
        {
            retour = valCoup(jouR);          // fonction d'évaluation
        }
    Si tu utilises la même variable pour tous les niveaux de recherche cela ne peut pas marcher.
    Je l’ai découvert en débugant : bestmove est maintenant un tableau indexé sur la profondeur.
    Mais je n’ai pas l’intention de le garder : j’oublie bestmove et je vais essayer de le lancer algoA_B() sur chaque coup et de jouer le meilleur. Je pense que c’est cette proposition dans :
    soit tu gères le premier niveau différemment des suivants car au final, tu n'as besoin de conserver le meilleur coup pour pouvoir le jouer qu'au premier niveau
    Je pense que je vais finir par y arriver … si le pseudo code est correct. Quelqu’un peut-il me le confirmer ?

  17. #17
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    Mai 2012
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : Mai 2012
    Messages : 13
    Points : 33
    Points
    33
    Par défaut
    Bonjour,

    Qu'entends tu par pseudo code correct ?

    Le problème des pseudos codes c'est qu'ils sont là pour nous donner une idée de la démarche à suivre. On se permet donc souvent des facilités d'écriture qu'un compilateur bien élevé ne tolèrera pas.

    Exemple dans ton premier pseudo code on a :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
      if (game over or depth <= 0)
          return winning score or eval();
    On comprend bien que cela veut dire que si le jeu est terminé (gain ou plein) ou que l'on est arrivé au bout de la profondeur, il faut retourner respectivement le score gain/perte/nulle ou l'évaluation de la position.
    Mais sauf à le vouloir explicitement, jamais une implémentation ne ressemblera à ça. D'ailleurs, à froid, je ne vois même pas comment faire.

    De plus, tu as bien compris que la variable bestmove n'est pas très utile. Elle sert presque de commentaire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
             alpha = score ;
             bestMove = m ;
    On change la valeur d'alpha parce que l'on a trouvé un meilleur coup.

    Le meilleur coup se trouvera en appelant cette méthode sur chaque coup du premier niveau et en prenant celui correspondant au meilleur score.

    Donc ce premier pseudo code me semble correct. Mais le travail d'implémentation n'est pas neutre.

    Celui de ton dernier message par contre ne me plait pas du tout :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    int alphaBeta( int alpha, int beta, int depthleft ) {
       if( depthleft == 0 ) return quiesce( alpha, beta );
       for ( all moves)  {
          score = -alphaBeta( -beta, -alpha, depthleft - 1 );
          if( score >= beta )
             return beta;   //  fail hard beta-cutoff
          if( score > alpha )
             alpha = score; // alpha acts like max in MiniMax
       }
       return alpha;
    }
    Où joue-t-on les coups, les enlève-t-on ? L'évaluation d'une position ne se fait qu'avec alpha bêta ? Et pourquoi la profondeur à 0 est le seul critère d'arrêt ? Le jeu n'est jamais plein ? Personne ne gagne ?

    Par contre, comparer alpha ou bêta en premier c'est un peu du pareil au même. Si on garde à l'esprit que lorsque l'on arrive à ces if alpha est inférieur à bêta :
    Pour score < alpha : on ne fait rien dans les deux algos.
    pour alpha < score < bêta : on affecte la nouvelle valeur à alpha. (on le fait aussi pour alpha = score dans le premier...)
    pour bêta <= score : on arrête tout et on renvoie score.

    Par contre, je me permettrais une petite remarque : dans tes deux algos le choix de l'ordre des coups à tester a l'aire aléatoire. Et dans tes implémentations tu choisis de balayer les colonnes avec un compteur.

    C'est le plus facile mais ce n'est pas le plus efficace. N'oublies pas que plus tu augmentes tes chances de trouver le bon coup vite plus l'élagage de l'arbre par l'alpha bêta est efficace.

    Mais n'allons pas trop vite. Tu amélioreras ça quand le reste tournera.

  18. #18
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Bonjour,

    Je suis bien d’accord avec ta démarche, Vincent.
    Voici l’implémentation actuelle :
    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
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    long int algoA_B(int prof, int jouR, long int alpha, long int beta)
    {
        long int score=0;
        long int retour;     // le retour de la fonction
        int libre=1;           // si il est possible de mettre un pion en x => libre = 1
        int i=1;                 // le x à jouer (1 à 7)
     
        if (final(prof, jouR))                  		// plein ou gagné ou prof atteinte
        {
            retour = valCoup(jouR, prof);      	// fonction d'évaluation
        }
        else
        {
            for(i=1;i<8;i++)                    // pour tous les coups possibles
            {
                libre=test_libre(i);            // on teste si l'on peut mettre un pion dans cette colonne
                if (libre)
                {
                    simule(i, jouR, prof);              	// on joue le coup pour jouR
                    score = -algoA_B(prof-1, 3-jouR, -beta, -alpha); // autre joueur (jouR = 1 ou 2)
                    efface(i, prof);                    	// on annule le coup
                    if (score>=alpha)
                    {
                        alpha = score;                 	// le meilleur coup jusqu'à maintenant
                        if (alpha>beta) break;          	// inutile de poursuivre
                    }
                }
     
            }
            retour = alpha;                     		// on retourne alpha
        }
        return retour;
    }
    J’appelle maintenant la fonction de cette manière :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
        for(i=1;i<8;i++)
        {
            retourAB[i] = -100000;  // pour les coups non libres
                if (test_libre(i))          // on teste si l'on peut mettre un pion dans cette colonne
                {
                    simule(i ,coul(joueurCour),profondeur);
                    retourAB[i] = -algoA_B(profondeur-1, 3-coul(joueurCour), -100000, 100000);
                    efface(i, profondeur);
                }
     
        }
    et je joue le i qui retourne la plus grande valeur de retourAB[]

    suite à ta remarque je ne vois pas comment je pourrais éviter de faire une simulation sur chaque colonne ? ni définir un ordre préférentiel ?

  19. #19
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    Mai 2012
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : Mai 2012
    Messages : 13
    Points : 33
    Points
    33
    Par défaut
    Là ton code commence à me plaire.

    À priori ça devrait tourner.

    Tu vas pouvoir commencer à t'amuser.

    Ton dernier message se termine sur deux questions.

    La première :

    Citation Envoyé par nanosoft Voir le message
    suite à ta remarque je ne vois pas comment je pourrais éviter de faire une simulation sur chaque colonne ?
    Mais c'est l'apha-bêta qui s'en charge! C'est donc déjà fait.

    Pour l'essentiel.

    Je reviendrais peut-être sur cette affirmation plus tard.

    Mais dans l'immédiat voyons la seconde question*:

    Citation Envoyé par nanosoft Voir le message
    ni définir un ordre préférentiel ?
    Et là un monde nouveau s'ouvre à toi.

    Mais pour te le présenter je vais d'abord attirer ton attention sur le nombre de nœuds de ton arbre.

    Pour rester compréhensible il faut souvent se limiter à des exemples simples. Prenons donc une grille vide et appliquons une recherche de profondeur 6.

    On ne dépassera jamais la capacité d'une colonne et on n'alignera jamais 4 jetons.

    Donc avec un min-max de base, on balayerais tout l'arbre des possibilités.

    Ça fait*: 7^1 + 7^2 + 7^3 + 7^4 + 7^5 + 7^6 = 137256
    (suite géométrige)

    Le dernier étage représentant 7^6=117349

    Où tu voix que c'est vraiment les feuilles qui coûtent. Bon jusque là rien de nouveau.

    Pour suivre l'évolution de ton alpha bêta, je t'invite à ajouter un petit compteur dans ton code. Pour visualiser le nombre de nœuds que tes implémentations vont t'épargner.

    Maintenant revenons au puissance 4.

    Voici une position :

    ------
    ------
    ------
    ------
    --xx--
    -xooo-

    Aux croix de jouer. Nous voyons tous qu'il y a urgence à jouer dans la colonne 7. Mais combien de temps ton algorithme va mettre pour le comprendre ?

    Dans un premier temps il va remplir la première colonne. Puis déplacer le rond du haut dans chacune des colonnes suivantes. Pour finir, il tombera sur la dernière. Mais n'en déduira rien d'autre que 5 coups dans la première colonne c'est mortel au sixième. Il recommencera avec 4 coups dans la première, une croix dans la deuxième et c'est reparti pour 7 coups de rond avant de retomber sur le problème.

    Et si, au lieu de te contenter de l'alpha et du beta tu lui transmettais également les coups tueurs? Pour simplifier le raisonnement: disons que tu passes à l'étage du dessous la colonne (éventuellement pleine quand même) à tester en premier et qui correspondrais au meilleur de la variante précédente ?
    Et bien on ne testera plus que le coup perdant (score = bêta à chaque premier coup). On passe de 7 coups à 1.

    Mieux, beaucoup mieux, quand au premier niveau, ton algo aura fini d'analyser la première colonne comme premier coup. Il aura compris qu'il y a un coup tueur pour l'adversaire à la 7ième ( faudrait en plus conserver la profondeur de gain car toutes les variantes sont gagnantes).
    Donc dès qu'il commence avec une croix dans la deuxième, il tente un rond dans la septième et c'est fini. Là c'est des centaines de nœuds que tu vires !

    Le seul hic, c'est que cette méthode ne marche que quand le jeu a déjà bien commencer.

    Il y a mieux. Mais plus compliqué.

    Exemple de solution. Tu appliques une profondeur de 6. Donc quand l'adversaire répond, sauf au premier coup, tu as déjà partiellement étudier cette réponse avec une profondeur de 4!

    Suppose que tu ais stocké l'évaluation des ces réponses ? Et bien tu les rejoues dans l'ordre décroissant.

    Tu peux aussi ranger les coups en fonction du plus grand nombre de jetons alignés qui aboutissent à la case.

    Faire des mixtes entre les solutions (plus grand alignement + coup tueur s'il y en un )

    Les choix sont immenses. L'efficacité de chaque choix dépendant de ton algo d'évaluation de la position.

    Bref, des heures de test en perspectives.

    Bon courage.

  20. #20
    Membre averti
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Juin 2012
    Messages
    257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2012
    Messages : 257
    Points : 321
    Points
    321
    Par défaut
    Voilà cela tourne

    C’est presque trivial maintenant !

    Je mets mon sujet en résolu et je vous fais partager mon expérience (je n’en ai pas vu beaucoup lors de mes premières recherches).

    C’était ma première implémentation de fonction récursive, j’ai mis beaucoup de temps à tester et à mettre au point pour les raisons suivantes :
    - la compréhension de ce foutu « move bestmove »
    - difficulté de faire des tests « unitaires » : j’ai testé en jouant des parties !
    - au début mes fonctions simule() et efface() n’étaient pas correctes : comme on ne déjoue pas dans le même ordre que le jeu, il faut tenir compte de la profondeur
    - la fonction d’évaluation est très importante : si elle ne chiffre que les coups gagnants, en début de jeu et avec une profondeur limitée cela joue n’importe quoi

    Actuellement avec une profondeur de 7 l’I.A. mets 7s. pour réfléchir , mais comme tu le dis cela ne veut pas dire 1s par niveau !
    Je vais maintenant travailler sur mon algo déterministe sans exploration (je propose le choix entre cet algo rapide ou le mini-max dans mon jeu).
    Après l’idée de mixer les deux, j’y ai déjà pensé mais ce n’est pas évident : dans mon algo perso je construit la situation d’évaluation au fur et à mesure des coups joués. Je ne peux pas l’exploiter dans le mini-max car le « déjeu » nécessaire serait trop compliqué.

    J’aime bien l’idée d’enregistrer les branches déjà explorées, je vais y réfléchir …

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme Alpha Béta
    Par titme dans le forum Intelligence artificielle
    Réponses: 2
    Dernier message: 15/04/2011, 21h27
  2. Difference Algorithme / Pseudo code
    Par elmander dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 01/03/2010, 13h24
  3. Algorithme alpha béta
    Par Bathou dans le forum Intelligence artificielle
    Réponses: 11
    Dernier message: 16/02/2010, 12h47
  4. Puissance 4 : algorithme MiniMax (alpha-béta)
    Par sperca dans le forum Intelligence artificielle
    Réponses: 9
    Dernier message: 26/04/2008, 21h46
  5. Algorithmes de generateur pseudo-aleatoire
    Par funx dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 06/09/2002, 19h33

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo