Journal Optimisation des tests pour un morpion.

Posté par  (site web personnel) .
Étiquettes : aucune
0
18
nov.
2003
Salut.

Voilà je suis en train de programmer une sorte de morpion ou les pions peuvent se deplacer

j'ai un terrain comme ceci:

int plateau[NB_LIG_PLAT][NB_COL_PLAT] =
{
{0,0,0},
{0,0,0},
{0,0,0}
};

les cases peuvent prendre les valeurs:
NOIR 2
BLANC 1
VIDE 0

J'ai besoin d'un fonction qui me disent si un plateau est gagnant pour le noir, pour le blanc ou si il est egalité.
J'ai fait cette fonction là mais ma gestion des if est tres bourrin. Je ne sais pas si il y'a moyen de l'optimiser, et si c'est le cas, si il y'a une methode precise. Je pense que ça doit etre possible avec un tableau de karnaugh ou quelque chose du genre.

Voilà ma fonction:

int eval_plateau()
{
int ennemie;
int gagnant = VIDE;


//TEST DES LIGNES
if (plateau[0][0] == plateau[0][1] == plateau[0][2] != VIDE)
gagnant = plateau[0][0];
if (plateau[1][0] == plateau[1][1] == plateau[1][2] != VIDE)
gagnant = plateau[1][0];
if (plateau[2][0] == plateau[2][1] == plateau[2][2] != VIDE)
gagnant = plateau[2][0];

//TEST DES COLONNES
if (plateau[0][0] == plateau[1][0] == plateau[2][0] != VIDE)
gagnant = plateau[0][0];
if (plateau[0][1] == plateau[1][1] == plateau[2][1] != VIDE)
gagnant = plateau[0][1];
if (plateau[0][2] == plateau[1][2] == plateau[2][2] != VIDE)
gagnant = plateau[0][2];

//TEST DES DIAGONALES
if (plateau[0][0] == plateau[1][1] == plateau[2][2] != VIDE)
gagnant = plateau[0][0];
if (plateau[0][2] == plateau[1][1] == plateau[2][0] != VIDE)
gagnant = plateau[0][2];

return gagnant;
}

Merci de votre aide.

Juke.

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 1.

    Tes tests sont faux, il faut comparer 2 à deux.
    Preuve :

    int main()
    {
    printf("%d\n", 2 == 2 == 2);
    return 0;
    }
    affiche 0 (faux).

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 0.

    Je pense que le linuxMag de ce mois est fait pour toi. (au passage, si tu peux te denicher celui du mois dernier en prime il sera interessant aussi)

    -> pour info, il y a un dossier sur les algos de decision dans les jeux de strategie...


    mes deux sioux,

    Hugh

    • [^] # Re: Optimisation des tests pour un morpion.

      Posté par  (site web personnel) . Évalué à 0.

      Oui ça fait un bout de temps que je m'interroge sur l'IA et c'est vraiment cet article que j'ai le mieux compris.
      Par contre, ils disent que le code source est sur le cdrom mais je ne l'a ipas trouvé, savez vous où le recuperer ?

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 1.

    Il n'y a pas d'optimisation evidente, tu peux à la limite mettre une boucle pour rendre le code plus cours, mais cela ne changera pas le temps d'execution.
    Karnaugh ne sera pas d'un très grand secours car les variables sont très largement indépendantes.

    Note que ton code est faux :
    (plateau[0][0] == plateau[0][1] == plateau[0][2] != VIDE)
    veut dire (azerty == plateau[0][2] != VIDE)
    avec azerty = (plateau[0][0] == plateau[0][1])
    et un == vaut 0 si les deux membres sont différents et est non nul si les deux membres sont égaux, sans aucune précision sur sa valeur.

    Au lieu de gagnant = plateau[0][0]; tu peux mettre return plateau[0][0]; car dès que tu as détecté un coup gagnant inutile d'en checher d'autre. (et tu met return VIDE à la fin)

    • [^] # Re: Optimisation des tests pour un morpion.

      Posté par  (site web personnel) . Évalué à 0.

      Il n'y a pas d'optimisation evidente, tu peux à la limite mettre une boucle pour rendre le code plus cours, mais cela ne changera pas le temps d'execution.

      C'est justement la question que je me posait.

      Karnaugh ne sera pas d'un très grand secours car les variables sont très largement indépendantes.
      Ha d'accord. Je viens juste d'aborder Karnaugh en cours, et c'est vrai que si c'est independant ça ne vaut rien.

      Au lieu de gagnant = plateau[0][0]; tu peux mettre return plateau[0][0]; car dès que tu as détecté un coup gagnant inutile d'en checher d'autre. (et tu met return VIDE à la fin)

      Oui, en fait c'est parce que ma fonction devais servir à autre chose à l'origine lol. (d'ou la variable ennemie aussi).



      Merci de ton aide.

    • [^] # Re: Optimisation des tests pour un morpion.

      Posté par  . Évalué à 0.


      et un == vaut 0 si les deux membres sont différents et est non nul si les deux membres sont égaux, sans aucune précision sur sa valeur.

      Non, (a==b) vaut 1 si les valeurs de a et b sont identiques,
      0 sinon. Y a des contraintes de type aussi.
      Et ca renvoit une valeur de type int.

      Cherche n843.pdf sur google.

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 0.

    euh, tu l'as testé ton truc ?
    "a == b == c" c'est pas equivalent à "a == (b == c)" ?

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 0.

    int ennemie;
    déclarée mais jamais utilisée.

    Si tu trouves un gagnant, inutile de continuer à tester.
    Maintenant, histoire de clarifier le code, j'aurais codé ca comme ca :
    struct {
    char orig_x;
    char orig_y;
    char dir_x;
    char_dir_y;
    } directions[] = {
    /* lignes */
    { 0, 0, 1, 0 },
    { 0, 1, 1, 0 },
    { 0, 2, 1, 0 },
    /* colonnes */
    {0, 0, 0, 1 },
    {1, 0, 0, 1 },
    {2, 0, 0, 1},
    /* diags */
    {0, 0, 1, 1},
    {0, 2, 1, -1}
    };

    int eval_plateau()
    {
    int i;
    for (i = 0; i < 8; i++)
    {
    struct dir = directions[i];
    if (plateau[dir.orig_x][dir.orig_y] != VIDE)
    if (plateau[dir.orig_x][dir.orig_y] == plateau[dir.orig_x + dir.dir_x][dir.orig_y + dir_y])
    if (plateau[dir.orig_x + dir.dir_x * 2][dir.orig_y + dir.dir_y * 2] == plateau[dir.orig_x + dir.dir_x][dir.orig_y + dir_y])
    return plateau[dir.orig_x][dir.orig_y];
    }
    return VIDE;
    }

  • # Re: Optimisation des tests pour un morpion.

    Posté par  (site web personnel) . Évalué à 1.

    Un truc assez simple et qui décorèle le data path du cotrol path :
    tu fais un tableau contenant les configurations gagantes, puis tu le parcours pour voir si il y a un truc qui matche...
    Ca clarifie le code, et il est facile de changer les fonctionnement du truc

    inline int lire_plateau(coord c)
    {
    return plateau[c.x][c.y];
    }

    typdef struct _coord
    {
    x : int;
    y: int;
    } coord;

    int NB_COUPS_GAGANTS = 8;
    coord [8][3] =
    {
    { {0,0}, {0,1}, {0,2} }, //première ligne horizontale
    { {1,0}, {1,1}, {1,2} }, //ligne 2 horizontale
    { {0,0}, {0,1}, {0,2} }, //ligne 3 horizontale
    { {0,0}, {1,0}, {2,0} }, //ligne 1 verticale
    ... //ajoute les deux lignes restatnes + les deux diagonales
    };

    for (int ii = 0 ; ii < NB_COUPS_GAGNANTS ; ii ++)
    {
    if (
    (lire_plateau(coord[ii][0]) == lire_plateau(coord[ii][1]))
    &&(lire_plateau(coord[ii][1]) == lire_plateau(coord[ii][2]))
    )
    return lire_plateau(coord[ii][0]);
    }
    return VIDE;

    • [^] # Re: Optimisation des tests pour un morpion.

      Posté par  (site web personnel) . Évalué à 0.

      ça a l'air sympa, je vais m'attarder un peu dessus.

      Merci.

      • [^] # Re: Optimisation des tests pour un morpion.

        Posté par  (site web personnel) . Évalué à 1.

        moi je ferais une fonction qui te génère un tableau des gagnants mais pour les 2 couleurs.

        genre

        position gagnant[3][nbg][3][3];

        gagnant_generate( * gagnant); <- fait une fois au début du jeu.

        eval ( position tab[3][3], position gagnant[nbg][3][3])
        {
        for (i = 0;i<nbg;i++)
        if(!!memcomp(tab,gagnant[0][i]))
        return (0);
        for (i = 0;i<nbg;i++)
        if(!!memcomp(tab,gagnant[1][i]))
        return (1);
        for (i = 0;i<nbg;i++)
        if(!!memcomp(tab,gagnant[2][i]))
        return (3);
        }

        C'est plus bourrin mais plus linéaire. Cela devrait être le code le plus rapide et de loin. Si tu veux encore plus te faire chier, tu codes l'info sur 2 bits, un tableau de jeux tient sur 18 bits et la fontion memcomp est un simple teste d'égalité sur un entier de 32 bits.

        "La première sécurité est la liberté"

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 0.

    bin, moi je ferais plutôt un truc du genre :

    (avec NOIR 4)

    gagnant = 0;

    for (i=0 ; i<3 ; i++) {
    for (j=0 ; j<3 ; j++) {
    somme_ligne += tableau[i][j];
    somme_colonne += tableau[j][i];
    }
    if ((somme_ligne == 3) || (somme_colonne ==3)) {
    gagnant = 1;
    break;
    }
    if ((somme_ligne == 12) || (somme_colonne == 12)) {
    gagnant = 4;
    break;
    }
    }

    if ((tableau[0][0] + tableau [1][1] + ... == 3) ||
    (tableau[0][2] + tableau [1][1] + ... == 3))
    gagnant = 1;
    else if ((tableau[0][0] + tableau [1][1] + ... == 12) ||
    (tableau[0][2] + tableau [1][1] + ... == 12))
    gagnant = 4;

    (en vitesse et pas testé)

    • [^] # Re: Optimisation des tests pour un morpion.

      Posté par  (site web personnel) . Évalué à 1.

      Cool l'idée de faire le test pour les lignes et les colonnes en meme temp, moi je faisait 2 boucle (enfin 4 en fait)

      Astucieux.

    • [^] # Re: Optimisation des tests pour un morpion.

      Posté par  (site web personnel) . Évalué à 1.

      Séduisant, dommage qu'on soit obligé de rajouter ce truc pour les diagonales.
      Les break me font un peu frémir, et autant mettre les noms symboliques plutôt que les valeurs :
      if ((somme_ligne == 3*NOIR) || (somme_colonne ==3*NOIR))
      return NOIR;
      if ((somme_ligne == 3*BLANC) || (somme_colonne ==3*BLANC))
      return BLANC;

      Ca me semble + lisible ;o)

      S'il y avait + de deux joueurs, ou un nombre de joueurs variables, on pourrait mettre ça dans une boucle ...

    • [^] # Re: Optimisation des tests pour un morpion.

      Posté par  . Évalué à 1.

      Tiens c'est marrant, j'aurais plutôt multiplié donc 1 ou 8 comme combinaison gagnante mais les solutions précédentes sont nettement meilleures.

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 2.

    Les optimisations se feraient plus facilement lors des ajouts ou déplacements de pions : une fois calculées les combinaisons gagnantes possibles, tu pourras détecter un coup gagnant immédiatement, ou remettre à jour les combinaisons gagnantes possibles après le coup.
    Cela t'économisera les cases vides.

    Exemple d'arbre partiel vite fait :
    Supposons que les blancs jouent en premier, et que tu as numéroté tes cases
    2 7 5
    6 1 8
    4 9 3

    Séquence pour coup blanc en 1, coup noir en 7, coup blanc en 2, coup noir en 3, coup blanc en 4 (les coups restants sont entre crochets) :
    [123456789] -1-> [23456789] -7-> [2345689] -2-> [345689] -3-> [45689] -4-> [5689]

    Depuis ce noeud [5689] on aura entre autres possibilités de coups (joueur noir en premier) :
    -5-> [689] -6-> WHITE
    -5-> [689] -8-> [69] -6-> [9] -9-> VOID
    -5-> [689] -8-> [69] -9-> [6] -6-> WHITE
    -5-> [689] -9-> [68] -6-> [8] -8-> VOID
    -5-> [689] -9-> [68] -8-> BLACK
    -6-> [589] -5-> WHITE
    -6-> [589] -8-> [59] -5-> [9] -9-> VOID
    -6-> [589] -8-> [59] -9-> [5] -5-> WHITE
    -6-> [589] -9-> [58] -5-> [8] -8-> VOID
    -6-> [589] -9-> [58] -8-> [5] -5-> WHITE
    ...

    Ensuite, il ne reste plus qu'à générer cet arbre :)

    • [^] # Re: Optimisation des tests pour un morpion.

      Posté par  . Évalué à 1.

      Petite note : si tu veux gérer des déplacements, ce ne sera non plus un arbre mais un automate puisque il y aura possibilité de boucles infinies.

      En bref le langage des séquences de coups possibles est fini dans le cas d'un simple morpion et régulier dans le cas où tu permets des déplacements, et la structure optimale pour le reconnaître passe d'un arbre à un automate.

  • # Re: Optimisation des tests pour un morpion.

    Posté par  (site web personnel) . Évalué à 2.

    sinon si a chaque coup joue tu lance cette fonction, c'est pas terrible si on commence d'une partie avec rien au debut sur le plateau, ca fait faire beaucoup de calculs qui pourraient etre deja fait;
    a chaque coup qu'une personne joue, tu ferais mieux de verifier sur la colonne, la diagonale, et la ligne ou le coup a été joué si cela n'entraine pas une combinaison gagnante.

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 3.

    Bon ben voila ce que je ferais dans ton cas.
    Chaque grille peut etre codee dans un entier. L'occupation de chaque case est codee sur 2 bits: 00 vide, 01 croix et 10 rond. Ensuite a chaque case est associee un decalage:
    0 2 4
    6 8 10
    12 14 16
    Pour regarder l'occupation d'une case, il te suffit de faire l'operation sur l'entier [grille] qui definit la grille:
    ([grille] >> decalage) & 0x3


    Pour regarder si une grille est gagnante:

    Tu calcules toutes les combinaisons gagnantes pour les croix.
    Par exemple, 0x15 est la combinaison pour la ligne horizontale passant par les cases du haut.

    Celles pour les ronds s'obtiennent par un simple decalage de 1 vers la gauche des conbinaisons gagnantes pour les croix.

    Au final il faut juste faire une methode qui a partir d'un etat te dit si la grille est gagnante pour les croix en faisant une serie de if du type

    if (([etat] & 0x15) != 0)
    return true

    et tu passes [etat] a ta methode pour tester la victoire des croix et [etat] >> 1 pour tester la victoire des ronds.

  • # Re: Optimisation des tests pour un morpion.

    Posté par  . Évalué à 1.

    Pour éviter de parcourir le plateau de jeu dans tous les sens pour detecter les combinaisons gagnantes, tu peut stoquer (et garder a jour selon les déplacements) la somme sur chaque ligne, colonne et diagonale (soit par couleur, soit en utilisant des puissances de deux pour les couleurs pour pouvoir les extraires de la somme totale) ....

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.