Rapport sur Minimax Simple example

Table of Contents

  • Présentation du problème
  • Métode de résolution
  • Doxygene
  • Bilan de ce travail

    • Lien vers ma page web ISIMA

    scrable.jpg

    Présentation du problème

    Minimax simple example est un problème du site Codingame. Le but de ce problème est de mettre en application l’algorithme Minimax dans un cas concret. Ici, on considérera un jeu où le but est de former des mots avec une liste de lettre. En effet, on considére une pile de lettre, où les joueurs vont chacun leurs tour prendre soit la première, soit la deuxième lettre de la pile, puis essayerons de former des mots parmi une liste fourni. Chaque mot rapporte un certain nombre de points. Le but sera donc de trouver le meilleur choix de lettre afin que l’écart de score entre le premier et le second joueur soit maximal. Pour cela, le site nous fourni un certain nombre d’entrée.

    • N: le nombre de lettre disponibles
    • Q: le nombre de mot contenu dans la liste
    • Q lignes où sur chacune d’entre elles est inscrit un mot et un score

    Le retour attendu de notre programme, c’est l’affichage du meilleur premier choix, puis du score des deux joueurs, séparé par un tiret.

    A noter: un joueur peut réutiliser autant de fois qu’il le souhaite les lettres qu’il a choisi. Il y a au maximum 26 lettres dans la pile.

    Métode de résolution

    Description de la stratégie

    Afin de résoudre ce problème, j’ai pu diviser mon code en plusieurs parties que voici ci dessous.

    Partie 1: Définition des structures

    typedef struct st_word {

  char word[11];
  int score;

} st_word;

typedef struct st_player { // Joueur et ses lettres

  int score;
  char letter[60];

} st_player;

typedef struct st_feuille {

  int difference;
  int score[2];
  char firstpick;

} st_feuille;

    Dans cette partie on défini des structures afin de concentrer l’information. Une structure pour les feuilles de l’arbre contenant les informations que l’on attend en sortie. Une structure pour représenter chaque joueur, avec son score et ses lettres. Enfin, une structure contenant chaque mot que l’on peut former, et son nombre de points correspondant.

    Partie 2: Fonction best

    void best(st_word point[]) { // Met les mots qui valent le plus de points au
                             // début de la liste

  int check = 0;
  st_word save;

  while (check == 0) {
    int exchange = 0;
    for (int i = 1; i < n; i++) {
      if (point[i - 1].score < point[i].score) {
        exchange = 1;
        save = point[i - 1];
        point[i - 1] = point[i];
        point[i] = save;
      }
    }
    if (exchange == 0) {
      check = 1;
    }
  }
}

    Cette fonction permet de ranger par ordre décroissant les différents mots disponible, en fonction de leur valeur.

    Partie 3: Fonction calcul_score

    int calcul_score(st_player player) {

  int i = 0;
  int j = 0;
  int stop = 0;
  int nb_lettre = nb_lettre_tot / 2;
  int s = 0;
  int verif;
  int k;

  while ((i < q) && (nb_lettre > 0)) { // Pour chaque mot
    j = 0;
    stop = 0;

    while ((point[i].word[j] != '\0') &&
           (stop == 0)) { // Si on peut former le mot avec les lettres du joueur
      verif = 0;
      k = 0;

      while ((player.letter[k] != '\0') &&
             (verif == 0)) { // On parcour toutes les lettres de ce joueur
        if (player.letter[k] == point[i].word[j]) { // Si on trouve la lettre
          verif = 1;
        }
        k++;
      }

      if (verif == 0) {
        stop = 1;
      }
      j++;
    }

    if (stop == 0) {
      s += point[i].score; // On ajoute au score du joueur
    }
    i++;
  }

  return s;
}

    Cette fonction permet de calculer le score d’un joueur en fonction des lettres qu’il possède. On part du principe qu’un joueur utilisera au mieux ses lettres, et que donc il verra toutes les combinaisons qu’il pourra réaliser.

    Partie 4: Fonction creer_arbre

    void creer_arbre(char choice1, char choice2, int player, int indicelettre,
                int countletters, int lettre_donnee, st_player player1,
                st_player player2, int pick1) {

  if (lettre_donnee >= n) {
    int savefirst = player1.letter[0];
    printf("lettre joueur 1: %s | lettre joueur 2: %s\nscore: %d-%d\n\n",player1.letter,player2.letter,calcul_score(player1),calcul_score(player2));

    int v1 = calcul_score(player1);
    int v2 = calcul_score(player2);

    feuille[indicefeuille].difference = v1 - v2;
    feuille[indicefeuille].firstpick = savefirst;
    feuille[indicefeuille].score[0] = v1;
    feuille[indicefeuille].score[1] = v2;

    indicefeuille++;

    return;
  }

  if (player == 1) { // Si c'est au joueur 1
    if (pick1 == 0) {
      if (lettre_donnee != n - 1) {
        creer_arbre(choice1, choice2, 1, indicelettre, countletters,
                    lettre_donnee, player1, player2, 1); // Test choix 2eme nb
      }
      player1.letter[indicelettre] = choice1;
      creer_arbre(choice2, letters[countletters], 2, indicelettre + 1,
                  countletters + 1, lettre_donnee + 1, player1, player2, 0);
    } else {
      player1.letter[indicelettre] = choice2;
      creer_arbre(choice1, letters[countletters], 2, indicelettre + 1,
                  countletters + 1, lettre_donnee + 1, player1, player2, 0);
    }
  }

  else if (player == 2) { // Si c'est au joueur 2
    if (pick1 == 0) {
      if (lettre_donnee != n - 1) {
        creer_arbre(choice1, choice2, 2, indicelettre, countletters,
                    lettre_donnee, player1, player2, 1); // Test choix 2eme nb
      }
      player2.letter[indicelettre - 1] = choice1;
      creer_arbre(choice2, letters[countletters], 1, indicelettre,
                  countletters + 1, lettre_donnee + 1, player1, player2, 0);
    } else {
      player2.letter[indicelettre - 1] = choice2;
      creer_arbre(choice1, letters[countletters], 1, indicelettre,
                  countletters + 1, lettre_donnee + 1, player1, player2, 0);
    }
  }

  return;
}

    Cette fonction récursive permet de construire l’arbre des possibilitées de score. Elle va stocker tout les scores possibles dans un tableau de structure feuille, ce qui va permettre d’appliquer l’algorithme minimax par la suite, comme on a pu le faire lors du puzzle minimax exercice.

    Partie 5: Fonction minimax

    int minimum(int a, int b) // Permet de trouver le minimum
{
  if (a <= b) {
    return (a);
  }

  return (b);
}

int maximum(int a, int b) // Permet de trouver le maximum
{
  if (a >= b) {
    return (a);
  }

  return (b);
}

int ft_power(int a, int b) // Fonction puissance
{
  if (b < 0)
    return (0);
  if (b == 0)
    return (1);
  return (a * ft_power(a, b - 1));
}

int minimax(st_feuille feuille[], int branchf, int depht, int a, int b,
            int joueur) {
  int i;
  int value;

  i = 0;
  if (depht == 0) { // Si on est au niveau des racine de l'arbre

    return (feuille->score[1]);
  }

  if (joueur == 1) {      // Si c'est au joueur 1 de jouer
    value = -999;         // On assigne la pire valeur possible
    while (i < branchf) { // On test chaque possibilité de jeu

      value = maximum(
          value,
          minimax(&feuille[i * ft_power(branchf, depht - 1)], branchf,
                  depht - 1, a, b, 0)
              .score[0]); // La valeur correspond au maximum entre la valeur
                          // actuelle et la valeur meilleure valeur disponible
                          // dans les branches précedentes

      if (value >= b) {
        break;
      }

      a = maximum(value, a); // Maximum entre
      i++;
    }
  }

  if (joueur == 0) { // Si c'est au joueur 0 de jouer

    value = 999;
    while (i < branchf) {

      value = minimum(value, minimax(&feuille[i * ft_power(branchf, depht - 1)],
                                     branchf, depht - 1, a, b, 1)
                                 .score[1]); // Appel de la fonction

      if (value <= a) {
        break;
      }

      b = minimum(value, b);
      i++;
    }
  }

  return (value);
}

    Je n’arrive malheureusement pas à faire fonctionner cette partie. Elle est sencé appliquer l’algorithme minimax au tableau de feuille créé précedement. Le fait qu’il y ai la différence, et le score de chaque joueur à gérer, malgré la création de st_feuille sencé simplifier les opérations me bloque. Cette partie reprend le fonctionnement du précedent codingame.

    Partie 6: Programme principal

    int main() {

  st_player player1;
  st_player player2;

  scanf("%d%d", &n, &q);

  for (int i = 0; i < n; i++) {
    char letter[2];
    scanf("%s", letter);
    letters[i] = letter[0];
  }
  fprintf(stderr, "%s\n", letters);

  nb_lettre_tot = strlen(letters);

  for (int i = 0; i < q; i++) {
    char word[11];
    int score;
    int j = 0;
    scanf("%s%d", word, &score);
    while (word[j] != '\0') {
      point[i].word[j] = word[j];
      j++;
    }
    point[i].score = score;
  }

  best(point);

  for (int i = 0; i < q; i++) {
    fprintf(stderr, "%s  %d\n", point[i].word, point[i].score);
  }

  char choice1 = letters[0];
  char choice2 = letters[1];

  creer_arbre(choice1, choice2, 1, 0, 2, 0, player1, player2, 0);

  return 0;
}

    Cette partie correspond au programme principal. On y récupère les entrées, puis on appelle la fonction qui permet de trier les mots donnés dans l’ordre décroissant. Enfin, on appelle la fonction creer_arbre, qui va tester toutes les possibilitées de score.

    Détail algorithmique de la méthode

    Dans le graph ci dessous, on retrouve le principe de fonctionnement général du programme que j’ai voulu créer. La partie utilisant minimax est donc incluse.

    scrableschema2.png

    Cliquez ici pour agrandir.

    La flèche rouge correspond à la réponse non, la flèche verte à la réponse oui.

    J’ai ainsi pu coder le programme de ce schéma jusqu’à l’étape de création de l’arbre. Malheuresement mon algorithme minimax ne fonctionnant pas, je n’ai pas pu arriver jusqu’à la fin de mon code.

    Fonction creer_arbre

    On retrouve ci-dessous un arbre correspondant à ce que cette fonction crée pour le test 1.

    scrableschema1.png

    Cliquez ici pour agrandir

    Les cercles rouges signifit que le joueur 1 choisi, les cercles bleus indiquent que c’est le joueur 2 qui choisi sa lettre.

    On remarque donc dans cet arbre les différentes possibilitées de combinaison pour chaque joueur, ainsi que le score qui en résulte. Ainsi, on observe facilement que le meilleur premier choix pour que le joueur 1 gagne est la lettre S.

    Remarque: Pour plus de détail sur le fonctionnement de l’algorithme minimax et de l’élagage alpha beta, le détail algorithmique du probleme minimax exercice que l’on peut trouver sur ma page personnelle ISIMA l’explique de façon détaillée.

    Code commenté ayant résolu le problème

    Voici ci dessous le code complet m’ayant permis de résoudre le problème. 

    #include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct st_word {

  char word[11];
  int score;

} st_word;

typedef struct st_player { // Joueur et ses lettres

  int score;
  char letter[60];

} st_player;

typedef struct st_feuille {

  int difference;
  int score[2];
  char firstpick;

} st_feuille;

st_word point[110];
int n;
int q;
char letters[110];
int nb_lettre_tot;

void best(st_word point[]) { // Met les mots qui valent le plus de points au
                             // début de la liste

  int check = 0;
  st_word save;

  while (check == 0) {
    int exchange = 0;
    for (int i = 1; i < n; i++) {
      if (point[i - 1].score < point[i].score) {
        exchange = 1;
        save = point[i - 1];
        point[i - 1] = point[i];
        point[i] = save;
      }
    }
    if (exchange == 0) {
      check = 1;
    }
  }
}

int calcul_score(st_player player) {

  int i = 0;
  int j = 0;
  int stop = 0;
  int nb_lettre = nb_lettre_tot / 2;
  int s = 0;
  int verif;
  int k;

  while ((i < q) && (nb_lettre > 0)) { // Pour chaque mot
    j = 0;
    stop = 0;

    while ((point[i].word[j] != '\0') &&
           (stop == 0)) { // Si on peut former le mot avec les lettres du joueur
      verif = 0;
      k = 0;

      while ((player.letter[k] != '\0') &&
             (verif == 0)) { // On parcour toutes les lettres de ce joueur
        if (player.letter[k] == point[i].word[j]) { // Si on trouve la lettre
          verif = 1;
        }
        k++;
      }

      if (verif == 0) {
        stop = 1;
      }
      j++;
    }

    if (stop == 0) {
      s += point[i].score; // On ajoute au score du joueur
    }
    i++;
  }

  return s;
}

int value = -1000;
int score[3];
st_feuille feuille[1000];
int indicefeuille = 0;

void creer_arbre(char choice1, char choice2, int player, int indicelettre,
                int countletters, int lettre_donnee, st_player player1,
                st_player player2, int pick1) {

  if (lettre_donnee >= n) {
    int savefirst = player1.letter[0];
    printf("lettre joueur 1: %s | lettre joueur 2: %s\nscore: %d-%d\n\n",player1.letter,player2.letter,calcul_score(player1),calcul_score(player2));

    int v1 = calcul_score(player1);
    int v2 = calcul_score(player2);

    feuille[indicefeuille].difference = v1 - v2;
    feuille[indicefeuille].firstpick = savefirst;
    feuille[indicefeuille].score[0] = v1;
    feuille[indicefeuille].score[1] = v2;

    indicefeuille++;

    return;
  }

  if (player == 1) { // Si c'est au joueur 1
    if (pick1 == 0) {
      if (lettre_donnee != n - 1) {
        creer_arbre(choice1, choice2, 1, indicelettre, countletters,
                    lettre_donnee, player1, player2, 1); // Test choix 2eme nb
      }
      player1.letter[indicelettre] = choice1;
      creer_arbre(choice2, letters[countletters], 2, indicelettre + 1,
                  countletters + 1, lettre_donnee + 1, player1, player2, 0);
    } else {
      player1.letter[indicelettre] = choice2;
      creer_arbre(choice1, letters[countletters], 2, indicelettre + 1,
                  countletters + 1, lettre_donnee + 1, player1, player2, 0);
    }
  }

  else if (player == 2) { // Si c'est au joueur 2
    if (pick1 == 0) {
      if (lettre_donnee != n - 1) {
        creer_arbre(choice1, choice2, 2, indicelettre, countletters,
                    lettre_donnee, player1, player2, 1); // Test choix 2eme nb
      }
      player2.letter[indicelettre - 1] = choice1;
      creer_arbre(choice2, letters[countletters], 1, indicelettre,
                  countletters + 1, lettre_donnee + 1, player1, player2, 0);
    } else {
      player2.letter[indicelettre - 1] = choice2;
      creer_arbre(choice1, letters[countletters], 1, indicelettre,
                  countletters + 1, lettre_donnee + 1, player1, player2, 0);
    }
  }

  return;
}

int main() {

  st_player player1;
  st_player player2;

  scanf("%d%d", &n, &q);

  for (int i = 0; i < n; i++) {
    char letter[2];
    scanf("%s", letter);
    letters[i] = letter[0];
  }
  fprintf(stderr, "%s\n", letters);

  nb_lettre_tot = strlen(letters);

  for (int i = 0; i < q; i++) {
    char word[11];
    int score;
    int j = 0;
    scanf("%s%d", word, &score);
    while (word[j] != '\0') {
      point[i].word[j] = word[j];
      j++;
    }
    point[i].score = score;
  }

  best(point);

  for (int i = 0; i < q; i++) {
    fprintf(stderr, "%s  %d\n", point[i].word, point[i].score);
  }

  char choice1 = letters[0];
  char choice2 = letters[1];

  creer_arbre(choice1, choice2, 1, 0, 2, 0, player1, player2, 0);

  return 0;
}

    Présentation des tests

    Afin de coder ce programme et de le valider, il a fallut passer plusieurs tests.

    Test 1

    • Entrée
      4 4
A S R E
SA 2
SE 4
RE 1
A 1
    • Résultat
      ============Test echoue============

==============Sortie==============

lettre joueur 1: SE | lettre joueur 2: RA
score: 4-1

lettre joueur 1: SA | lettre joueur 2: RE
score: 3-1

lettre joueur 1: SE | lettre joueur 2: AR
score: 4-1

lettre joueur 1: SR | lettre joueur 2: AE
score: 0-1

lettre joueur 1: AE | lettre joueur 2: RS
score: 1-0

lettre joueur 1: AS | lettre joueur 2: RE
score: 3-1

lettre joueur 1: AE | lettre joueur 2: SR
score: 1-0

lettre joueur 1: AR | lettre joueur 2: SE
score: 1-4



===========Sortie attendue===========

S 4-1

==================================

      Ce test nous montres plusieurs choses. Tout d’abord, on peut voir ce que calcul le programme, sans la partie minimax qui ne fonctionne pas. Il permet d’obtenir les informations affichées, et les stock dans une structure. De plus, on observe le format de sortie attendue par le site.

    Remarque:

    J’ai pu lors d’une autre tentative créer un programme passant les deux premiers test. Mais il n’utilisait pas la bonne méthode, donc les tests suivants ne passaient pas.

    Pour voir le code cliquez ici.

    Test 1

    • Entrée
      4 4
A S R E
SA 2
SE 4
RE 1
A 1
    • Résultat
      ============Test passe============

==============Sortie==============

S 4-1

==================================

    Test 2

    • Entrée
      2 2
A B
A 10
B 5
    • Résultat
      ============Test passe============

==============Sortie==============

A 10-5

==================================

      Remarque: N’ayant pas trouvé de solution au problème, je ne peux pas présenter une solution de la communauté.

    Doxygene

    Pour plus d’information sur ce programme, voici une page de documentation qui s’interesse au code résolvant ce problème.

    Bilan de ce travail

    Malgré un échec pour résoudre ce problème, j’ai pu créer un arbre des possibilitées utilisant la récursion. J’ai ainsi pu m’entrainer à nouveau sur cette méthode. De plus, le fait d’avoir essayé différentes méthodes pour résoudre ce problème m’a montré les limites de certains systèmes qui me paraissaient viables.

    Author: Mathieu CHEDAS

    Created: 2023-04-02 dim. 12:07