Minimax Simple Example

• Un entier représentant le nombre de lettres dans la pile
• Un entier représentant le nombre de mots formables possibles
• Une chaîne de caractères représentant un mot possible, suivie de son score, un entier

• La lettre à prendre entre la première et le deuxième dans la pile, un caractère
• Le score final si le joueur prend la lettre conseillée, une chaîne de caractères

Pour créer cet algorithme, nous nous aiderons de l’algorithme minimax ou MinMax, un algorithme permettant de comparer facilement et récursivement les solutions finales afin d’obtenir la meilleure.

Cela nous est permis car le jeu ne possède pas un nombre de situations finales élevées.

Pour comprendre cet algorithme, nous pouvons visualiser une partie comme un arbre :

Un arbre est une structure de données composée de 2 éléments :

• Des noeuds, contenant des valeurs
• Des branches, qui relient un noeud à un ou plusieurs autres noeud

Cette structure possède aussi une hiérarchie, c’est-à-dire qu’il existe un noeud central (placé souvent en haut de l’arbre), qui n’est relié qu’à des noeuds secondaires, eux-mêmes reliés à d’autres noeuds, etc…

Ainsi, les noeuds les plus bas dans la hiérarchie (souvent en bas), sont appelées des feuilles.

Dans la résolution, l’arbre que nous étudierons sera un arbre binaire, c’est-à-dire, que chaque noeud possède 2 branches qui le relie aux noeuds inférieurs.

Nous pouvons donc ici visualiser un tour comme un noeud.

Voici donc le premier tour par exemple :

    Digraph{a[label="Tour 1"]
    a

    }

De ce premier tour deux tours suivants sont possibles, si le joueur prend la première, ou la deuxième lettre de la pile (1 ou 2 dans ce cas):

    Digraph{a[label="Tour 1"]b[label="Tour 2"]c[label="Tour 2"]
    a->b[label="1"]

    a->c[label="2"]

    }

Les derniers tours possibles sont représentés par des feuilles.

    Digraph{a[label="Tour 1"]b,c[label="Tour 2"]d,e,f,g[label= "Tour 3"]h,i,j,k,l,m,n,o[label= "Tour 4"]
    a->b
    a->c

    b->{d,e}
    c->{f,g}

    d->{h,i}
    e->{j,k}
    f->{l,m}
    g->{n,o}

    }

Une fois les feuilles atteintes, nous calculons la valeur de ces feuilles, ici, nous calculons le score de chaque joueur et renvoyons la différence entre le score du joueur 1 et du joueur 2.

    Digraph{a[label="Tour 1"]b,c[label="Tour 2"]d,e,f,g[label= "Tour 3"]h[label= "1"]i[label= "-2"]j[label= "8"]k[label= "2"]l[label= "-5"]m[label= "6"]n[label= "7"]o[label= "5"]
    a->b
    a->c

    b->{d,e}
    c->{f,g}

    d->{h,i}
    e->{j,k}
    f->{l,m}
    g->{n,o}

    }

Les noeuds plus haut prendront soit la valeur la plus haute parmi les neouds inférieurs, soit la valeur la plus basse, selon le joueur qui doit jouer pendant le tour représenté par le noeud.

Si le noeud représente le tour du joueur 1 (celui qui doit maximiser l’écart), la valeur choisie sera, de manière triviale, la plus haute, l’inverse serait en effet contre-productif

    Digraph{a[label="Tour 1"]b,c[label="Tour 2"]d[label= "1"]e[label= "8"]f[label= "6"]g[label="7"]h[label= "1"]i[label= "-2"color= "white"]j[label= "8"]k[label= "2"color= "white"]l[label= "-5"color= "white"]m[label= "6"]n[label= "7"]o[label= "5"color= "white"]
    a->b
    a->c

    b->{d,e}
    c->{f,g}

    d->{h,i}
    e->{j,k}
    f->{l,m}
    g->{n,o}

    }

Si le noeud représente le tour du joueur 2 (celui qui doit minimiser l’écart, voire le rendre négatif), la valeur choisie sera donc la plus basse, pour “simuler un coup intelligent face au joueur 1”.

    Digraph{a[label="Tour 1"]b[label= "1"]c[label="6"]d[label= "1"]e[label= "8"color= "white"]f[label= "6"]g[label="7"color= "white"]h[label= "1"]i[label= "-2"color= "white"]j[label= "8"color= "white"]k[label= "2"color= "white"]l[label= "-5"color= "white"]m[label= "6"]n[label= "7"color= "white"]o[label= "5"color= "white"]
    a->b
    a->c

    b->{d,e}
    c->{f,g}

    d->{h,i}
    e->{j,k}
    f->{l,m}
    g->{n,o}

    }

Le coup à jouer pour le joueur 1 sera donc celui qui aura la plus grande valeur entre deux coups que le joueur 2 aura choisi parmi les plus petites valeurs données par le joueur 1 et ainsi de suite.

    Digraph{a[label="6"]b[label= "1"color= "white"]c[label="6"]d[label= "1"color= "white"]e[label= "8"color= "white"]f[label= "6"]g[label="7"color= "white"]h[label= "1"color= "white"]i[label= "-2"color= "white"]j[label= "8"color= "white"]k[label= "2"color= "white"]l[label= "-5"color= "white"]m[label= "6"]n[label= "7"color= "white"]o[label= "5"color= "white"]
    a->b
    a->c

    b->{d,e}
    c->{f,g}

    d->{h,i}
    e->{j,k}
    f->{l,m}
    g->{n,o}

    }

Ici par exemple, le joueur 1 doit commencer par prendre la deuxième lettre de la pile afin de lui garantir un écart de score de 6 avec le joueur 2.

Ici, nous allons utiliser l’algorithme MinMax étudié

Pour chaque tour, deux options nous seront données et la valeur à optimiser pour les deux joueurs est l’écart de score

Nous commençons par créer une chaîne de caractères qui contiendra toutes les lettres de la pile

Ainsi, la première lettre de la chaîne sera la lettre au-dessus de la pile et les lettres suivantes dans la chaîne de caractère sont les lettres qui se trouvent en-dessous.

Nous créons aussi une sorte de dictionnaire qui associe à chaque mot de la liste de mots un score (qui lui a été donné)

Nous appelons ensuite une fonction qui se charge de trouver récursivement par l’algorithme minimax la bonne solution.

Nous donnons à cette fonction les valeurs de bêta et alpha, donc plus et moins l’infini, la pile pleine, les ensembles(vides) de lettres des deux joueurs, le dictionnaire mot-score ainsi que le nombre dans le dictionnaire et enfin la profondeur de l’arbre de recherche (ici fixé à 0, car c’est le premier tour)

Nous entrons ainsi dans une fonction récursive:

• Si la pile de lettres est vide, nous calculons le score des deux joueurs et l’enregistrerons dans une valeur. Nous renvoyons ensuite cette structure.

• Si c’est au tour du joueur 1 (celui que nous devons faire gagner):

  • Nous prenons une valeur de moins l’infini, cela nous servira de “score à battre” pour chaque sous-noeud
  • Nous copions la pile de lettres ainsi que l’ensemble de lettres du joueur 1.
  • Nous retirons ensuite la lettre au-dessus de la copie de la pile de lettres pour la mettre dans la copie de l’ensemble de lettres du joueur 1
  • Nous appelons ensuite récursivement la fonction minmax avec la pile et l’ensemble de lettres modifiés, afin de récupérer le noeud avec le score maximum récupéré dans les feuilles.
  • Le “score à battre” prend le meilleur score entre le “score à battre” actuel et le score récupéré à la suite de l’appel de la fonction minmax
  • Nous recommençons ensuite une deuxième fois ces instructions en réinitialisant les copies de la pile et de l’ensemble de lettre, puis en prenant cette fois la deuxième lettre de la pile
  • Avant de recommencer, nous regardons si le différence du “score à battre” est plus grande que alpha.
  • Si tel est le cas, alpha devient la différence du score des deux joueurs du “score à battre”.
  • Enfin, si alpha est inférieur à beta, nous ne recommençons pas avec la deuxième lettre de la pile, cela évite donc de faire des appels inutils

  Si nous sommes en haut de l’arbre de recherche, nous affichons la lettre à prendre, ainsi que le score garanti en prenant cette lettre

• Si c’est au tour du deuxième joueur, l’algorithme est similaire à celui du premier joueur en changeant plusieurs détails:
  • Le “score à battre” est de plus l’infini, et prend la valeur du score le plus bas
  • L’ensemble de lettres copié est celui du joueur 2
  • Beta prend la valeur du score le plus bas, et alpha reste inchangé, le test et ses conséquences restent les mêmes.

La fonction finit donc par afficher la lettre recommendée ainsi que le score garanti, la fonction principale s’arrête donc après le premier appel.

    char bd[100] = "";
    wscore_t dict[100];

Nous initialisons la pile et le dictionnaire

    struct word_score {
        int score;
        char word[27];
    };

Une entrée du dictionnaire

Nous appelons maintenant la fonction principale minmax

    minmax(bd, -65535, 65535, 1, "", "", dict,  q, 0);

Ici 65535 représente l’infini, un tel score ne sera jamais atteint

Nous appelons la fonctions minmax

pscore_t minmax(char letters[], int a, int b, int play, char p1[], char p2[], wscore_t dict[], int n, int d) {

Prototype de la fonction minmax, letters est la pile, a et b sont alpha et beta, play détermine le joueur qui doit jouer (1 si vrai, 2 sinon), p1 et p2 sont les ensembles de lettres des joueurs 1 et 2, dict est le tableau d’entrées de dictionnaire, n est le nombre de mots possible et d la profondeur, 0 étant le premier tour, donc en haut de l’arbre.

    if(strlen(letters) == 0) {
        pscore_t output = {score(p1, dict, n),score(p2, dict, n)};
        return output;
    }

Cas d’arrêt, nous calculons le score des deux joueurs en renvoyant les deux scores, cela permettra de plus facilement afficher le score final, 7 les valeurs qui serviront de test seront la différence entre le score du premier joueur et du deuxième

    struct player_score {
        int score1;
        int score2;
    };

La structure score:

    int score(char result[], wscore_t dict[], int n){

Prototype de la fonction de calcul de score d’un joueur

    int points = 0;

Nous initialisons les points à 0

for(int i = 0; i < n; i++) {

Pour chaque entrée du dictionnaire

    for(int j = 0; j < strlen(dict[i].word); j++) {

Pour chaque lettre d’un mot du dictionnaire

Si la lettre ne se trouve pas dans l’ensemble de lettres du joueur, nous passons au mot suivant

    if(strchr(result, dict[i].word[j]) == NULL) {
        break;
    }

Sinon, si nous arrivons à la fin du mot, nous ajoutons au score du joueur le nombre de points que donne le mot

    else if(j == strlen(dict[i].word)-1){
        points += dict[i].score;
    }
return points;

Nous renvoyons le score du joueur

Revenons au premier cas récursif de la fonction minmax

    if(play)

Si le joueur 1 joue :

    int answer = 0;
    pscore_t value = {0, 65535};
    char l[27] = "", x[27] = "";
    strcpy(l, letters);

Nous initialisons les variables : answer est le numéro de la lettre à prendre dans la pile

Ici 65535 représente l’infini, un tel score ne sera jamais atteint

    for(int i = 0; i < 2; i++) {

Nous entrons dans une boucle qui se réalise deux fois, pour prendre les deux premières lettres seulement

    sprintf(x, "%s%c", p1, l[i]);
    strremove(l, i)

Nous retirons la i-ème lettre de la pile et l’ajoutons à l’inventaire du joueur 1

void strremove(char *str, int n){
    char out[27] = "";
    int j = 0;
    for(int i = 0; i < strlen(str);i++){
        if(i != n){
            out[j] = str[i];
            j++;
        }
    }
    strcpy(str, out);
}

Fonction strremove qui retire un caractère de la pile

    pscore_t test = minmax(l, a, b, 0, x, p2, dict, n, d+1);

Nous appelons la fonction minmax, avec la pile sans la i-ème lettre, qui se trouve maintenant dans l’inventaire du joueur 1. Nous indiquons aussi que c’est au joueur 2 de jouer

    x[strlen(x)-1] = '\0';
    strcpy(l, letters);     

Nous retirons à la copie de l’inventaire du joueur 1 la i-ème lettre et la remettons dans la pile (ici, nous recopions la pile donnée en argument de la fonction pour la mettre dans la copie de la pile)

    if((test.score1-test.score2)>(value.score1-value.score2)){
        value=test;
        answer = i;
    }

Si la différence de score est plus grande que le score à battre, le score à battre prend la valeur du score obetenu avec la fonction et answer prend la valeur de i, ce qui veut dire qu’il faut prendre la i-ème lettre

a = (value.score1-value.score2)>a?(value.score1-value.score2):a; if(b<=a)break; Alpha prend la valeur maximum entre la différence du score à battre et alphe lui-même, et si alpha est plus petit que beta, nous sortons immédiatement de la boucle et arrêtons la recherche

À la fin de la boucle (recherche), le score à battre est renvoyé en étant le plus grand possible

    return value;

Les différences avec le joueur 2 sont celles-ci: La différence du score à battre est de plus l’infini, l’inventaire du joueur 2 est copié et la fonction est appelée avec la pile et l’inventaire du joueur 2 changés et en faisant jouer le joueur 1

Avant la recherche :

    pscore_t value = {65535, 0};         
    sprintf(y, "%s%c", p2, l[i]);   
    pscore_t test = minmax(l, a, b, 1, p1, y, dict, n, d+1);

Et pour chacune des deux premières lettres de la pile restante

    value = (test.score1-test.score2)<(value.score1-value.score2)?test:value;
    b = (test.score1-test.score2)<b?(test.score1-test.score2):b;
    if(b<=a)break;

Le score à battre cherche donc à être le plus faible possible, de même que pour beta.

Le même test est fait que pour le joueur 1.

Lorsque la meilleure possibilité remonte à la racine (tour 1), nous vérifions si la profondeur(le tour) est le premier, dans ce cas, après avoir selectionné la meilleure possibilité, nous renvoyons la lettre recommandée, qui est celle assurant le meilleur coup ainsi que les scores des deux joueurs à la fin de la partie :

if(!d) printf("%c %d-%d\n", letters[answer], value.score1, value.score2);

Cette instruction se situe juste avant le renvoi du score à battre (dans le cas où nous ne somme pas à la racine)

Voici le code sans commentaire :

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

typedef struct word_score wscore_t;
typedef struct player_score pscore_t;
struct word_score {
    int score;
    char word[27];
};
struct player_score {
    int score1;
    int score2;
};

int score(char result[], wscore_t dict[], int n){
    int points = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < strlen(dict[i].word); j++) {
            if(strchr(result, dict[i].word[j]) == NULL) {
                break;
            }
            else if(j == strlen(dict[i].word)-1){
                points += dict[i].score;
            }
        }
    }
    return points;
}

void strremove(char *str, int n){
    char out[27] = "";
    int j = 0;
    for(int i = 0; i < strlen(str);i++){
        if(i != n){
            out[j] = str[i];
            j++;
        }
    }
    strcpy(str, out);
}

pscore_t minmax(char letters[], int a, int b, int play, char p1[], char p2[], wscore_t dict[], int n, int d) {
    if(strlen(letters) == 0) {
        pscore_t output = {score(p1, dict, n),score(p2, dict, n)};
        return output;
    }
    if(play) {
        int answer = 0;
        pscore_t value = {0, 65535};
        char l[27] = "", x[27] = "";
        strcpy(l, letters);
        
        for(int i = 0; i < 2; i++) {
            sprintf(x, "%s%c", p1, l[i]);
            strremove(l, i);
            
            pscore_t test = minmax(l, a, b, 0, x, p2, dict, n, d+1);
 
            x[strlen(x)-1] = '\0';
            strcpy(l, letters);            

            if((test.score1-test.score2)>(value.score1-value.score2)){
                value=test;
                answer = i;
            }
            a = (value.score1-value.score2)>a?(value.score1-value.score2):a;
            if(b<=a)break;
        }
        if(!d) printf("%c %d-%d\n", letters[answer], value.score1, value.score2);
        return value;
    }
    else {
        int answer = 0;
        pscore_t value = {65535, 0};
        char l[27] = {'\0'}, y[27] = {'\0'};
        strcpy(l, letters);

        for(int i = 0; i < 2 ; i++) {
            sprintf(y, "%s%c", p2, l[i]);
            strremove(l, i);
            pscore_t test = minmax(l, a, b, 1, p1, y, dict, n, d+1);
            y[strlen(y)-1] = '\0';
            strcpy(l, letters);
            value = (test.score1-test.score2)<(value.score1-value.score2)?test:value;
            b = (value.score1-value.score2)<b?(value.score1-value.score2):b;
            if(b<=a)break;
        }
        if(!d) printf("%c %d-%d\n", letters[answer], value.score1, value.score2);
        return value;
    }

}

int main()
{
    int n;
    int q;
    char bd[100] = "";
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++) {
        char letter[2];
        scanf("%s", letter);
        sprintf(bd, "%s%c", bd, letter[0]);
    }
    
    wscore_t dict[100];
    for (int i = 0; i < q; i++) {
        char word[11];
        int score;
        scanf("%s%d", word, &score);
        dict[i].score = score;
        sprintf(dict[i].word,"%s", word);
    }
    minmax(bd, -65535, 65535, 1, "", "", dict,  q, 0);
    return 0;
}

Ainsi, le code en entier, sans commentaire est le suivant :