Rapport : Minimax simple example

Table des matières

1. Introduction

1.1. Principe de focntionnment

Url du challenge : https://www.codingame.com/ide/puzzle/minimax-simple-example

L’objectif de ce challenge est de jouer à un jeu de lettres contre un adversaire.

Au début les 2 joueurs voient un tas de lettres, toutes différentes. À tour de rôle, ils peuvent choisir de prendre la première ou la deuxième lettre de la pile. Au dernier tour, le dernier joueur n’a d’autre choix que de prendre la dernière lettre. Quand il ne reste plus lettre, les joueurs doivent former des mots avec les lettres qu’ils ont choisies. Puis ils comptent leurs points. Un dictionnaire donne les mots possibles avec leurs gains associés. Les lettres peuvent être utilisées plusieurs fois pour former plusieurs mots.

L’objectif est de conseiller le premier joueur pour son premier tour : quelle lettre est la meilleure à choisir, et quels scores sont attendus pour chaque joueur, lorsque les deux joueurs jouent leur meilleur choix à chaque tour.

Pour le joueur 1, le but est d’avoir la différence positive la plus élevée entre son score et le score de l’adversaire. Par exemple, ’10-2’ est un meilleur résultat que ’15-14’, qui est meilleur que ’20-25’.

1.2. Données fournies

On reçoit deux entiers : `N` le nombre de lettres dans le tas, et `Q` le nombre de mots dans le dictionnaire. Puis on recoit le tas de lettres sous la forme d’une chaîne de caractères ou chaque lettre est séparée par un espace. Enfin on recoit le dictionnaire sous la forme d’une liste de mots et de leurs gains associés, séparés par un espace.

1.3. Données à fournir

On doit fournir la lettre à prendre pour le premier tour, et le score attendu pour le joueur 1 et le joueur 2.

1.4. Contraintes

  • 2 ≤ N ≤ 26
  • 1 ≤ Q ≤ 1000

2. Méthode de résolution

Le principe de résolution est le suivant :

On commence par lire les données d’entrée et les stocker dans des structures de données adaptées : un tableau de `wordt` pour le dictionnaire, et une chaîne de caractères pour le tas de lettres. Puis on appelle la fonction minimax. Cette fonction va parcourir l’arbre des possibilités et renvoyer le meilleur résultat possible pour le joueur 1. A chaque appel de la fonction, si c’est le tour du joueur 1, on cherche le meilleur coup entre les deux possibilités (prendre la première ou la deuxième lettre du tas). Si c’est le tour de l’adversaire, on cherche le pire coup entre les deux possibilités. Pour chacune des deux possibilités, on appelle la fonction minimax avec les données mises à jour (le tas de lettres sans la lettre prise, et la main du joueur 1 ou de l’adversaire mise à jour). Lorsqu’il n’y a plus de lettre dans le tas, on calcule le score des deux joueurs et on renvoie le résultat.

2.1. Code

On commence par définir les structures de données utilisées :

  • wordt : structure pour stocker un mot et son score
  • resultt : structure pour stocker le score du joueur et de l’adversaire, ainsi que la différence entre les deux. Elle contient également la lettre à prendre au 1er tour.
/**
 * @struct word_t
 * @brief Structure pour stocker un mot et son score.
 */
typedef struct {
    char word[13]; ///< Le mot (chaîne de caractères)
    int score; ///< Le score associé au mot
} word_t;

/**
 * @struct result_t
 * @brief Structure pour stocker le score du joueur et de l'adversaire, ainsi que la différence entre les deux.
 * Elle contient également la lettre à prendre au 1er tour.
 * Elle est utilisée pour le retour de la fonction minimax.
 */
typedef struct {
    int player_score; ///< Score du joueur
    int opponent_score; ///< Score de l'adversaire
    int diff; ///< Différence entre le score du joueur et celui de l'adversaire
    char best_letter; ///< Première lettre a prendre au 1er tour
} result_t;

On définit ensuite une fonction qui vérifie si un mot peut être formé avec les lettres données. 

/**
 * @brief Fonction qui vérifie si un mot peut être formé avec les lettres données.
 * @param word Le mot à vérifier
 * @param letters Les lettres disponibles
 * @return true si le mot peut être formé, false sinon
 */
bool is_word_possible(char *word, char *letters) {
    int i, j;
    int word_len = strlen(word);
    int letters_len = strlen(letters);

    for (i = 0; i < word_len; i++) {
        for (j = 0; j < letters_len; j++) {
            if (word[i] == letters[j]) {
                break;
            }
        }
        if (j == letters_len) {
            return false;
        }
    }
    return true;
}

On defini une fonction qui calcule le score total d’un joueur. 

/**
 * @brief Fonction qui calcule le score total d'un joueur.
 * @param letters Les lettres dans la main du joueur
 * @param word_list La liste des mots possibles
 * @param nb_words Le nombre de mots dans la liste
 * @return Le score total du joueur
 */
int points(char *letters, word_t *word_list, int nb_words) {
    int total_score = 0;

    for (int i = 0; i < nb_words; i++) {
        if (is_word_possible(word_list[i].word, letters)) {
            total_score += word_list[i].score;
        }
    }

    return total_score;
}

On définit deux fonctions qui copient une chaîne de caractères sans le premier ou le deuxième caractère. 

/**
 * @brief Fonction qui copie une chaîne de caractères sans le premier caractère.
 * @param destination La chaîne de caractères de destination (doit être allouée avant l'appel de la fonction)
 * @param source La chaîne de caractères source
 * @param len La longueur de la chaîne de caractères source
 */
void copy_string_without_first_letter(char *destination, char *source, int len) {
    // destination needs to be len - 1 long
    for (int i = 0; i < len; i++) {
        destination[i] = source[i + 1];
    }
}

/**
 * @brief Fonction qui copie une chaîne de caractères sans le deuxième caractère.
 * @param destination La chaîne de caractères de destination (doit être allouée avant l'appel de la fonction)
 * @param source La chaîne de caractères source
 * @param len La longueur de la chaîne de caractères source
 */
void copy_string_without_second_letter(char *destination, char *source, int len) {
    // destination needs to be len - 1 long
    for (int i = 0; i < len; i++) {
        destination[i] = source[i + 1];
    }
    destination[0] = source[0];
}

On définit ensuite la fonction minimax qui calcule le score du joueur et de l’adversaire en utilisant l’algorithme minimax et qui retourne un pointeur vers une structure resultt contenant le score du joueur et de l’adversaire, la différence entre les deux et la lettre à prendre au 1er tour. 

/**
 * @brief Fonction qui calcule le score du joueur et de l'adversaire en utilisant l'algorithme minimax.
 * @param letters Les lettres disponibles
 * @param hand Les lettres dans la main du joueur
 * @param opponent_hand Les lettres dans la main de l'adversaire
 * @param maximizing_player true si c'est au tour du joueur, false si c'est au tour de l'adversaire
 * @param alpha Valeur de alpha
 * @param beta Valeur de beta
 * @param word_list La liste des mots possibles
 * @param nb_word Le nombre de mots dans la liste
 * @return Un pointeur vers une structure result_t contenant le score du joueur et de l'adversaire, ainsi que la différence entre les deux.
 */
result_t * minimax(char *letters, char *hand, char *opponent_hand, bool maximizing_player, int alpha, int beta, word_t *word_list, int nb_word) {

    if (strlen(letters) == 1) {
        char *new_opponent_hand = malloc(strlen(opponent_hand) + 3 * sizeof *new_opponent_hand);
        strcpy(new_opponent_hand, opponent_hand);
        new_opponent_hand[strlen(opponent_hand) + 1] = '\0';
        new_opponent_hand[strlen(opponent_hand)] = letters[0];

        int player_score = points(hand, word_list, nb_word);
        int opponent_score = points(new_opponent_hand, word_list, nb_word);

        result_t *result = malloc(sizeof *result);
        result->player_score = player_score;
        result->opponent_score = opponent_score;
        result->diff = player_score - opponent_score;
        result->best_letter = hand[0];

        free(new_opponent_hand);
        return result;
    }

    result_t *result1;
    result_t *result2;
    int len = strlen(letters);
    char *new_letters = malloc(len * sizeof *new_letters);
    if (maximizing_player) {
        // Coup du joueur
        char *new_hand = malloc((strlen(hand) + 2) * sizeof *new_hand); // +1 pour le \0 et +1 pour la lettre
        strcpy(new_hand, hand);
        new_hand[strlen(hand) + 1] = '\0';

        // on choisit la première lettre
        copy_string_without_first_letter(new_letters, letters, len);
        new_hand[strlen(hand)] = letters[0];
        result1 = minimax(new_letters, new_hand, opponent_hand, false, alpha, beta, word_list, nb_word);
        alpha = result1->diff > alpha ? result1->diff : alpha;
        if (beta <= alpha) {
            free(new_hand);
            free(new_letters);
            return result1;
        }

        // on choisit la seconde lettre
        copy_string_without_second_letter(new_letters, letters, len);
        new_hand[strlen(hand)] = letters[1];
        result2 = minimax(new_letters, new_hand, opponent_hand, false, alpha, beta, word_list, nb_word);
        free(new_hand);
        free(new_letters);
        if (result1->diff >= result2->diff) {
            free(result2);
            return result1;
        } else {
            free(result1);
            return result2;
        }
    } else {
        // Coup de l'adversaire
        char *new_opponent_hand = malloc((strlen(opponent_hand) + 2) * sizeof *new_opponent_hand);
        strcpy(new_opponent_hand, opponent_hand);
        new_opponent_hand[strlen(opponent_hand) + 1] = '\0';

        // on choisit la première lettre
        copy_string_without_first_letter(new_letters, letters, len);
        new_opponent_hand[strlen(opponent_hand)] = letters[0];

        result1 = minimax(new_letters, hand, new_opponent_hand, true, alpha, beta, word_list, nb_word);
        beta = result1->diff < beta ? result1->diff : beta;
        if (beta <= alpha) {
            free(new_opponent_hand);
            free(new_letters);
            return result1;
        }

        // on choisit la deuxieme lettre
        copy_string_without_second_letter(new_letters, letters, len);
        new_opponent_hand[strlen(opponent_hand)] = letters[1];
        result2 = minimax(new_letters, hand, new_opponent_hand, true, alpha, beta, word_list, nb_word);
        free(new_opponent_hand);
        free(new_letters);
        if (result1->diff <= result2->diff) {
            free(result2);
            return result1;
        } else {
            free(result1);
            return result2;
        }
    }
}

On définit enfin la fonction principale, elle commence par lire les données d’entrée, puis appelle la fonction minimax et affiche le résultat. 

/**
 * @brief Fonction principale
 * @return 0 si le programme s'est terminé correctement
 */
int main() {
    int n; // the number of letters in the stack
    int q; // the number of words in the list
    scanf("%d%d", &n, &q);

    char *letters = malloc((n + 1) * sizeof *letters);
    for (int i = 0; i < n; i++) {
        scanf("%s", &letters[i]);
    }
    letters[n] = '\0';

    word_t *words = malloc(q * sizeof *words);
    for (int i = 0; i < q; i++) {
        scanf("%s%d", words[i].word, &words[i].score);
    }

    int max_value = points(letters, words, q) - 0 + 1;
    int min_value = -max_value;

    char *hand = malloc(n / 2 * sizeof *hand);
    hand[0] = '\0';

    char *opponent_hand = malloc(n / 2 * sizeof *opponent_hand);
    opponent_hand[0] = '\0';

    result_t *result = minimax(letters, hand, opponent_hand, true, min_value, max_value, words, q);
    printf("%c %d-%d", result->best_letter, result->player_score, result->opponent_score);

    free(letters);
    free(words);
    free(hand);
    free(opponent_hand);
    free(result);

    return 0;
}

2.2. Implémentation complète

/**
   * @file minimax-example.c
   * @brief Résolution du problème "minimax-simple-example" de Codingame
   * @author Jules GIRARD
   * @version 1.0
   * @date 2023-04-04
   */
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

/**
 * @struct word_t
 * @brief Structure pour stocker un mot et son score.
 */
typedef struct {
    char word[13]; ///< Le mot (chaîne de caractères)
    int score; ///< Le score associé au mot
} word_t;

/**
 * @struct result_t
 * @brief Structure pour stocker le score du joueur et de l'adversaire, ainsi que la différence entre les deux.
 * Elle contient également la lettre à prendre au 1er tour.
 * Elle est utilisée pour le retour de la fonction minimax.
 */
typedef struct {
    int player_score; ///< Score du joueur
    int opponent_score; ///< Score de l'adversaire
    int diff; ///< Différence entre le score du joueur et celui de l'adversaire
    char best_letter; ///< Première lettre a prendre au 1er tour
} result_t;

/**
 * @brief Fonction qui vérifie si un mot peut être formé avec les lettres données.
 * @param word Le mot à vérifier
 * @param letters Les lettres disponibles
 * @return true si le mot peut être formé, false sinon
 */
bool is_word_possible(char *word, char *letters) {
    int i, j;
    int word_len = strlen(word);
    int letters_len = strlen(letters);

    for (i = 0; i < word_len; i++) {
        for (j = 0; j < letters_len; j++) {
            if (word[i] == letters[j]) {
                break;
            }
        }
        if (j == letters_len) {
            return false;
        }
    }
    return true;
}

/**
 * @brief Fonction qui calcule le score total d'un joueur.
 * @param letters Les lettres dans la main du joueur
 * @param word_list La liste des mots possibles
 * @param nb_words Le nombre de mots dans la liste
 * @return Le score total du joueur
 */
int points(char *letters, word_t *word_list, int nb_words) {
    int total_score = 0;

    for (int i = 0; i < nb_words; i++) {
        if (is_word_possible(word_list[i].word, letters)) {
            total_score += word_list[i].score;
        }
    }

    return total_score;
}

/**
 * @brief Fonction qui copie une chaîne de caractères sans le premier caractère.
 * @param destination La chaîne de caractères de destination (doit être allouée avant l'appel de la fonction)
 * @param source La chaîne de caractères source
 * @param len La longueur de la chaîne de caractères source
 */
void copy_string_without_first_letter(char *destination, char *source, int len) {
    // destination needs to be len - 1 long
    for (int i = 0; i < len; i++) {
        destination[i] = source[i + 1];
    }
}

/**
 * @brief Fonction qui copie une chaîne de caractères sans le deuxième caractère.
 * @param destination La chaîne de caractères de destination (doit être allouée avant l'appel de la fonction)
 * @param source La chaîne de caractères source
 * @param len La longueur de la chaîne de caractères source
 */
void copy_string_without_second_letter(char *destination, char *source, int len) {
    // destination needs to be len - 1 long
    for (int i = 0; i < len; i++) {
        destination[i] = source[i + 1];
    }
    destination[0] = source[0];
}

/**
 * @brief Fonction qui calcule le score du joueur et de l'adversaire en utilisant l'algorithme minimax.
 * @param letters Les lettres disponibles
 * @param hand Les lettres dans la main du joueur
 * @param opponent_hand Les lettres dans la main de l'adversaire
 * @param maximizing_player true si c'est au tour du joueur, false si c'est au tour de l'adversaire
 * @param alpha Valeur de alpha
 * @param beta Valeur de beta
 * @param word_list La liste des mots possibles
 * @param nb_word Le nombre de mots dans la liste
 * @return Un pointeur vers une structure result_t contenant le score du joueur et de l'adversaire, ainsi que la différence entre les deux.
 */
result_t * minimax(char *letters, char *hand, char *opponent_hand, bool maximizing_player, int alpha, int beta, word_t *word_list, int nb_word) {

    if (strlen(letters) == 1) {
        char *new_opponent_hand = malloc(strlen(opponent_hand) + 3 * sizeof *new_opponent_hand);
        strcpy(new_opponent_hand, opponent_hand);
        new_opponent_hand[strlen(opponent_hand) + 1] = '\0';
        new_opponent_hand[strlen(opponent_hand)] = letters[0];

        int player_score = points(hand, word_list, nb_word);
        int opponent_score = points(new_opponent_hand, word_list, nb_word);

        result_t *result = malloc(sizeof *result);
        result->player_score = player_score;
        result->opponent_score = opponent_score;
        result->diff = player_score - opponent_score;
        result->best_letter = hand[0];

        free(new_opponent_hand);
        return result;
    }

    result_t *result1;
    result_t *result2;
    int len = strlen(letters);
    char *new_letters = malloc(len * sizeof *new_letters);
    if (maximizing_player) {
        // Coup du joueur
        char *new_hand = malloc((strlen(hand) + 2) * sizeof *new_hand); // +1 pour le \0 et +1 pour la lettre
        strcpy(new_hand, hand);
        new_hand[strlen(hand) + 1] = '\0';

        // on choisit la première lettre
        copy_string_without_first_letter(new_letters, letters, len);
        new_hand[strlen(hand)] = letters[0];
        result1 = minimax(new_letters, new_hand, opponent_hand, false, alpha, beta, word_list, nb_word);
        alpha = result1->diff > alpha ? result1->diff : alpha;
        if (beta <= alpha) {
            free(new_hand);
            free(new_letters);
            return result1;
        }

        // on choisit la seconde lettre
        copy_string_without_second_letter(new_letters, letters, len);
        new_hand[strlen(hand)] = letters[1];
        result2 = minimax(new_letters, new_hand, opponent_hand, false, alpha, beta, word_list, nb_word);
        free(new_hand);
        free(new_letters);
        if (result1->diff >= result2->diff) {
            free(result2);
            return result1;
        } else {
            free(result1);
            return result2;
        }
    } else {
        // Coup de l'adversaire
        char *new_opponent_hand = malloc((strlen(opponent_hand) + 2) * sizeof *new_opponent_hand);
        strcpy(new_opponent_hand, opponent_hand);
        new_opponent_hand[strlen(opponent_hand) + 1] = '\0';

        // on choisit la première lettre
        copy_string_without_first_letter(new_letters, letters, len);
        new_opponent_hand[strlen(opponent_hand)] = letters[0];

        result1 = minimax(new_letters, hand, new_opponent_hand, true, alpha, beta, word_list, nb_word);
        beta = result1->diff < beta ? result1->diff : beta;
        if (beta <= alpha) {
            free(new_opponent_hand);
            free(new_letters);
            return result1;
        }

        // on choisit la deuxieme lettre
        copy_string_without_second_letter(new_letters, letters, len);
        new_opponent_hand[strlen(opponent_hand)] = letters[1];
        result2 = minimax(new_letters, hand, new_opponent_hand, true, alpha, beta, word_list, nb_word);
        free(new_opponent_hand);
        free(new_letters);
        if (result1->diff <= result2->diff) {
            free(result2);
            return result1;
        } else {
            free(result1);
            return result2;
        }
    }
}

/**
 * @brief Fonction principale
 * @return 0 si le programme s'est terminé correctement
 */
int main() {
    int n; // the number of letters in the stack
    int q; // the number of words in the list
    scanf("%d%d", &n, &q);

    char *letters = malloc((n + 1) * sizeof *letters);
    for (int i = 0; i < n; i++) {
        scanf("%s", &letters[i]);
    }
    letters[n] = '\0';

    word_t *words = malloc(q * sizeof *words);
    for (int i = 0; i < q; i++) {
        scanf("%s%d", words[i].word, &words[i].score);
    }

    int max_value = points(letters, words, q) - 0 + 1;
    int min_value = -max_value;

    char *hand = malloc(n / 2 * sizeof *hand);
    hand[0] = '\0';

    char *opponent_hand = malloc(n / 2 * sizeof *opponent_hand);
    opponent_hand[0] = '\0';

    result_t *result = minimax(letters, hand, opponent_hand, true, min_value, max_value, words, q);
    printf("%c %d-%d", result->best_letter, result->player_score, result->opponent_score);

    free(letters);
    free(words);
    free(hand);
    free(opponent_hand);
    free(result);

    return 0;
}

3. Tests

3.1. Compilation

Compilation avec gcc : 

✅ Compilation sans erreur/warning OK

3.2. Test de Codingame

3.2.1. Test 1 : 4 turns

Input: 

4 4
A S R E
SA 2
SE 4
RE 1
A 1

Expected output: 

S 4-1

Actual output: 

S 4-1

Run test: 

Test 1: 4 turns
✅ Test passed

3.2.2. Test 2 : 2 turns

Input: 

2 2
A B
A 10
B 5

Expected output: 

A 10-5

Actual output: 

A 10-5

Run test: 

Test 2: 2 turns
✅ Test passed

3.2.3. Test 3 : 8 turns

Input: 

8 11
E S R I A C P T
TSAR 20
CARE 18
STEP 15
RICE 14
ACT 12
PIC 11
SEA 8
SIR 6
PA 3
IS 3
AT 1

Expected output: 

S 3-3

Actual output: 

S 3-3

Run test: 

Test 3: 8 turns
✅ Test passed

3.2.4. Test 4 : 16 turns

Input: 

16 73
I T E C G F L R P A S M O D N H
HELIPORT 42
LEOPARDS 41
DECIGRAM 40
PLATFORM 40
HANDSOME 39
REACTION 38
ATHEISM 33
IRELAND 31
INSPECT 31
DIAMOND 30
PALMIER 30
PRIMATE 29
ARTICLE 28
MONSTER 27
FISHER 26
DOLMEN 26
PORTAL 25
FLIGHT 25
PRINCE 24
CASINO 24
CHORAL 23
NECTAR 22
RATION 22
STREAM 21
PLANET 21
GIFTED 20
DETAIL 19
MASTER 18
STORE 18
TIGER 18
CANOE 17
STOLE 17
CLOTH 16
CORPS 16
SEPIA 16
CHILD 15
SINCE 15
PEACH 14
DRONE 14
SLIDE 14
DRAFT 13
MEDIC 13
MAPLE 12
CHAIN 12
AGILE 11
GAME 11
THIS 11
LOFT 10
SING 10
RAID 9
STEP 9
THIN 8
ROLE 7
LIFE 7
HELP 6
MICE 6
GRID 6
EAST 6
EARS 5
SAID 5
INFO 5
LIST 4
LIME 4
LEFT 4
OIL 5
TEA 4
NOT 4
OAF 4
MAD 3
TIC 2
ACT 2
MAP 2
THE 1

Expected output: 

I 29-14

Actual output: 

I 29-14

Run test: 

Test 4: 16 turns
✅ Test passed

3.2.5. Test 5 : 24 turns - 100 words

Input: 

24 100
O A S U W J N F X E M K Y L G C I B R P V H T D
EXPURGATIONS 100
LAWRENCIUMS 99
JUXTAPOSING 98
WORKMANSHIP 97
JOURNALISED 96
DECATHLONS 95
METHODICAL 94
NIGHTCLUBS 93
PLAYGROUND 92
FLYWEIGHTS 91
DISCOURAGE 90
DUPLICATOR 89
HEADSTRONG 88
FLUORIDATE 87
FORMIDABLY 86
IMPORTANCE 85
OLIGARCHS 84
TAXIDERMY 83
SUPREMACY 82
SINGAPORE 81
COMPARING 80
SYMPHONIC 79
STRANGELY 78
MOUNTABLE 77
ROMANTICS 76
JUDGMENTS 75
TRIANGLES 74
PHARYNGES 73
OBSCURITY 72
SLAUGHTER 71
SKEPTICAL 70
PRUDENTLY 69
LIGHTFACE 68
DECLARING 67
ORGANISED 66
PNEUMATIC 65
AUDITORY 64
HOMESPUN 63
PINOCHLE 62
AUCTIONS 61
MONSIEUR 60
SOCIETAL 59
FORENSIC 58
CHARMING 57
PODIATRY 56
BEGONIAS 55
CLARINET 54
BREAKOUT 53
CRAFTING 52
LADYSHIP 51
OBLIGATE 50
SPOILAGE 49
BACHELOR 48
SONGBIRD 47
HORNLIKE 46
CHOLERA 45
GAINFUL 44
ROMAINE 43
CAPTURE 42
MUSTARD 41
DUCTILE 40
HOLIDAY 39
UTOPIAS 38
PRUDENT 37
PROTEIN 36
YOGURTS 35
TSUNAMI 34
GRYPHON 33
BRIEFLY 32
INDULGE 31
THINKS 30
MELODY 29
STIFLE 28
CASKET 27
POLICY 26
MORTAL 25
EPILOG 24
LOCKER 23
GARDEN 22
LOCATE 21
WHITEN 20
VERMIN 19
FOREST 18
PONDER 17
BEYOND 16
DETOUR 15
FILET 14
PRUNE 13
PACER 12
USAGE 11
CRISE 10
BRUIT 9
BUSHY 8
FORAY 7
FLANK 6
PEDAL 5
SKIER 4
FAROE 3
LAGER 2
MODAL 1

Expected output: 

A 5-0

Actual output: 

A 5-0

Run test: 

Test 5: 24 turns - 100 words
✅ Test passed

3.2.6. Résumé global

✅ Test 1 : 4 turns passed
✅ Test 2 : 2 turns passed
✅ Test 3 : 8 turns passed
✅ Test 4 : 16 turns passed
✅ Test 5 : 24 turns - 100 words passed
Passed: 5 (100.0%)
Failed: 0 (0.0%)

Le programme passe tous les tests sauf le test 4e. Cependant la soumission sur Codingame est acceptée.

3.3. Test Valgrind

✅ Valgrind check
==13036== Memcheck, a memory error detector
==13036== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==13036== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info
==13036== Command: ./temp/code
==13036== 
A 5-0==13036== 
==13036== HEAP SUMMARY:
==13036==     in use at exit: 0 bytes in 0 blocks
==13036==   total heap usage: 157,878 allocs, 157,878 frees, 1,644,432 bytes allocated
==13036== 
==13036== All heap blocks were freed -- no leaks are possible
==13036== 
==13036== For lists of detected and suppressed errors, rerun with: -s
==13036== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

4. Solution de la communauté

Solution de Pduhard- : https://www.codingame.com/training/expert/minimax-simple-example/solution?id=10952656 

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

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/

# define MIN 0
# define MAX 1

typedef struct  s_score
{
    int         p1_score;
    int         p2_score;
}               t_score;

t_score find_max_move(char **letters, int p1_letters, int p2_letters,
    int mini, int maxi, int action, char **words, int *words_score, int depth);

void find_firsts(char **letters, int *choice_A, int *choice_B, int used)
{
    int i = 0;

    while (letters[i] && (!(*choice_A) || !(*choice_B)))
    {
        if (!(used & (1 << (letters[i][0] - 'A'))))
        {
            if (!(*choice_A))
                *choice_A = (1 << (letters[i][0] - 'A'));
            else
                *choice_B = (1 << (letters[i][0] - 'A'));
        }
        i++;
    }
}

t_score find_scores(int p1_letters, int p2_letters, char **words, int *words_score)
{
    int i = 0;
    int j = 0;
    int check1;
    int check2;
    t_score scores;

    scores.p1_score = 0;
    scores.p2_score = 0;
    while (words[i])
    {
        check1 = 1;
        check2 = 1;
        j = 0;
        while (words[i][j])
        {
            if (!(p1_letters & (1 << (words[i][j] - 'A'))))
                check1 = 0;
            if (!(p2_letters & (1 << (words[i][j++] - 'A'))))
                check2 = 0;
        }
        if (check1)
            scores.p1_score += words_score[i];
        if (check2)
            scores.p2_score += words_score[i];
        i++;
    }
    return (scores);
}

t_score find_min_move(char **letters, int p1_letters, int p2_letters,
    int mini, int maxi, int action, char **words, int *words_score, int depth)
{
    int     used = p1_letters + p2_letters;
    int     choice_A = 0;
    int     choice_B = 0;
    int     value = 0;
    int     value2 = 0;
    t_score test;
    t_score test2;

    find_firsts(letters, &choice_A, &choice_B, used);
    if (!choice_B)
    {
        p2_letters += choice_A;
        return (find_scores(p1_letters, p2_letters, words, words_score));
    }
    p2_letters += choice_A;
    test = find_max_move(letters, p1_letters, p2_letters
        , mini, maxi, MAX, words, words_score, depth + 1);
    value = test.p1_score - test.p2_score;
    p2_letters -= choice_A;
    if (value <= maxi)
        return (test);
    else if(mini > value)
        mini = value;
    p2_letters += choice_B;
    test2 = find_max_move(letters, p1_letters, p2_letters
        , mini, maxi, MAX, words, words_score, depth + 1);
    value2 = test2.p1_score - test2.p2_score;
    p2_letters -= choice_B;
    if (depth == 1)
        printf("%c", value2 < value ? letters[0][0] : letters[1][0]);
    return (value2 < value ? test2 : test);
}

t_score find_max_move(char **letters, int p1_letters, int p2_letters,
    int mini, int maxi, int action, char **words, int *words_score, int depth)
{
    int     used = p1_letters + p2_letters;
    int     choice_A = 0;
    int     choice_B = 0;
    int     value = 0;
    int     value2 = 0;
    t_score test;
    t_score test2;

    find_firsts(letters, &choice_A, &choice_B, used);
    if (!choice_B)
    {
        p1_letters += choice_A;
        return (find_scores(p1_letters, p2_letters, words, words_score));
    }
    p1_letters += choice_A;
    test = find_min_move(letters, p1_letters, p2_letters
        , mini, maxi, MIN, words, words_score, depth + 1);
    value = test.p1_score - test.p2_score;
    p1_letters -= choice_A;
    if (value >= mini)
        return (test);
    if (maxi < value)
        maxi = value;
    p1_letters += choice_B;
    test2 = find_min_move(letters, p1_letters, p2_letters
        , mini, maxi, MIN, words, words_score, depth + 1);
    value2 = test2.p1_score - test2.p2_score;
    p1_letters -= choice_B;
    if (depth == 1)
        printf("%c", value2 <= value ? letters[0][0] : letters[1][0]);
    return (value2 <= value ? test : test2);
}

int main()
{
    int     n;
    int     q;
    char    **letters;
    int     *scores;
    char    **words;
    int     maxi = -21000000;
    int     mini = 21000000;
    t_score scor;

    scanf("%d%d", &n, &q);
    letters = malloc(sizeof(char *) * (n + 1));
    scores = malloc(sizeof(int) * q);
    words = malloc(sizeof(char *) * (q + 1));
    for (int i = 0; i < n; i++) {
        char letter[2];
        scanf("%s", letter);
        letters[i] = strdup(letter);
    }
    letters[n] = NULL;
    for (int i = 0; i < q; i++) {
        char word[11];
        int score;
        scanf("%s%d", word, &score);
        words[i] = strdup(word);
        scores[i] = score;
    }
    words[q] = NULL;
    scor = find_max_move(letters, 0, 0, mini, maxi, MAX, words, scores, 1);

    printf(" %d-%d\n", scor.p1_score, scor.p2_score);

    return 0;
}

J’ai choisi cette solution car elle est différente de ma solution. Elle ne retourne pas la lettre à jouer dans les appels récursifs mais elle retourne le score seul, il faut donc créer une fonction qui va chercher la lettre à jouer. On note remarque que la fonction minimax est séparée en deux fonctions, une pour le joueur 1 et une pour le joueur 2. Cela permet de simplifier le code et de le rendre plus lisible.

Lors de cet exercice, j’ai mis en application les connaissances acquises sur l’algorithme minimax et l’algorithme alpha-beta. J’ai pu voir que ces algorithmes sont très efficaces et permettent de résoudre des problèmes complexes en un temps raisonnable. De plus, j’ai pu mettre en pratique mes connaissances en programmation récursive.

Retour vers ma page Web personnelle

Crédits :

Date: 2023-04-03

Auteur: Jules Girard

Created: 2023-04-26 mer. 19:28