Partage
  • Partager sur Facebook
  • Partager sur Twitter

zMorp - 2ème partie

Créer une IA

    30 janvier 2011 à 13:41:52

    Rhooo, j'avais pas vu ce topic...
    Je vais tenter tout de suite, j'avais vu le tuto (le titre seulement) sur le SDZ mais je savais pas que c'était un début d'IA :)
    A tout à l'heure ! ;)

    EDIT : Bon je galère :(

    Voici comment je vois la chose :

    Je lance ma fonction IAPlay(); Elle récupère les cellules vides, et pour toutes les cellules vides, lance la fonction IASimulation();
    IASimulation(), pour toutes les cellules vides restantes, lance HumanSimulation(); puis vérifie si le coup à jouer est le max.
    HumanSimulation(), pour toutes les cellules vides restantes, lance IASimulation(); puis vérifie si le coup à jouer est le min.
    Ensuite, lorsque la profondeur est nulle, j'évalue la plateau, et retourne le meilleur coup à jouer

    Ai-je compris le principe ? Parce que je me perds dans toutes ces petites fonctions d'IA :-°
    • Partager sur Facebook
    • Partager sur Twitter
      30 janvier 2011 à 19:01:09

      Oui, le principe c'est ça. :)
      Par contre, te fait pas chier avec la fonction d'évaluation, va jusqu'au bout de ton arbre et renvoie les valeurs que si tu as gagné, l'IA a gagné ou match nul. C'est plus simple. ;)
      • Partager sur Facebook
      • Partager sur Twitter
        30 janvier 2011 à 20:51:17

        C'est vraiment prise de tête votre truc >_<>_<>_<

        Voici ce que j'ai fait, je comprends pas vraiment comment tout cela fonctionne :-°
        int IAplay(int *board, int deepth){
            int *emptyBoard = malloc(sizeof(int) * deepth),
                i,
                tmp,
                tmpi,
                best = -INF_MAX;
            // Pour toutes les cellules vides
            for(i = 0; i < deepth; i++){
                getEmptyCells(board, emptyBoard);
                tmp = IASimulation(board, deepth);
                if(tmp > best){
                    best = tmp;
                    tmpi = emptyBoard[i];
                }
            }
            free(emptyBoard);
            return tmpi;
        }
        
        int IASimulation(int *board, int deepth){
            if(deepth == 0)
                return evalBoard(board);
            int i,
                tmp,
                max = -INF_MAX;
            for(i = 0; i < deepth; i++){
                if(board[i] == EMPTY){
                    board[i] = P2;
                    tmp = HumanSimulation(board, (deepth - 1));
                    if(tmp > max){
                        max = tmp;
                    }
                    board[i] = EMPTY;
                }
            }
            return max;
        }
        
        int HumanSimulation(int *board, int deepth){
            if(deepth == 0)
                return evalBoard(board);
            int i,
                tmp,
                min = INF_MAX;
            for(i = 0; i < deepth; i++){
                if(board[i] == EMPTY){
                    board[i] = P1;
                    tmp = IASimulation(board, (deepth - 1));
                    if(tmp < min){
                        min = tmp;
                    }
                    board[i] = EMPTY;
                }
            }
            return min;
        }
        
        int evalBoard(int *board){
            int i,
                pions = 0;
            Coord c;
            for(i = 0; i < CELL_X * CELL_Y; i++)
                pions++;
            for(i = 0; i < CELL_X * CELL_Y; i++){
                c.x = i % CELL_X;
                c.y = i / CELL_X;
                if(hasWin(board, c, P1))
                    return INF_MAX - pions;
                if(hasWin(board, c, P2))
                    return pions - INF_MAX;
            }
            return EMPTY;
        }
        


        J'ai fait des test avec printf et je ne rentre jamais dans la fonction evalBoard, ce qui me semble super pas logique étant donnée que je fais bien mes (deepth - 1) o_O
        Ce qui fait que tmp de la fonction IAPlay() vaut toujours 1000 ou -1000 et donc l'IA remplit la grille dans l'ordre croissant des choses... De plus, arrivé au milieu de la grille à peu près, tmpi n'est même pas réévalué donc vaut 132454534 ou 31651689 (enfin, l'ancienne valeur quoi :p ) et donc, SegFault >_<

        Un peu d'aide sur la conception, pas forcément une correction du code sera la bienvenue :D
        • Partager sur Facebook
        • Partager sur Twitter
          30 janvier 2011 à 20:58:23

          Je n'ai pas eu le temps d'y participer :( , pas grave :o , je le ferais plus-tard :) . Pendant les vacances car là, j'ai franchement pas le temps de coder :colere2: .

          HS: J'abuse, 4 smiley dans 2 phrases.
          • Partager sur Facebook
          • Partager sur Twitter
          🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles  - ♡ Copying is an act of love.
            30 janvier 2011 à 21:17:30

            Quel profondeur utilises-tu.
            Pour un morpion 3x3, si tu met une profondeur > 9, c'est un peu normal, que tu n'atteignes pas 0.

            Il faut lancer la fonction evalBoard si
            -la profondeur a atteint 0 ou
            -si la grille est remplie.
            Pour un morpion, tu peux oublier la profondeur, je pense.

            Par contre, tu dois à chaque appel tester si le coup est gagnant.
            • Partager sur Facebook
            • Partager sur Twitter
            Zeste de Savoir, le site qui en a dans le citron !
              30 janvier 2011 à 22:09:04

              Voici comment j'appel mes fonctions d'IA :

              // Récupère les coordonnées de la cellule de l'IA
              Coord getIACell(int *board, int nb){
                  // On copie le plateau
                  int _board[CELL_X * CELL_Y] = {0},
                      i;
                  Coord c;
                  copyBoard(board, _board);
                  // Maintenant, qu'on a copié notre tableau, il faut choisir le meilleur coup...
                  i = IAplay(_board, nb);
                  c.x = i % CELL_X;
                  c.y = i / CELL_X;
                  return c;
                  //return getRandomCell(board, nb);
              }
              
              currentCell = getIACell(board, turn--));
              // Turn correspond au nombre de tour qu'il reste à jouer ou au nombre de case vide...
              // Déclaration :
              int turn = CELL_X * CELL_Y;
              

              Bien entendu, turn diminue aussi lorsque le joueur joue ^^
              • Partager sur Facebook
              • Partager sur Twitter
                30 janvier 2011 à 22:34:54

                Citation : GurneyH

                tu dois à chaque appel tester si le coup est gagnant.


                A quoi te sert getEmptyCells ?
                Par contre, le but de la profondeur c'est de limiter la recherche de l'arbre, là tu vas explorer tout ton arbre quoi qu'il arrive. :)
                • Partager sur Facebook
                • Partager sur Twitter
                  30 janvier 2011 à 23:00:37

                  Citation : GurneyH

                  tu dois à chaque appel tester si le coup est gagnant.


                  A chaque appel de quoi ? IASimulation et HumanSimulation ?


                  Citation : Pouet_forever


                  A quoi te sert getEmptyCells ?
                  Par contre, le but de la profondeur c'est de limiter la recherche de l'arbre, là tu vas explorer tout ton arbre quoi qu'il arrive. :)


                  getEmptyCells me retourne la liste des cases vides, ainsi, cela m'évite de faire à chaque fois de faire tout le plateau depuis le début (même avec les cases remplies) mais j'ai du mal à l'utiliser correctement :-°
                  Je crois (je dis bien je crois) que je viens de comprendre un truc. Il ne faudrait pas mieux que je fasse :
                  int IASimulation(int *board, int deepth, int *emptyCells){
                      if(deepth == 0)
                          return evalBoard(board);
                      int i,
                          tmp,
                          max = -INF_MAX;
                      for(i = 0; i < deepth; i++){
                          board[emptyCells[i]] = P2;
                          getEmptyCells(board, emptyCells);
                          tmp = HumanSimulation(board, (deepth - 1), emptyCells);
                          if(tmp > max){
                              max = tmp;
                          }
                          board[emptyCells[i]] = EMPTY;
                      }
                      return max;
                  }
                  

                  Je vais tester, je vous dis de suite, j'éditerai ;)

                  EDIT :
                  Bon, c'est déjà un début, je peux atteindre la fin du plateau (à savoir faire match null :D )
                  Voici le code :
                  #include "include.h"
                  
                  int IAplay(int *board, int deepth){
                      int *emptyBoard = malloc(sizeof(int) * deepth),
                          i,
                          tmp,
                          tmpi,
                          best = -INF_MAX;
                      // Pour tous les coups restants
                      for(i = 0; i < deepth; i++){
                          // Initialisation du tableau des cellules vides
                          getEmptyCells(board, emptyBoard);
                          tmp = IASimulation(board, deepth, emptyBoard);
                          if(tmp > best){
                              best = tmp;
                              tmpi = emptyBoard[i];
                          }
                      }
                      free(emptyBoard);
                      return tmpi;
                  }
                  
                  int IASimulation(int *board, int deepth, int *emptyCells){
                      if(deepth == 0)
                          return evalBoard(board);
                      int i,
                          tmp,
                          max = -INF_MAX;
                      for(i = 0; i < deepth; i++){
                          // On simule le coup pour la 1ere cellule vide trouvée
                          board[emptyCells[i]] = P2;
                          // Réinitialisation du tableau de cellules vides
                          getEmptyCells(board, emptyCells);
                  
                          tmp = HumanSimulation(board, (deepth - 1), emptyCells);
                          if(tmp > max){
                              max = tmp;
                          }
                          // Et on la revide (Pour le prochain test complet)
                          board[emptyCells[i]] = EMPTY;
                      }
                      return max;
                  }
                  
                  int HumanSimulation(int *board, int deepth, int *emptyCells){
                      if(deepth == 0)
                          return evalBoard(board);
                      int i,
                          tmp,
                          min = INF_MAX;
                      for(i = 0; i < deepth; i++){
                          // On simule le coup pour la 1ere cellule vide trouvée
                          board[emptyCells[i]] = P1;
                          // Réinitialisation du tableau de cellules vides
                          getEmptyCells(board, emptyCells);
                          tmp = IASimulation(board, (deepth - 1), emptyCells);
                          if(tmp < min){
                              min = tmp;
                          }
                          // Et on la revide (Pour le prochain test complet)
                          board[emptyCells[i]] = EMPTY;
                      }
                      return min;
                  }
                  
                  int evalBoard(int *board){
                      int i,
                          pions = 0;
                      Coord c;
                      for(i = 0; i < CELL_X * CELL_Y; i++)
                          pions++;
                      for(i = 0; i < CELL_X * CELL_Y; i++){
                          c.x = i % CELL_X;
                          c.y = i / CELL_X;
                          if(hasWin(board, c, P1))
                              return INF_MAX - pions;
                          if(hasWin(board, c, P2))
                              return pions - INF_MAX;
                      }
                      return EMPTY;
                  }
                  


                  Par contre, je ne vois pas du tout où appeler evalBoard :euh:

                  EDIT 2 : Ajout de commentaire dans le code
                  • Partager sur Facebook
                  • Partager sur Twitter
                    30 janvier 2011 à 23:25:40

                    Citation : Zenko



                    A chaque appel de quoi ? IASimulation et HumanSimulation ?


                    les 2. ;)
                    • Partager sur Facebook
                    • Partager sur Twitter
                    Zeste de Savoir, le site qui en a dans le citron !
                      30 janvier 2011 à 23:25:45

                      A chaque coup que tu fais, il faut que tu testes si le pion qui a été posé est gagnant. :)
                      Si le pion est gagnant, il faut que tu retournes le maximum ou le minimum en fonction du joueur qui joue.

                      Je pense que tu te fais trop chier avec ton getEmptyCells, essaye plutôt de parcourir ta grille normalement. Ou, si tu veux vraiment utiliser cette fonction, utilise une pile (ou une liste chaînée, mais plus lourd à gérer). ;)
                      • Partager sur Facebook
                      • Partager sur Twitter
                        31 janvier 2011 à 2:01:05

                        Merci pour vos conseils et votre temps mais là, je crois qu'il y a un sérieux problème...

                        Voici le code :
                        #include "include.h"
                        
                        // On prend en considération que l'IA
                        // va toujours au bout de l'arbre
                        // Donc deepth = nombre de cases vides
                        // On verra l'amélioration ensuite
                        int IAplay(int *board, int deepth){
                            int i,
                                tmp,
                                tmpi,
                                best = -INF_MAX;
                            for(i =0; i < CELL_X * CELL_Y; i++){
                                printf("%d", board[i]);
                                    if((i  + 1) % CELL_X == 0)
                                        printf("\n");
                            }
                            for(i =0; i < CELL_X * CELL_Y; i++){
                                printf("%d : ", i);
                                if(board[i] == EMPTY){
                                    //printf("\n\nTour %d\n", i);
                                    tmp = IASimulation(board, deepth);
                                    printf("tmp = %d\n", tmp);
                                    if(tmp > best){
                                        tmp = best;
                                        tmpi = i;
                                    }
                                } else {
                                    printf("board[%d] is not empty => %d\n", i, board[i]);
                                }
                            }
                            printf("La cellule à jouer est %d\n", tmpi);
                            return tmpi;
                        }
                        
                        int IASimulation(int *board, int deepth){
                            if(deepth == 0)
                                return evalBoard(board, P2);
                            else {
                                int i = 0,
                                    tmp,
                                    winner,
                                    max = -INF_MAX;
                                for(i = 0; i < CELL_X * CELL_Y; i++){
                                    if(board[i] == EMPTY){
                                        board[i] = P2;
                                        if((winner = evalBoard(board, P2)) != EMPTY)
                                            return winner;
                                        tmp = HumanSimulation(board, (deepth - 1));
                                        if(tmp > max){
                                            max = tmp;
                                        }
                                        board[i] = EMPTY;
                                        printf("board[%d] a été réinitialisé à %d\n", i, board[i]);
                                    }
                                }
                                return max;
                            }
                        }
                        
                        int HumanSimulation(int *board, int deepth){
                            if(deepth == 0)
                                return evalBoard(board, P1);
                            else {
                                int i,
                                    tmp,
                                    winner,
                                    min = INF_MAX;
                                for(i = 0; i < CELL_X * CELL_Y; i++){
                                    if(board[i] == EMPTY){
                                        board[i] = P1;
                                        if((winner = evalBoard(board, P1)) != 0 )
                                            return winner;
                                        tmp = IASimulation(board, (deepth - 1));
                                        if(tmp < min){
                                            min = tmp;
                                        }
                                        board[i] = EMPTY;
                                        printf("board[%d] a été réinitialisé à %d\n", i, board[i]);
                                    }
                                }
                                return min;
                            }
                        }
                        
                        int evalBoard(int *board, int player){
                            int i,
                                pions = 0;
                            Coord c;
                            for(i = 0; i < CELL_X * CELL_Y; i++)
                                if(board[i] != EMPTY)
                                    pions++;
                            for(i = 0; i < CELL_X * CELL_Y; i++)
                                if(board[i] != EMPTY){
                                    c.x = i % CELL_X;
                                    c.y = i / CELL_X;
                                    if(hasWin(board, c, board[i])){
                                        printf("hasWin returns %d pour %d(%d-%d)\n", board[i] == P1 ? INF_MAX - pions : -INF_MAX + pions, i, c.x, c.y);
                                        return player == P1 ? INF_MAX - pions : pions - INF_MAX;
                                    }
                                }
                            return EMPTY;
                        }
                        

                        Et un résultat : (2 étant l'IA, 1 moi et 0 une cellule vide)

                        Citation : zMorp2


                        000
                        000
                        100

                        0 : board[8] a été réinitialisé à 0
                        board[7] a été réinitialisé à 0
                        hasWin returns -992 pour 0(0-0)
                        board[5] a été réinitialisé à 0
                        hasWin returns -992 pour 0(0-0)
                        board[4] a été réinitialisé à 0
                        hasWin returns -992 pour 2(2-0)
                        board[3] a été réinitialisé à 0
                        hasWin returns 992 pour 1(1-0)
                        board[2] a été réinitialisé à 0
                        hasWin returns 992 pour 1(1-0)
                        board[1] a été réinitialisé à 0
                        hasWin returns 992 pour 2(2-0)
                        board[0] a été réinitialisé à 0
                        hasWin returns 992 pour 2(2-0)
                        tmp = -992
                        1 : board[1] is not empty => 2
                        2 : board[2] is not empty => 1
                        3 : board[3] is not empty => 2
                        4 : board[4] is not empty => 1
                        5 : board[5] is not empty => 2
                        6 : board[6] is not empty => 1
                        7 : board[7] is not empty => 1
                        8 : board[8] is not empty => 2
                        La cellule à jouer est 0


                        201
                        000
                        100

                        0 : board[0] is not empty => 2
                        1 : hasWin returns -992 pour 1(1-0)
                        board[5] a été réinitialisé à 0
                        hasWin returns -992 pour 1(1-0)
                        board[4] a été réinitialisé à 0
                        hasWin returns 991 pour 2(2-0)
                        board[5] a été réinitialisé à 0
                        board[3] a été réinitialisé à 0
                        hasWin returns 992 pour 2(2-0)
                        board[1] a été réinitialisé à 0
                        hasWin returns 992 pour 2(2-0)
                        tmp = -992
                        2 : board[2] is not empty => 1
                        3 : board[3] is not empty => 2
                        4 : board[4] is not empty => 1
                        5 : board[5] is not empty => 1
                        6 : board[6] is not empty => 1
                        7 : board[7] is not empty => 2
                        8 : board[8] is not empty => 1
                        La cellule à jouer est 1

                        221
                        010
                        100



                        Je ne comprends pas pourquoi mon tableau board n'est pas réinitialisé correctement lorsqu'il faut passer au 2ème teste :euh:
                        EDIT : INF_MAX vaut 1000 ;)
                        • Partager sur Facebook
                        • Partager sur Twitter
                          31 janvier 2011 à 11:15:46

                          Je dirais qu'avec cette condition

                          if((winner = evalBoard(board, P1)) != 0 )
                              return winner;
                          

                          dans tes 2 fonctions, tu sors avant d'avoir "undo" le coup
                          board[i] = P1;
                          

                          • Partager sur Facebook
                          • Partager sur Twitter
                          Zeste de Savoir, le site qui en a dans le citron !
                            31 janvier 2011 à 12:14:15

                            Merci GurneyH, c'est déjà un début, mais cela ne fonctionne vraiment toujours pas...
                            Je vais tenter d'implémenter la correction de Pouet_forever et comprendre ce qui cloche car l'IA remplit la grille dans l'ordre croissant de i >_<
                            • Partager sur Facebook
                            • Partager sur Twitter
                              18 février 2011 à 19:45:52

                              Bonsoir,

                              Voici ma réponse, un petit peu longtemps après. J'étais pas mal débordé par différents projets, mais j'avais très envie de participer. Si vous pouvez commenter mon code, malgré la date, je vous en remercierai grandement!

                              game.h :
                              #ifndef GAME_H
                              #define GAME_H
                              
                              #define W 3
                              #define H 3
                              
                              void startGame(int isH[2]);
                              void playH(int turn, int grid[W][H]);
                              int playB(int turn, int grid[W][H]);
                              int IA(int player, int turn, int grid[W][H], int profondeur, int *L, int *C);
                              void printGrid(int grid[W][H]);
                              int hasWin(int grid[W][H], int turn);
                              int game(void);
                              
                              #endif
                              


                              game.c :
                              #include <stdio.h>
                              #include <stdlib.h>
                              
                              #include "game.h"
                              
                              #define IAMAX 2000
                              #define IAMIN -1000
                              #define IANUL 0
                              #define PROFMAX 10000
                              
                              void startGame(int isH[2]){
                                    do{
                                          printf("Tappe 1 pour que le joueur 1 soit humain, 0 pour un ordinateur");
                                          scanf("%d", &isH[0]);
                                    }while((unsigned)isH[0] > 1);
                                    do{
                                          printf("Tappe 1 pour que le joueur 2 soit humain, 0 pour un ordinateur");
                                          scanf("%d", &isH[1]);
                                    }while((unsigned)isH[1] > 1);
                              
                              }
                              
                              int isEmpty(int box){
                                    if(box == 0){
                                          return 1;
                                    }
                                    else{
                                          return 0;
                                    }
                              }
                              
                              void emptyCase(int *box){
                                    *box = 0;
                              }
                              
                              int isFull(int grid[W][H]){
                                    int i, j;
                              
                                    for(i = 0; i < W; i++){
                                          for(j = 0; j < H; j++){
                                                if(isEmpty(grid[i][j])){
                                                      return 0;
                                                }
                                          }
                                    }
                              
                                    return 1;
                              }
                              
                              void playH(int turn, int grid[W][H]){
                                    int i, j, ok = 0;
                              
                                    do{
                                          printf("Rentre la ligne de la case\n");
                                          scanf("%d", &i);
                                          printf("Rentre la colonne de la case\n");
                                          scanf("%d", &j);
                                          if(grid[i][j] != 0 || (unsigned)j >= H || (unsigned)i >= W){
                                                printf("Choix invalide\n");
                                          }
                                          else{
                                                ok = 1;
                                                grid[i][j] = turn + 1;
                                          }
                                    }while(!ok);
                              } 
                              
                              int playB(int turn, int grid[W][H]){
                                    int i, j;
                                    IA(turn, turn, grid, 100, &i, &j);
                              
                                    if(!isEmpty(grid[i][j])){
                                          printf("Erreur d'algo\n");
                                          return EXIT_FAILURE;
                                    }
                                    else{
                                          grid[i][j] = turn + 1;
                                    }
                                    
                              
                              
                                    return 0;
                              }
                              
                              int IA(int player, int turn, int grid[W][H], int profondeur, int *L, int *C){
                                    int i, j, iM = 0, jM = 0;
                                    int maxT, max = IAMIN;
                                    int gridT[W][H];
                                    int t1, t2; 
                              
                                    if(profondeur == 0){
                                          printf("On touche le fond\n");
                                          return IANUL;
                                    }
                              
                                    for(i = 0; i < W; i++){
                                          for(j = 0; j < H; j++){
                                                gridT[i][j] = grid[i][j];
                                          }
                                    }
                              
                                    for(i = 0; i < W; i++){
                                          for(j = 0; j < H; j++){
                                                if(isFull(gridT)){
                                                      return IANUL;
                                                }
                              
                                                if(isEmpty(gridT[i][j])){
                                                      gridT[i][j] = turn + 1;
                              
                                                      if(hasWin(gridT, player)){
                                                            return IAMAX +  profondeur - PROFMAX;
                                                      }
                              
                                                      if(hasWin(gridT, (player + 1)%2)){
                                                            return IAMIN + profondeur - PROFMAX;
                                                      }
                              
                                                      maxT = IA(player, (turn + 1)%2, gridT, profondeur -1, &t1, &t2);
                                                      emptyCase(&gridT[i][j]);
                                                      if(max < maxT){
                                                            max = maxT;
                                                            iM = i;
                                                            jM = j;
                                                      }
                                                }
                                          }
                                    }
                                    
                              
                                    *L = iM;
                                    *C = jM;
                              
                                    return max;
                              }
                              
                              void printGrid(int grid[W][H]){
                                    int i, j;
                              
                                    for(i = 0; i < W; i++){
                                          for(j = 0; j < H; j++){
                                                printf("%c|", " ox"[grid[i][j]]);
                                          }
                                          printf("\n");
                                    }
                              }
                              
                              int hasWin(int grid[W][H], int turn){
                                    int result, i, j;
                              
                                    result = 1;
                                    for(i = 0; i < W; i++){
                                          if(grid[i][i] != turn +1){
                                                result = 0;
                                          }
                                    }
                                    if(result) return 1;
                              
                                    result = 1;
                                    for(i = 0; i < H; i++){
                                          if(grid[H-1-i][i] != turn +1){
                                                result = 0;
                                          }
                                    }
                                    if(result) return 1;
                              
                                    for(i = 0; i < W; i++){
                                          result = 1;
                                          for(j = 0; j < H; j++){
                                                if(grid[i][j] != turn +1){
                                                      result = 0;
                                                }
                                          }
                                          if(result) return 1;
                                    }
                              
                                    for(i = 0; i < W; i++){
                                          result = 1;
                                          for(j = 0; j < H; j++){
                                                if(grid[j][i] != turn +1){
                                                      result = 0;
                                                }
                                          }
                                          if(result) return 1;
                                    }
                              
                                    return 0;
                              }
                              
                              int game(void){
                                    int isHuman[2], win = 0, cont = 1;
                                    int turn = 0;
                                    int grid[W][H] = {{0}};
                              
                                    startGame(isHuman);
                              
                                    while(cont){
                                          if(isHuman[turn]){
                                                playH(turn, grid);
                                          }
                                          else{
                                                if(playB(turn, grid) == EXIT_FAILURE){
                                                      return EXIT_FAILURE;
                                                }
                                          }
                              
                                          printGrid(grid);
                              
                                          if(hasWin(grid, turn)){
                                                cont = 0;
                                                win = 1;
                                          }
                                          if(isFull(grid)){
                                                cont = 0;
                                          }
                                          else{
                                                turn += 1;
                                                turn %= 2;
                                          }
                                    }
                                    if(win){
                                          printf("Victoire du jouer %d!", turn + 1);
                                    }
                                    else{
                                          printf("Match nul!");
                                    }
                              
                                    return 0;
                              }
                              


                              main.c :
                              #include <stdio.h>
                              #include <stdlib.h>
                              
                              #include "game.h"
                              
                              int main(int argc, char* argv[]){
                              
                                    game();
                                    
                                    return 0;
                              }
                              


                              J'ai essayé de séparer pas mal les fonctions. Je me sers d'assertions pour ne pas avoir à ajouter des variables en folie. Le programme n'est pas "secure", si il faudrait que je vide le buffer pour ça. Mais j'ai un peu la flemme, ce n'était pas mon but dans l'exercice.

                              Voici une trace d'exécution :
                              Tappe 1 pour que le joueur 1 soit humain, 0 pour un ordinateur0
                              Tappe 1 pour que le joueur 2 soit humain, 0 pour un ordinateur0
                              o| | |
                               | | |
                               | | |
                              o|x| |
                               | | |
                               | | |
                              o|x|o|
                               | | |
                               | | |
                              o|x|o|
                              x| | |
                               | | |
                              o|x|o|
                              x| |o|
                               | | |
                              o|x|o|
                              x| |o|
                               | |x|
                              o|x|o|
                              x|o|o|
                               | |x|
                              o|x|o|
                              x|o|o|
                              x| |x|
                              o|x|o|
                              x|o|o|
                              x|o|x|
                              Match nul!


                              Merci!

                              Joueur 1156
                              • Partager sur Facebook
                              • Partager sur Twitter
                                18 février 2011 à 21:57:41

                                Déjà, merci de ta participation. :)
                                Sans rentrer dans ton code, ya quelque chose qui ne va pas. Si tu joues une case dans le coin, la case à jouer juste après sera la case du milieu. :)
                                Tu as inversé les lignes et les colonnes dans ton programme (rien de bien méchant).
                                Dans ta fonction startGame tu pourrais utiliser une boucle.
                                Tu utilises souvent turn + 1, mais tu ne fais pas toujours de modulo, c'est voulu ? tu ne risques pas d'avoir une valeur que tu ne veux pas ?
                                Comme tu n'utilises pas ta profondeur, tu peux enlever ces lignes là :

                                if(profondeur == 0){
                                            printf("On touche le fond\n");
                                            return IANUL;
                                      }
                                

                                Pourquoi faire une copie de ton tableau ? Tu peux simplement travailler sur le même tableau. :)
                                Tu t'es trompé sur les valeurs que tu renvoies :

                                if(hasWin(gridT, player)){
                                                              return IAMAX +  profondeur - PROFMAX;
                                                        }
                                
                                                        if(hasWin(gridT, (player + 1)%2)){
                                                              return IAMIN + profondeur - PROFMAX;
                                                        }
                                

                                Tu renvoies les valeurs inverses de celles que tu devrais renvoyer (PROFMAX >> IAMAX > IAMIN).
                                Pour le premier cas, tu devrais renvoyer IAMAX-profondeur et dans le deuxième cas IAMIN+profondeur.

                                Je me suis pas trop attardé à commenter ton code, j'ai surtout regardé l'IA. :)
                                Je trouve ton code simple et propre, j'aime bien. :)

                                Encore une fois, merci de ta participation !
                                Bon courage. Je pense que pour faire fonctionner ton algo tu n'as que quelques modifications (mineures) à faire. ;)
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  19 février 2011 à 2:39:51

                                  Citation : Pouet_forever

                                  Déjà, merci de ta participation. :)


                                  Mais c'est un plaisir!

                                  Citation : Pouet_forever


                                  Tu utilises souvent turn + 1, mais tu ne fais pas toujours de modulo, c'est voulu ? tu ne risques pas d'avoir une valeur que tu ne veux pas ?



                                  En fait, turn vaut soit 0, soit 1. Joueur 1 vaut 1, Joueur 2 vaut 2, vide vaut 0. Ainsi, turn + 1 indique le numéro (et donc la valeur dans la grille) du joueur. Donc +1%2 pour changer de tour, comme dans l'AI (j'en reparle plus tard), et +1 pour indiquer le joueur.

                                  Citation : Pouet_forever


                                  Comme tu n'utilises pas ta profondeur, tu peux enlever ces lignes là :

                                  if(profondeur == 0){
                                              printf("On touche le fond\n");
                                              return IANUL;
                                        }
                                  


                                  Pourquoi faire une copie de ton tableau ? Tu peux simplement travailler sur le même tableau. :)



                                  Pour la profondeur, je vais sûrement l'utiliser plus tard. Donc autant la laisser. Le "on touche le fond", c'est surtout de la vérification d'algo. Le tableau est une erreur de code. Je m'en suis rendu compte tôt, mais j'avais envie d'un algo fonctionnel, donc j'ai eu la flemme de modifier tout de suite.

                                  Citation : Pouet_forever


                                  Tu t'es trompé sur les valeurs que tu renvoies :

                                  if(hasWin(gridT, player)){
                                                                return IAMAX +  profondeur - PROFMAX;
                                                          }
                                  
                                                          if(hasWin(gridT, (player + 1)%2)){
                                                                return IAMIN + profondeur - PROFMAX;
                                                          }
                                  


                                  Tu renvoies les valeurs inverses de celles que tu devrais renvoyer (PROFMAX >> IAMAX > IAMIN).
                                  Pour le premier cas, tu devrais renvoyer IAMAX-profondeur et dans le deuxième cas IAMIN+profondeur.



                                  En fait non, je ne me suis pas trompé.
                                  int IA(int player, int turn, int grid[W][H], int profondeur, int *L, int *C){
                                  

                                  Comme on le voit, il y a deux valeur : player et turn. Player permet de voir pour qui est l'algorithme. Ainsi, quand player+1 %2 indique l'autre joueur. C'est pour marquer l'alternance des coups dans la récursivité, en sachant à qui profite les coups. Player n'est jamais modifié, comme tu peux le voir à la ligne 119.
                                  Après, j'ai quelques valeurs à modifier, pour obtenir un code plus fonctionnel au niveau du poids des coups. En fait, j'ai bien compris le système de poids (comment initialiser max, comment le modifier etc...) que récemment, du coup c'est encore du domaine de l'innovation ^^".

                                  Citation : Pouet_forever


                                  Je me suis pas trop attardé à commenter ton code, j'ai surtout regardé l'IA. :)
                                  Je trouve ton code simple et propre, j'aime bien. :)

                                  Encore une fois, merci de ta participation !
                                  Bon courage. Je pense que pour faire fonctionner ton algo tu n'as que quelques modifications (mineures) à faire. ;)



                                  Et encore une fois de rien! C'est très agréable. Et merci pour les compliments, ça me touche beaucoup.

                                  Une fois un algo stable, c'est parti pour la SDL =)
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    19 février 2011 à 11:41:28

                                    Ton histoire de 'turn' est un peu ambigu, tu pourrais faire une fonction histoire de bien montrer pourquoi tu fais ça. :)
                                    J'ai vu que player n'était pas modifié, mais je maintiens que les valeurs que tu renvoies sont fausses. De plus, tu as oublié une partie de l'algo en fait, ton algo doit être un min/max et tu ne fais que le max : if(max < maxT)
                                    C'est bien d'avoir fait la console avant, au moins tu ne te focalises pas sur l'affichage mais sur l'aglo. :)
                                    Bon courage !
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      19 février 2011 à 14:09:39

                                      Hmm, ok je cède!

                                      J'ai un changé complètement pour l'IA, histoire d'avoir un truc plus clair. Pour vérifier mes assertions entre turn et player, j'ai fait trois fonctions :
                                      turn vaut soit 0, soit 1
                                      player vaut soit 1, soit 2
                                      changeTurn(turn -> turn), getPlayer(turn -> player), getOtherPlayer(player -> player).
                                      Ces fonctions vérifient que les arguments sont bien des player ou des turns.

                                      Ça permet d'enlever un peu de "magie" du code.

                                      Sinon, j'ai fait une fonction IAmax, qui appelle une autre fonction IAmin, sur le concept du minmax. Très différente de l'ancienne, plus claire, plus intuitive.

                                      J'utilise aussi un "doubleBreak", qui me permet de sortir d'une double boucle. De même, j'ai rajouté une struct coordonnées pour simplifier le code.

                                      Il faut choisir la difficulté (entre 1 et l'infini : 0 fait planter). Je compte rajouter des unions histoire de permettre de faire des bots de différentes puissances. Mais pas tout de suite, là j'ai piscine :p

                                      Voici le nouveau code :

                                      game.c :

                                      #include <stdio.h>
                                      #include <stdlib.h>
                                      
                                      #include "game.h"
                                      
                                      #define IAMAX 100
                                      #define IAMIN -100
                                      #define IANUL 0
                                      #define INF 1000000
                                      
                                      #define DIFF 2
                                      
                                      void startGame(int isH[2]){
                                            do{
                                                  printf("Tappe 1 pour que le joueur 1 soit humain, 0 pour un ordinateur");
                                                  scanf("%d", &isH[0]);
                                            }while((unsigned)isH[0] > 1);
                                            do{
                                                  printf("Tappe 1 pour que le joueur 2 soit humain, 0 pour un ordinateur");
                                                  scanf("%d", &isH[1]);
                                            }while((unsigned)isH[1] > 1);
                                      
                                      }
                                      
                                      int isEmpty(int box){
                                            if(box == 0){
                                                  return 1;
                                            }
                                            else{
                                                  return 0;
                                            }
                                      }
                                      
                                      void emptyCase(int *box){
                                            *box = 0;
                                      }
                                      
                                      int getOtherPlayer(int player){
                                            if(player <1 || player > 2){
                                                  printf("Bad use of getOtherPlayer : player = %d\n", player);
                                                  return EXIT_FAILURE;
                                            }
                                            else{
                                                  return player  % 2 + 1;
                                            }
                                      }
                                      
                                      int getPlayer(int turn){
                                            if((unsigned) turn > 1){
                                                  printf("Bad use of getPlayer : turn = %d\n", turn);
                                                  return EXIT_FAILURE;
                                            }
                                            else{
                                                  return turn + 1;
                                            }
                                      }
                                      
                                      int changeTurn(int turn){
                                            return (turn + 1) %2;
                                      }
                                      
                                      int isFull(int grid[W][H]){
                                            int i, j;
                                      
                                            for(i = 0; i < W; i++){
                                                  for(j = 0; j < H; j++){
                                                        if(isEmpty(grid[i][j])){
                                                              return 0;
                                                        }
                                                  }
                                            }
                                      
                                            return 1;
                                      }
                                      
                                      void playH(int player, int grid[W][H]){
                                            int i, j, ok = 0;
                                      
                                            do{
                                                  printf("Rentre la ligne de la case\n");
                                                  scanf("%d", &i);
                                                  printf("Rentre la colonne de la ligne\n");
                                                  scanf("%d", &j);
                                                  if(!((unsigned) i < H && (unsigned) j < W && isEmpty(grid[i][j]))){
                                                        int c;
                                                        while((c = getchar()) != '\n' && c != EOF);
                                                        
                                                        printf("Choix invalide\n");
                                                  }
                                                  else{
                                                        ok = 1;
                                                        grid[i][j] = player;
                                                  }
                                            }while(!ok);
                                      } 
                                      
                                      int playB(int turn, int grid[W][H], int diff){
                                            coord ij;
                                      
                                            IAmax(turn, grid, diff, &ij);
                                      
                                            if(!isEmpty(grid[ij.x][ij.y])){
                                                  printf("Erreur d'algo\n");
                                                  return EXIT_FAILURE;
                                            }
                                            else{
                                                  grid[ij.x][ij.y] = getPlayer(turn);
                                            }
                                      
                                            return 0;
                                      }
                                      
                                      void chooseDiff(int *diff){
                                            printf("Choose difficulty (1..Inf)");
                                            scanf("%d", diff);
                                      }
                                      
                                      int IAmax(int turn, int grid[W][H], int deepth, coord *c){
                                            int max = -INF, maxT;
                                            int doubleBreak = 0;
                                            coord ij, t;
                                      
                                            if(deepth == 0){
                                                  return IANUL;
                                            }
                                      
                                            if(isFull(grid)){
                                                  return IANUL;
                                            }
                                      
                                            for(ij.x = 0; ij.x < W; ij.x++){
                                                  for(ij.y = 0; ij.y < H; ij.y++){
                                                        if(isEmpty(grid[ij.x][ij.y])){
                                                              grid[ij.x][ij.y] = getPlayer(turn);
                                                              
                                                              if(isFull(grid)){
                                                                    max = IANUL;
                                                                    doubleBreak = 1;
                                                              }
                                      
                                                              if(hasWin(grid, getPlayer(turn))){
                                                                    max =  IAMAX + deepth;
                                                                    doubleBreak = 1;
                                                              }
                                                              else{
                                                                    maxT = IAmin(changeTurn(turn), grid, deepth - 1, &t);
                                                                    if(maxT > max){
                                                                          c->x = ij.x;
                                                                          c->y = ij.y;
                                                                          max = maxT;
                                                                    }
                                                              }
                                                              emptyCase(&grid[ij.x][ij.y]);
                                                        }
                                                        if(doubleBreak){
                                                              c->x = ij.x;
                                                              c->y = ij.y;
                                                              break;
                                                        }
                                                  }
                                                  if(doubleBreak) break;
                                            }
                                            
                                            return max;
                                      }
                                      
                                      int IAmin(int turn, int grid[W][H], int deepth, coord *c){
                                            int min = INF, minT;
                                            int doubleBreak = 0;
                                            coord ij, t;
                                      
                                            if(deepth == 0){
                                                  return IANUL;
                                            }
                                      
                                            if(isFull(grid)){
                                                  return IANUL;
                                            }
                                      
                                            for(ij.x = 0; ij.x < W; ij.x++){
                                                  for(ij.y = 0; ij.y < H; ij.y++){
                                                        if(isEmpty(grid[ij.x][ij.y])){
                                                              grid[ij.x][ij.y] = getPlayer(turn);
                                                              
                                                              if(isFull(grid)){
                                                                    min = IANUL;
                                                                    doubleBreak = 1;
                                                              }
                                      
                                                              if(hasWin(grid, getPlayer(turn))){
                                                                    min =IAMIN - deepth;
                                                                    doubleBreak = 1;
                                                              }
                                                              else{
                                                                    minT = IAmax(changeTurn(turn), grid, deepth - 1, &t);
                                                                    if(minT < min){
                                                                          c->x = ij.x;
                                                                          c->y = ij.y;
                                                                          min = minT;
                                                                    }
                                                              }
                                                              
                                                              emptyCase(&grid[ij.x][ij.y]);
                                                        }
                                                        if(doubleBreak){
                                                              c->x = ij.x;
                                                              c->y = ij.y;
                                                              break;
                                                        }
                                                  }
                                                  if(doubleBreak) break;
                                            }
                                      
                                            return min;
                                      }
                                      
                                      void printGrid(int grid[W][H]){
                                            int i, j;
                                      
                                            for(i = 0; i < W; i++){
                                                  for(j = 0; j < H; j++){
                                                        printf("%c|", " ox"[grid[i][j]]);
                                                  }
                                                  printf("\n");
                                            }
                                      }
                                      
                                      int hasWin(int grid[W][H], int player){
                                            int result, i, j;
                                      
                                            result = 1;
                                            for(i = 0; i < W; i++){
                                                  if(grid[i][i] != player){
                                                        result = 0;
                                                  }
                                            }
                                            if(result) return 1;
                                      
                                            result = 1;
                                            for(i = 0; i < H; i++){
                                                  if(grid[H-1-i][i] != player){
                                                        result = 0;
                                                  }
                                            }
                                            if(result) return 1;
                                      
                                            for(i = 0; i < W; i++){
                                                  result = 1;
                                                  for(j = 0; j < H; j++){
                                                        if(grid[i][j] != player){
                                                              result = 0;
                                                        }
                                                  }
                                                  if(result) return 1;
                                            }
                                      
                                            for(i = 0; i < W; i++){
                                                  result = 1;
                                                  for(j = 0; j < H; j++){
                                                        if(grid[j][i] != player){
                                                              result = 0;
                                                        }
                                                  }
                                                  if(result) return 1;
                                            }
                                      
                                            return 0;
                                      }
                                      
                                      int game(void){
                                            int isHuman[2], win = 0, cont = 1;
                                            int turn = 0, diff;
                                            int grid[W][H] = {{0}};
                                      
                                            startGame(isHuman);
                                      
                                            chooseDiff(&diff);
                                      
                                            while(cont){
                                                  printf("Au tour du joueur %d!\n", getPlayer(turn));
                                                  if(isHuman[turn]){
                                                        playH(getPlayer(turn), grid);
                                                  }
                                                  else{
                                                        if(playB(turn, grid, diff) == EXIT_FAILURE){
                                                              return EXIT_FAILURE;
                                                        }
                                                  }
                                      
                                                  printGrid(grid);
                                      
                                                  if(hasWin(grid, getPlayer(turn))){
                                                        cont = 0;
                                                        win = 1;
                                                  }
                                                  if(isFull(grid)){
                                                        cont = 0;
                                                  }
                                                  else{
                                                        turn = changeTurn(turn);
                                                  }
                                            }
                                            if(win){
                                                  printf("Victoire du joueur %d!", getPlayer(turn));
                                            }
                                            else{
                                                  printf("Match nul!");
                                            }
                                      
                                            return 0;
                                      }
                                      


                                      game.h :

                                      #ifndef GAME_H
                                      #define GAME_H
                                      
                                      #define W 3
                                      #define H 3
                                      
                                      typedef struct coord{
                                            int x;
                                            int y;
                                      }coord;
                                      
                                      void startGame(int isH[2]);
                                      int isEmpty(int box);
                                      void emptyCase(int *box);
                                      int getOtherPlayer(int player);
                                      int getPlayer(int turn);
                                      int changeTurn(int turn);
                                      int isFull(int grid[W][H]);
                                      void playH(int player, int grid[W][H]);
                                      int playB(int turn, int grid[W][H], int diff);
                                      void chooseDiff(int *diff);
                                      int IAmax(int turn, int grid[W][H], int deepth, coord *c);
                                      int IAmin(int turn, int grid[W][H], int deepth, coord *c);
                                      void printGrid(int grid[W][H]);
                                      int hasWin(int grid[W][H], int player);
                                      int game(void);
                                      
                                      #endif
                                      


                                      J'ai fait quelques tests. En dessous de 3, l'IA est nulle. La 6 semble imbattable. Pourquoi pas une IA avec gestion du stress : pouvant rater des coups ^^".

                                      Merci beaucoup d'animer cette section avec des exercices comme ça, c'est vraiment fun.

                                      Joueur 1156
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        19 février 2011 à 15:03:57

                                        A première vue ça a l'air correct (je n'ai pas compilé le code). :)
                                        Mais tu n'étais pas obligé de faire 2 fonctions, tu pouvais rester sur 1 seule fonction mais gérer les 2 cas dans cette même fonction. :)
                                        Par contre, ta gestion de la profondeur n'est pas correcte, il faut que, dès que tu atteins profondeur==0, renvoyer une évaluation de ta grille, là tu gères ce cas comme un match nul. ^^
                                        Si tu veux, tu peux améliorer ton IA avec le négamax et l'alpha/beta, et pourquoi pas si tu veux, d'autres techniques que je n'ai pas présentées ici pour gérer une grille de taille supérieure à 3x3 et une IA pas trop longue. :)

                                        Merci de ta participation !
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          19 février 2011 à 16:01:55

                                          J'y jetterai un coup d'oeil!
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            21 février 2011 à 10:45:23

                                            Voici mon algo du negaMax :

                                            int negaMax(int player, int turn, int grid[W][H], int deepth, coord *c){
                                                  int max = -INF, maxT;
                                                  int doubleBreak = 0;
                                                  coord ij, t;
                                                  int coefTurn;
                                            
                                                  
                                            
                                                  if(player != getPlayer(turn)){
                                                        coefTurn = -1;
                                                  }
                                                  else{
                                                        coefTurn = 1;
                                                  }
                                            
                                                  max *= coefTurn;
                                            
                                                  if(deepth == 0){
                                                        if(hasWin(grid, getOtherPlayer(getPlayer(turn)))){
                                                              return -1 * coefTurn* IAMIN;
                                                        }            
                                                        else return -1 * coefTurn* IANUL;
                                                  }
                                            
                                                  if(isFull(grid)){
                                                        if(hasWin(grid, getOtherPlayer(getPlayer(turn)))){
                                                              return  -1 * coefTurn * IAMIN;
                                                        }
                                                        else{
                                                              return  -1 * coefTurn * IANUL;
                                                        }
                                                  }
                                            
                                                  for(ij.x = 0; ij.x < W; ij.x++){
                                                        for(ij.y = 0; ij.y < H; ij.y++){
                                                              if(isEmpty(grid[ij.x][ij.y])){
                                                                    grid[ij.x][ij.y] = getPlayer(turn);
                                                                    
                                                                    if(hasWin(grid, getPlayer(turn))){
                                                                          max = coefTurn* (IAMAX + deepth);
                                                                          doubleBreak = 1;
                                                                    }
                                                                    
                                                                    else{
                                                                          maxT = negaMax(player, changeTurn(turn), grid, deepth - 1, &t);
                                                                          if(player == getPlayer(turn)){
                                                                                      if(maxT > max){
                                                                                            c->x = ij.x;
                                                                                            c->y = ij.y;
                                                                                            max = maxT;
                                                                                      }
                                                                                }
                                                                          else{
                                                                                if(maxT < max){
                                                                                      c->x = ij.x;
                                                                                      c->y = ij.y;
                                                                                      max = maxT;
                                                                                }
                                                                          }
                                                                    }
                                                                    
                                                                    emptyCase(&grid[ij.x][ij.y]);
                                                              }      
                                                              if(doubleBreak){
                                                                    c->x = ij.x;
                                                                    c->y = ij.y;
                                                                    break;
                                                              }
                                                        }
                                                        if(doubleBreak) break;
                                                  }
                                                  
                                                  return  max;
                                            }
                                            


                                            En gros, la différence avec l'algo IAmax et IAmin, est que je calcule le coefficient "coefTurn" au dessus, qui indique si le joueur à qui est le tour est le joueur qui veut faire le maximum de points (si on se retrouve dans un noeud max ou noeud min).
                                            Ensuite, j'applique ce coef à tous les return, sauf le dernier.

                                            Et voilà!

                                            Je vais regarder l'alphabeta maintenant =)
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              21 février 2011 à 12:05:18

                                              Le but du negamax est justement de supprimer ce coefficient. :)
                                              Ce que tu as fait n'est pas un negamax. ^^
                                              Il faut que tes résultats soient symétriques par rapport à 0 (ce qui est le cas chez toi) et il faut que tu récupères l'inverse de ce que tu récupères (pas très clair là...). Ta fonction doit faire beaucoup moins de lignes. :)
                                              • Partager sur Facebook
                                              • Partager sur Twitter

                                              zMorp - 2ème partie

                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                              × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                              • Editeur
                                              • Markdown