Minimax simple example

On nous fournit:

• Un entier N qui correspond au nombre de lettres dans la pile;
• Un entier Q qui correspond au nombre de mots de score disponibles;
• Une liste de N lettres toutes différentes, séparées par des espaces;
• Q lignes qui contiennent chacune un mot composé des lettres disponibles, ainsi que son score associé.

Deux joueurs s’affrontent en récupérant, tour à tour, une lettre parmi celles disponibles dans une pile. À chaque tour, ils peuvent choisir de prendre soit la première lettre, soit la deuxième. Lors du dernier tour, le dernier joueur n’a pas d’autre choix que de prendre la dernière lettre restante. Une fois toutes les lettres récupérées, les joueurs marquent des points en formant des mots à partir de leurs lettres collectées. Un dictionnaire donné indique les mots valides ainsi que leur score. Les lettres peuvent être utilisées plusieurs fois pour créer plusieurs mots.

L’objectif est de conseiller le premier joueur sur le choix optimal de sa première lettre afin de maximiser son avantage sur son adversaire. Pour cela, il faut :

• Simuler les différents choix possibles et leurs conséquences.
• Estimer les scores finaux des joueurs en utilisant une approche stratégique optimale (Minimax, et potentiellement avec l’élagage alpha-bêta pour améliorer l’efficacité du calcul).
• Déterminer la meilleure lettre à choisir en premier.

L’objectif du premier joueur est d’obtenir la plus grande différence positive entre son score et celui de son adversaire.

Il faut afficher le résultat sous la forme : lettre choisie, suivi du score attendu pour chaque joueur (S1-S2).

J’ai utilisé un algorithme permettant d’explorer toutes les options possibles et d’évaluer leur impact sur le score final. Afin d’optimiser cette analyse et éviter de tester des scénarios inutiles, j’applique une méthode de filtrage qui réduit les calculs. Grâce à cette simulation complète, j’ai identifier le meilleur choix de lettre pour le premier joueur, garantissant le score le plus avantageux possible, avant d’afficher la solution finale.

Je commence d’abord par créer deux tructures de données pour organiser les informations ainsi que pour manipuler facilement les données du jeu :

• wscore_t stocke les mots du dictionnaire et leur score.
• pscore_t contient les scores des deux joueurs.

Ensuite je crée une première fonction de calcul des scores (score) qui permet de parcourir le dictionnaire pour vérifier quels mots peuvent être construits avec les lettres collectées par un joueur. Pour cela, elle commence par initialiser le score à zéro, elle vérifie ensuite que chaque lettre d’un mot du dictionnaire est bien présente dans la chaîne resultat grâce à strchr() et enfin elle ajoute le score du mot si toutes ses lettres sont présentes. La fonction strchr() est très intéressante, en effet elle est inclut dans la librairie string.h, elle permet, en prennant comme argument une chaine de caractère et un caractère, de retourner un pointeur sur la première occurence du caractère passé en argument dans la chaine de caractère également passé en argument de la fonction. La fonction score retourne pour finir le score total obtenu par le joueur.

J’implémente aussi une fonction qui permet la suppression d’une lettre dans la pile (supprimerStr). En effet, lorsque le joueur sélectionne une lettre, elle doit être retirée de la pile. J’utilise donc la fonction memmove() qui décale les caractères à gauche pour supprimer la lettre choisie.

Je finis par implémenter ma dernière fonction qui est l’algorithme Minimax avec élagage alpha-bêta (minmax). Cette fonction est le cœur du programme. Elle simule chaque tour en analysant toutes les possibilités jusqu’à la fin du jeu. Il y a plusieurs possibilités:

• Le cas de base lorsqu’il ne reste plus de lettres. Dans ce cas là, le programme calcule les scores des joueurs et retourne le résultat.
• Ensuite, vient le tour du joueur 1 qui correspond à la partie où on effectue la maximisation de son score par rapport à celui de son adversaire. Pour chaque choix possible, on copie temporairement la pile et les lettres du joueur, on ajoute la lettre choisie à la chaîne du joueur, puis on supprime la lettre de la pile. A la suite de tout cela, on effectue un appel récursif minmax() avec les nouvelles données, si le score obtenu est meilleur que le précédent, il est conservé, et si concernant la profondeur: depth = 0, l’algorithme sauvegarde la meilleure première lettre (*bestChoice).
• Puis, c’est au tour du joueur 2 (minimisation du score du joueur 1), le programme essaie de réduire l’écart en choisissant la lettre la moins favorable à l’adversaire. Le programme suis la même logique que pour le joueur 1, mais ici, il sélectionne le pire résultat pour son adversaire.
• Pour finir, il reste l’élagage alpha-bêta qui permet d’arréter la recherche au bon moment. De ce fait, pour éviter de tester des choix inutiles, on utilise deux bornes (alpha et beta) :
  • alpha représente la meilleure valeur trouvée pour le joueur maximisant.
  • beta représente la meilleure valeur trouvée pour le joueur minimisant.
  • Si beta <= alpha, on coupe la recherche dans cet arbre.

Concernant le main, il lit d’abord les entrées, puis appel la fonction minmax() avec les lettres initiales et une chaîne vide pour chaque joueur pour rechercher la meilleure première lettre (bestChoice). Puis, il finit par afficher la lettre optimale et les scores finaux.

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

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

int score(char resultat[], wscore_t dict[], int q) {
    int points = 0;
    for (int i = 0; i < q; i++) {
        bool valid = true;
        for (int j = 0; j < strlen(dict[i].word); j++) {
            if (strchr(resultat, dict[i].word[j]) == NULL) {
                valid = false;
                break;
            }
        }
        if (valid) {
            points += dict[i].score;
        }
    }
    return points;
}

void supprimerStr(char *str, int n) {
    memmove(&str[n], &str[n+1], strlen(str) - n);
}

pscore_t minmax(char lettres[], int alpha, int beta, int play, char p1[], char p2[], wscore_t dict[], int q, int depth, char *bestChoice) {
    if (strlen(lettres) == 0) {
        return (pscore_t){score(p1, dict, q), score(p2, dict, q)};
    }
    pscore_t bestMove;
    char tempLetters[27], tempP1[27], tempP2[27];
    if (play) {
        bestMove.score1 = 0;
        bestMove.score2 = 65535;
        for (int i = 0; i < 2; i++) {
            strcpy(tempLetters, lettres);
            strcpy(tempP1, p1);
            sprintf(tempP1, "%s%c", p1, tempLetters[i]);
            supprimerStr(tempLetters, i);
            pscore_t result = minmax(tempLetters, alpha, beta, 0, tempP1, p2, dict, q, depth + 1, bestChoice);
            if ((result.score1 - result.score2) > (bestMove.score1 - bestMove.score2)) {
                bestMove = result;
                if (depth == 0) {
                    *bestChoice = lettres[i];
                }
            }
            alpha = (bestMove.score1 - bestMove.score2) > alpha ? (bestMove.score1 - bestMove.score2) : alpha;
            if (beta <= alpha) break;
        }
    } else {
        bestMove.score1 = 65535;
        bestMove.score2 = 0;
        for (int i = 0; i < 2; i++) {
            strcpy(tempLetters, lettres);
            strcpy(tempP2, p2);
            sprintf(tempP2, "%s%c", p2, tempLetters[i]);
            supprimerStr(tempLetters, i);
            pscore_t result = minmax(tempLetters, alpha, beta, 1, p1, tempP2, dict, q, depth + 1, bestChoice);
            if ((result.score1 - result.score2) < (bestMove.score1 - bestMove.score2)) {
                bestMove = result;
            }
            beta = (bestMove.score1 - bestMove.score2) < beta ? (bestMove.score1 - bestMove.score2) : beta;
            if (beta <= alpha) break;
        }
    }
    return bestMove;
}

int main() {
    int n, q;
    char letters[27] = "";
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++) {
        char letter[2];
        scanf("%s", letter);
        sprintf(letters, "%s%c", letters, letter[0]);
    }
    wscore_t dict[100];
    for (int i = 0; i < q; i++) {
        char word[27];
        int score;
        scanf("%s%d", word, &score);
        dict[i].score = score;
        strcpy(dict[i].word, word);
    }
    char bestChoice = ' ';
    pscore_t finalScore = minmax(letters, -65535, 65535, 1, "", "", dict, q, 0, &bestChoice);
    printf("%c %d-%d\n", bestChoice, finalScore.score1, finalScore.score2);
    return 0;
}