Rapport : Minimax exercise

Table des matières

1. Introduction

1.1. Principe de focntionnment

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

L’objectif de ce challenge est de choisir le meilleur coup à jouer pour un joueur donné dans un jeu de quelconque à deux joueurs et à somme nulle. Pour cela, on utilise l’algorithme minimax avec de l’élagage alpha-beta. Pour chaque coup possible, on calcule le meilleur score garanti. Pour cela, quand c’est au tour de l’adversaire de jouer, on prend le pire score possible (le minimum, l’adversaire joue sont meilleur coup, le pire pour nous) et quand c’est au tour de notre joueur de jouer, on prend le meilleur score possible (le maximum, on joue notre meilleur coup).

1.2. Données fournies

On reçoit en entrée deux entiers ’D’ et ’B’ qui représentent respectivement la profondeur maximale de l’arbre et le nombre de branches par nœud (le nombre de coups possibles à chaque tour). On reçoit ensuite une liste de ’BD’ entiers qui représentent les scores de chaque feuille de l’arbre.

1.3. Données à fournir

On doit fournir un entier qui représente le score garanti pour notre joueur. On doit également fournir le nombre de nœuds explorés par l’algorithme.

1.4. Contraintes

  • 0 < D < 15 (profondeur maximale de l’arbre)
  • 0 < B < 15 (nombre de branches par nœud)
  • -1000 < score < 1000 (score d’une feuille)

2. Méthode de résolution

Le principe de résolution est le suivant :

On récupère les scores de chaque feuille de l’arbre, on les stocke dans un tableau. Le tableau représente les feuilles de l’arbre. On parcourt l’arbre en profondeur en partant de la racine. Pour chaque nœud, on calcule le meilleur score garanti pour notre joueur en utilisant les scores des feuilles de ses fils. Si c’est au tour de l’adversaire de jouer, on prend le pire score possible (le minimum, l’adversaire joue sont meilleur coup, le pire pour nous) et quand c’est au tour de notre joueur de jouer, on prend le meilleur score possible (le maximum, on joue notre meilleur coup). On fait cela jusqu’à ce qu’on arrive à la profondeur maximale de l’arbre. On retourne alors le meilleur score garanti pour notre joueur.

Détails technique : J’ai choisi de stocker les scores des feuilles dans un tableau et de ne pas utiliser de structure de données pour augmenter la vitesse de l’algorithme. Cependant cela rend le code moins lisible puisqu’il faut faire des calculs pour retrouver l’index d’une feuille dans le tableau et passer à la fonction récursive les bons paramètres (index de la feuille, profondeur actuelle, profondeur maximale).

2.1. Code

On commence par définir des variables de pré-processeur qui correspondent aux valeurs minimales et maximales possibles pour un score. 

#define MIN_VALUE (-1000) ///< Valeur minimale possible.
#define MAX_VALUE 1000 ///< Valeur maximale possible.

On définit ensuite une fonction qui permet de parser une chaîne de caractères en un tableau d’entiers. 

/**
 * \brief Convertit une chaîne de caractères en un tableau d'entiers.
 * \param str Chaîne de caractères à convertir.
 * \param n Nombre d'éléments à extraire de la chaîne.
 * \return Pointeur vers le tableau d'entiers extrait.
 */
int *parse_string(char *str, int n) {
    int *result = malloc(n * sizeof *result);
    char *token;
    int i;

    token = strtok(str, " ");
    for (i = 0; i < n; i++) {
        result[i] = atoi(token);
        token = strtok(NULL, " ");
    }
    return result;
}

On définit ensuite une fonction qui permet de calculer le meilleur score garanti pour notre joueur. La fonction prend en paramètres :

  • la profondeur actuelle
  • l’index du nœud actuel
  • un booléen qui indique si c’est au tour de notre joueur de jouer
  • le tableau des scores des feuilles
  • alpha
  • beta

(…)

On commence par incrémenter le nombre de nœuds explorés. Si c’est au tour de notre joueur de jouer, on prend le maximum des scores garantis pour chaque coup possible. Si c’est au tour de l’adversaire de jouer, on prend le minimum des scores garantis pour chaque coup possible. 

/**
 * \brief Implémente l'algorithme Minimax avec élagage Alpha-Beta.
 * \param depth Profondeur actuelle de l'arbre de recherche.
 * \param node_index Indice du noeud actuel dans l'arbre.
 * \param maximizing_player Booléen indiquant si le joueur actuel maximise (true) ou minimise (false).
 * \param values Tableau des valeurs des feuilles de l'arbre.
 * \param alpha Valeur alpha de l'élagage Alpha-Beta.
 * \param beta Valeur beta de l'élagage Alpha-Beta.
 * \param max_depth Profondeur maximale de l'arbre.
 * \param branching_factor Facteur de branchement de l'arbre (nombre de coups possibles à chaque tour).
 * \param nodes_visited Pointeur vers un entier qui compte le nombre de noeuds visités.
 * \return Le meilleur score garanti pour le joueur actuel.
 */
int minimax(int depth, int node_index, bool maximizing_player, int values[], int alpha, int beta, int max_depth,
            int branching_factor, int *nodes_visited) {
    (*nodes_visited)++;

    if (depth == max_depth) {
        return values[node_index];
    }

    int value, i;
    if (maximizing_player) {
        int best_value = MIN_VALUE;
        for (i = 0; i < branching_factor; i++) {
            value = minimax(depth + 1, node_index * branching_factor + i, false, values, alpha, beta, max_depth,
                            branching_factor, nodes_visited);
            best_value = value > best_value ? value : best_value;
            alpha = value > alpha ? value : alpha;
            if (beta <= alpha) {
                break;
            }
        }
        return best_value;
    } else {
        int best_value = MAX_VALUE;
        for (i = 0; i < branching_factor; i++) {
            value = minimax(depth + 1, node_index * branching_factor + i, true, values, alpha, beta, max_depth,
                            branching_factor, nodes_visited);
            best_value = value < best_value ? value : best_value;
            beta = value < beta ? value : beta;
            if (beta <= alpha) {
                break;
            }
        }
        return best_value;
    }
}

On définit enfin la fonction principale qui lit les données en entrée, appelle la fonction minimax et affiche le résultat. 

/**
 * \brief Fonction principale du programme.
 * \return Le code de retour du programme.
 */
int main() {
    int depth; // B
    int branching_factor; // D
    scanf("%d%d", &depth, &branching_factor); // B^D
    fgetc(stdin);
    int n = (int) pow(branching_factor, depth);

    char LEAFS[40001];
    scanf("%[^\n]", LEAFS);
    int *leafs = parse_string(LEAFS, n);

    int nodes_visited = 0;
    int best_score = minimax(0, 0, true, leafs, MIN_VALUE, MAX_VALUE, depth, branching_factor, &nodes_visited);
    printf("%d %d", best_score, nodes_visited);

    free(leafs);
    return 0;
}

2.2. Implémentation complète

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

#define MIN_VALUE (-1000) ///< Valeur minimale possible.
#define MAX_VALUE 1000 ///< Valeur maximale possible.

/**
 * \brief Convertit une chaîne de caractères en un tableau d'entiers.
 * \param str Chaîne de caractères à convertir.
 * \param n Nombre d'éléments à extraire de la chaîne.
 * \return Pointeur vers le tableau d'entiers extrait.
 */
int *parse_string(char *str, int n) {
    int *result = malloc(n * sizeof *result);
    char *token;
    int i;

    token = strtok(str, " ");
    for (i = 0; i < n; i++) {
        result[i] = atoi(token);
        token = strtok(NULL, " ");
    }
    return result;
}

/**
 * \brief Implémente l'algorithme Minimax avec élagage Alpha-Beta.
 * \param depth Profondeur actuelle de l'arbre de recherche.
 * \param node_index Indice du noeud actuel dans l'arbre.
 * \param maximizing_player Booléen indiquant si le joueur actuel maximise (true) ou minimise (false).
 * \param values Tableau des valeurs des feuilles de l'arbre.
 * \param alpha Valeur alpha de l'élagage Alpha-Beta.
 * \param beta Valeur beta de l'élagage Alpha-Beta.
 * \param max_depth Profondeur maximale de l'arbre.
 * \param branching_factor Facteur de branchement de l'arbre (nombre de coups possibles à chaque tour).
 * \param nodes_visited Pointeur vers un entier qui compte le nombre de noeuds visités.
 * \return Le meilleur score garanti pour le joueur actuel.
 */
int minimax(int depth, int node_index, bool maximizing_player, int values[], int alpha, int beta, int max_depth,
            int branching_factor, int *nodes_visited) {
    (*nodes_visited)++;

    if (depth == max_depth) {
        return values[node_index];
    }

    int value, i;
    if (maximizing_player) {
        int best_value = MIN_VALUE;
        for (i = 0; i < branching_factor; i++) {
            value = minimax(depth + 1, node_index * branching_factor + i, false, values, alpha, beta, max_depth,
                            branching_factor, nodes_visited);
            best_value = value > best_value ? value : best_value;
            alpha = value > alpha ? value : alpha;
            if (beta <= alpha) {
                break;
            }
        }
        return best_value;
    } else {
        int best_value = MAX_VALUE;
        for (i = 0; i < branching_factor; i++) {
            value = minimax(depth + 1, node_index * branching_factor + i, true, values, alpha, beta, max_depth,
                            branching_factor, nodes_visited);
            best_value = value < best_value ? value : best_value;
            beta = value < beta ? value : beta;
            if (beta <= alpha) {
                break;
            }
        }
        return best_value;
    }
}

/**
 * \brief Fonction principale du programme.
 * \return Le code de retour du programme.
 */
int main() {
    int depth; // B
    int branching_factor; // D
    scanf("%d%d", &depth, &branching_factor); // B^D
    fgetc(stdin);
    int n = (int) pow(branching_factor, depth);

    char LEAFS[40001];
    scanf("%[^\n]", LEAFS);
    int *leafs = parse_string(LEAFS, n);

    int nodes_visited = 0;
    int best_score = minimax(0, 0, true, leafs, MIN_VALUE, MAX_VALUE, depth, branching_factor, &nodes_visited);
    printf("%d %d", best_score, nodes_visited);

    free(leafs);
    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 : Depth 1 game

Input: 

1 4
2 -1 3 0

Expected output: 

3 5

Actual output: 

3 5

Run test: 

Test 1: Depth 1 game
✅ Test passed

3.2.2. Test 2 : Depth 2, no cutoffs

Input: 

2 2
1 2 3 4

Expected output: 

3 7

Actual output: 

3 7

Run test: 

Test 2: Depth 2, no cutoffs
✅ Test passed

3.2.3. Test 3 : Depth 2, cutoffs

Input: 

2 2
1 2 0 4

Expected output: 

1 6

Actual output: 

1 6

Run test: 

Test 3: Depth 2, cutoffs
✅ Test passed

3.2.4. Test 4 : Small game

Input: 

3 2
-1 0 2 666 -3 -2 666 666

Expected output: 

0 11

Actual output: 

0 11

Run test: 

Test 4: Small game
✅ Test passed

3.2.5. Test 5 : Slightly deeper game

Input: 

5 2
-821 -318 46 -870 -595 -56 -817 -170 -464 1 -212 67 -83 -233 -263 83 -890 -713 -141 -320 -676 93 -794 -175 -322 -481 -916 -761 91 37 -464 -194

Expected output: 

-170 37

Actual output: 

-170 37

Run test: 

Test 5: Slightly deeper game
✅ Test passed

3.2.6. Test 6 : Random game, deep but narrow

Input: 

11 2
19 10 83 29 64 46 79 72 63 41 10 80 51 24 1 36 27 19 -4 20 59 3 53 86 33 60 82 61 3 41 39 59 -2 6 74 85 12 95 68 60 -2 77 -4 44 -9 31 63 90 16 29 13 55 28 98 83 32 -4 27 9 -3 10 66 24 72 -1 55 79 48 87 35 48 19 3 -8 27 30 83 99 94 35 20 57 55 25 57 93 19 85 53 82 99 73 21 69 73 46 49 18 18 91 68 83 99 50 11 13 5 10 44 -2 94 85 69 -6 51 79 34 45 39 77 64 48 61 90 99 32 62 36 3 52 17 89 73 66 22 13 4 86 23 -9 18 23 65 36 10 8 93 68 22 12 12 66 65 37 31 41 54 81 18 25 49 10 94 35 42 -5 55 26 7 -6 27 90 40 70 90 28 34 22 57 60 -7 2 84 -5 26 44 57 36 15 47 47 51 60 64 35 18 61 53 19 85 21 26 29 31 8 65 54 65 68 15 94 30 56 84 88 45 74 37 63 45 12 58 74 42 -7 49 49 93 93 79 77 6 17 5 64 66 75 32 28 65 63 85 68 0 60 61 37 48 44 37 3 69 80 28 63 56 60 18 -3 40 80 44 42 5 56 84 35 43 62 11 24 98 93 48 28 86 78 -3 37 44 36 36 -5 55 -8 43 53 53 55 37 2 61 42 9 13 1 -1 -1 20 98 65 50 72 -8 88 64 -2 55 93 46 60 74 61 85 26 93 57 21 0 95 52 86 81 -8 22 55 89 5 99 98 89 17 58 -7 93 -3 30 85 23 10 24 46 67 36 91 24 32 6 9 41 65 82 48 85 37 84 80 26 3 -6 81 60 47 37 23 77 85 11 49 5 19 1 8 52 69 -8 88 81 12 75 3 -3 88 55 21 18 10 34 23 49 80 14 61 6 19 93 45 84 -6 49 1 29 90 65 -8 84 -1 26 40 81 68 57 28 6 19 41 13 16 64 68 39 40 -1 61 34 22 28 37 87 47 58 13 -5 39 75 69 36 4 94 95 27 55 20 11 27 95 27 0 95 15 41 19 29 63 91 25 40 96 39 3 80 94 0 -4 27 51 71 66 45 59 47 95 13 98 53 15 63 62 18 18 62 39 37 26 12 8 15 43 93 -5 96 37 82 18 38 81 95 51 74 64 34 81 58 61 68 15 95 70 37 83 -6 59 51 28 43 12 40 75 4 -2 28 74 32 50 6 58 72 48 77 -3 19 -7 90 51 69 95 53 88 89 53 96 95 73 27 51 -7 83 89 60 46 -2 95 26 -5 81 -2 83 45 20 61 61 42 17 12 78 3 47 71 53 95 3 -4 28 -4 31 27 54 12 60 55 38 96 58 1 -7 42 8 60 99 69 -5 42 85 11 20 80 28 37 -6 40 -9 -9 90 52 52 88 86 59 23 44 70 55 63 44 83 14 92 45 33 82 86 24 54 87 25 26 97 6 15 5 1 12 58 92 52 70 71 4 16 72 -6 16 2 -4 21 98 94 89 20 20 91 39 73 94 49 35 48 78 -3 0 68 4 18 71 53 38 3 78 44 1 74 51 22 45 66 49 34 23 67 98 72 -6 25 80 82 49 32 6 33 95 28 88 19 74 76 86 19 -5 66 92 45 36 20 68 17 1 4 58 60 -4 -1 40 66 -9 88 -7 65 96 26 -9 82 31 31 52 60 55 3 -1 55 -8 84 -5 70 73 59 93 22 83 83 83 32 50 3 18 33 24 52 49 93 36 98 26 53 72 51 -8 61 0 -4 62 93 85 33 49 30 -7 42 16 11 73 76 27 85 51 27 73 5 37 84 34 44 34 91 58 29 -4 76 95 62 55 22 98 56 67 1 37 14 91 98 16 6 58 39 99 -2 12 43 75 15 45 21 0 -8 27 2 -1 80 50 16 59 -3 17 12 15 63 59 68 -9 59 60 96 -4 7 44 3 56 4 52 16 30 -8 2 -6 5 66 -5 40 64 44 47 40 84 50 3 27 46 26 99 94 15 68 99 95 79 17 4 4 28 79 43 -1 75 50 57 6 79 98 36 46 65 30 23 19 71 48 61 8 52 62 20 75 -1 90 92 40 55 -9 63 98 43 80 2 31 13 72 58 44 -1 28 27 86 5 54 88 11 83 74 95 78 40 76 8 5 75 6 -8 72 57 48 96 78 93 78 -4 44 8 93 99 23 10 69 63 90 -9 46 1 0 74 68 88 -1 35 60 60 15 15 -2 78 63 44 49 0 61 18 52 72 17 7 41 73 14 27 27 59 48 19 15 54 93 51 77 96 33 47 71 78 71 89 24 -1 -9 3 57 95 72 59 85 50 80 58 33 99 48 -7 2 74 84 89 -4 -6 55 23 54 34 -4 31 47 97 67 74 79 7 -9 51 20 74 25 68 73 96 -9 -2 44 19 62 44 79 50 15 58 -9 15 51 77 45 87 75 14 37 91 26 62 82 48 96 93 78 22 56 65 95 65 52 40 85 82 41 15 92 86 77 6 90 43 89 89 -7 9 59 12 88 60 42 30 25 73 32 61 95 94 11 -9 37 92 46 67 52 61 76 53 54 73 92 -3 23 51 30 69 18 70 58 42 41 54 49 11 11 77 60 11 99 15 2 81 32 84 17 44 26 69 10 11 -6 98 0 98 31 91 4 72 82 63 65 4 38 29 26 16 55 78 62 47 28 37 7 81 88 85 94 56 51 78 73 40 56 32 19 83 33 32 71 97 80 66 81 61 72 98 71 68 58 84 54 91 39 92 72 83 25 16 25 55 45 29 44 75 84 20 29 49 58 59 -1 56 59 12 68 62 53 43 67 13 39 18 -7 88 2 21 91 -8 48 83 41 54 62 96 47 71 32 61 3 81 84 63 27 28 50 -1 23 9 31 10 13 31 63 23 83 84 62 -4 38 25 -2 44 65 78 82 4 83 68 79 76 83 72 49 84 81 32 72 24 69 90 20 52 48 12 75 49 92 81 23 46 50 10 33 -2 42 67 12 64 86 43 78 -2 19 28 2 79 52 12 -8 83 8 30 73 4 10 93 67 73 54 -7 5 80 4 45 18 26 24 92 33 75 21 69 24 55 6 87 6 12 51 8 71 -3 57 25 42 97 6 29 23 69 -6 -5 84 96 43 31 72 99 73 67 14 92 91 19 78 94 29 42 0 2 17 83 77 -8 26 90 22 4 77 60 47 45 19 -9 80 81 38 43 10 60 15 87 19 79 61 40 0 23 11 23 16 90 1 3 1 12 87 10 30 90 56 -6 49 55 72 64 33 18 90 27 -4 88 33 71 50 81 77 36 45 30 80 4 29 43 30 70 35 92 -7 82 60 38 69 86 -1 37 14 11 90 76 4 29 53 71 98 92 23 85 68 96 -7 -5 22 7 83 71 83 99 73 15 28 64 -9 68 86 67 29 14 38 9 16 91 37 -8 68 2 57 9 20 83 65 96 22 93 -1 73 74 70 95 4 22 44 39 97 27 42 51 29 36 61 -6 19 82 55 1 41 64 72 38 33 77 70 70 95 72 -4 2 10 84 35 14 94 36 90 -9 0 12 5 16 17 60 83 79 44 18 60 57 97 84 12 18 98 74 41 70 86 55 62 10 7 54 12 25 66 59 49 -9 67 9 70 30 61 30 99 67 49 55 20 -6 21 1 94 18 16 76 94 73 44 47 53 83 78 39 -6 7 -7 55 6 45 62 85 93 22 15 86 56 63 98 95 55 26 52 55 61 83 44 17 81 69 22 99 73 82 -7 67 96 57 6 61 62 37 31 6 61 55 35 10 98 82 36 53 29 50 95 58 53 54 72 47 43 66 83 9 29 20 99 4 20 80 55 16 17 -9 76 27 12 31 -5 23 70 58 92 76 48 -1 27 54 56 72 79 86 -6 74 33 55 83 -4 -3 48 69 22 53 -1 64 22 88 66 58 61 33 75 95 84 85 71 44 1 -1 17 33 24 24 34 82 50 73 44 93 -6 -6 17 -5 68 1 97 60 99 81 81 57 18 22 38 53 81 92 62 66 26 61 47 57 19 44 97 64 97 11 68 86 64 89 23 75 29 -4 35 96 49 85 11 77 59 8 88 -9 6 1 -1 14 55 78 57 78 99 53 45 34 74 78 63 70 32 82 -7 11 -9 78 98 9 45 97 41 35 30 90 14 50 72 34 63 3 35 -2 -5 34 29 55 83 90 53 73 87 15 -8 88 -2 3 94 47 99 81 17 23 71 62 8 94 49 72 6 -9 23 44 60 39 60 54 -4 24 2 40 9 26 3 83 39 18 -1 31 38 81 63 39 -5 70 99 80 6 -8 -1 82 48 15 87 85 25 4 57 54 49 86 92 98 63 77 42 50 45 44 74 2 95 72 6 85 12 71 38 80 36 27 50 21 86 87 11 80 69 71 58 5 97 99 65 62 38 -1 82 89 86 0 25 37 52 19 12 88 63 72 74 89 72 84 38 26 98 -6 13 99 25 92 62 53 20 32 76 44 43 89 97 47 19 69 28 30 78 16 73 67 13 40 28 -9 86 56 2 16 25 92 25 -2 78 6 58 93 -9 -5 33 -9 99 1 30 3 -1 93 -7 12 40 16 66 18 35 -9 77 34 45 41 77 23 63 15 69 48 20 93 56 89 65 51 99 41 76 39 14 2 97 91 71 88 56 0 61 14 53 16 0 94 40 64 72 72 40 53 49 35 37 97 63 -2 75 33 55 87 10 48 52 71 36 88 87 31 48 42 11 92 32 74 75 13 26 85 11 59 75 68

Expected output: 

59 1510

Actual output: 

59 1510

Run test: 

Test 6: Random game, deep but narrow
✅ Test passed

3.2.7. Test 7 : Another large random game

Input: 

5 5
30 41 95 -7 11 28 53 47 62 81 10 73 63 -3 34 55 95 68 89 -4 16 95 28 92 41 5 49 43 19 25 28 42 52 19 90 60 3 0 -6 30 32 35 84 10 27 48 95 61 79 58 21 28 5 -9 92 4 83 94 21 83 66 91 31 90 67 86 39 1 2 0 67 34 -1 2 37 43 -1 94 -2 33 80 42 3 26 50 39 91 12 -1 56 87 46 67 46 45 75 45 2 61 90 4 40 -6 13 25 85 6 8 29 30 12 60 -9 37 5 34 41 25 45 94 51 -4 -9 0 81 17 54 92 66 -5 10 31 -8 81 15 83 19 36 10 34 5 77 41 12 31 15 69 -3 19 10 13 67 -4 69 39 81 49 27 82 58 8 22 11 82 13 36 90 72 -3 71 9 10 83 30 29 44 22 88 63 26 49 -8 20 88 83 -2 12 98 24 -6 22 59 49 72 1 13 42 72 47 -4 25 6 84 97 76 80 51 21 55 25 59 -6 90 13 26 3 99 -2 50 28 66 88 72 68 98 9 20 85 8 84 70 38 13 36 39 96 26 44 -4 44 8 97 2 21 35 20 48 4 32 86 11 58 43 64 17 78 -3 58 10 57 50 -5 19 53 54 35 47 72 4 13 95 58 3 54 27 53 84 -8 46 28 37 75 96 16 63 12 -6 60 -8 69 93 49 94 82 61 46 29 77 -9 36 2 44 46 2 34 52 21 82 9 -7 17 10 54 28 16 47 12 66 11 2 41 32 21 93 27 -5 12 27 26 94 -7 25 60 58 1 8 50 0 26 56 35 76 27 42 8 31 43 77 60 21 82 75 81 8 -1 8 20 -6 28 33 -4 15 -4 94 24 86 32 76 59 31 13 1 40 88 46 -9 53 2 93 45 77 -2 62 86 2 67 0 90 13 24 35 91 86 87 65 79 -6 50 67 83 95 86 36 22 -4 28 -6 2 -9 65 90 21 21 15 -9 23 97 12 79 4 77 36 70 31 68 57 2 43 24 29 61 48 80 47 29 53 50 28 89 98 5 39 43 2 17 82 67 29 51 2 85 73 77 63 29 27 22 89 16 25 69 5 85 86 77 11 28 67 62 1 96 91 99 80 -8 85 63 94 50 16 28 14 38 21 34 79 11 23 72 5 87 92 35 66 9 26 49 12 79 98 83 66 -9 86 14 66 24 15 62 19 49 59 41 -5 91 67 63 40 89 92 19 92 7 77 61 -6 4 88 48 -1 42 62 68 26 49 58 25 51 55 44 11 -6 83 15 24 24 47 30 70 51 12 36 65 26 53 86 -7 51 91 38 61 31 -7 14 20 60 25 18 67 0 19 76 25 42 84 19 44 84 68 34 78 36 85 1 49 11 93 31 55 51 36 23 40 86 43 8 82 35 93 1 40 15 13 29 84 99 74 82 91 48 98 52 76 17 73 43 -7 -8 74 -3 19 51 47 57 2 77 7 41 99 18 37 14 30 29 95 50 89 27 70 4 30 48 12 51 61 33 29 89 -7 0 79 43 52 24 26 -8 94 20 32 98 72 27 8 -8 97 72 36 28 4 67 9 62 -8 61 16 2 8 43 29 52 86 83 -9 31 10 89 7 37 95 74 65 0 48 -6 99 84 73 31 51 -2 91 -4 39 86 20 40 54 20 47 11 57 80 53 22 41 81 33 3 -6 79 41 13 36 83 30 8 39 51 23 17 86 62 83 64 64 59 64 87 51 46 13 -9 95 98 43 1 47 89 87 13 -4 93 -6 22 30 48 51 55 76 4 40 -6 93 48 68 62 -3 0 66 32 92 96 -6 89 35 23 95 6 91 20 13 22 10 79 38 18 32 28 29 91 92 67 38 70 91 64 28 2 -9 39 40 83 50 52 23 8 21 6 63 25 72 44 25 32 11 82 49 13 -5 16 15 60 4 -5 11 20 94 58 75 56 71 53 -9 91 87 96 7 3 26 41 84 60 70 84 56 4 26 99 1 48 92 19 20 -7 88 96 98 -6 14 -2 53 44 93 74 43 91 60 78 77 33 64 83 8 59 18 94 50 62 50 51 41 21 67 88 3 80 38 81 45 74 99 22 46 50 28 82 12 51 11 55 31 98 5 95 74 68 73 35 87 26 90 63 26 -7 51 93 29 93 15 72 53 16 47 -7 1 33 -2 89 74 28 28 3 26 37 10 10 23 81 15 41 8 25 23 58 -2 35 64 42 38 5 61 51 63 5 27 65 67 14 91 -7 90 11 92 14 56 63 13 15 32 -5 79 30 32 98 54 8 79 69 80 5 7 42 98 -1 41 95 83 52 1 64 71 7 37 21 63 84 33 8 99 29 28 42 34 40 -6 58 75 81 23 67 16 -8 58 65 38 60 83 72 46 28 26 29 7 23 43 28 25 77 93 61 62 75 26 8 72 37 61 29 94 35 16 39 20 98 61 82 92 56 20 64 42 79 80 5 95 85 14 94 73 61 10 51 55 4 57 68 5 28 71 57 -3 35 79 85 8 82 59 78 11 11 54 79 31 68 86 1 8 14 8 -4 36 50 69 22 5 74 -5 -8 63 13 89 88 6 4 94 27 16 52 8 92 86 -1 91 43 29 73 85 -6 57 80 61 98 10 84 0 62 -1 96 75 18 1 30 36 77 64 72 56 30 71 50 89 -4 48 -8 -4 19 83 46 61 86 84 82 60 99 79 88 66 -1 22 76 55 79 99 9 97 60 29 33 2 1 47 68 12 59 11 14 61 32 47 20 88 96 32 92 -5 9 1 69 68 94 65 59 14 51 33 6 68 20 92 81 17 84 70 6 31 98 0 40 20 -7 29 40 60 94 39 55 3 16 5 18 3 82 80 88 -5 5 41 69 16 52 92 19 11 56 62 14 45 39 8 13 48 40 6 96 41 88 80 20 67 58 28 35 33 59 46 70 42 86 94 58 41 83 -4 51 45 35 67 16 96 50 35 58 38 -1 15 15 64 68 5 49 94 48 24 -9 36 88 21 17 42 -2 83 74 82 10 86 35 39 86 33 46 51 -7 60 81 94 18 -7 -4 1 67 -4 12 70 87 53 38 33 0 16 66 29 -9 -8 -5 63 -7 6 36 63 52 75 47 80 -2 14 92 91 89 -1 54 43 -9 51 25 45 41 87 91 65 57 99 71 3 66 12 69 83 81 90 -5 98 59 -9 24 2 -3 95 24 91 32 26 84 34 92 58 28 85 56 5 37 33 73 15 -7 60 16 3 45 -4 11 14 42 67 98 98 78 68 63 11 99 53 69 29 62 -9 32 1 75 20 36 39 59 6 12 13 65 79 21 73 51 22 94 49 27 53 38 4 53 74 66 55 -4 64 -9 86 42 46 56 83 43 75 -5 33 91 93 75 19 2 49 61 43 27 38 55 65 98 33 12 27 6 -2 -6 45 -4 64 10 29 77 21 4 -3 62 64 7 83 63 68 32 41 14 21 34 99 84 59 -2 57 63 72 88 57 9 74 92 1 91 83 50 17 -1 23 18 26 80 73 83 0 24 59 5 15 92 26 44 78 69 56 46 58 -2 38 1 87 48 84 96 36 -1 -5 87 27 4 51 88 94 31 85 44 41 19 44 17 57 64 29 8 13 66 60 55 3 35 -4 16 60 77 67 58 64 78 -1 48 68 33 72 48 98 28 22 16 77 93 -8 19 27 -2 17 64 44 84 13 46 21 62 -3 49 64 25 45 6 45 76 -4 58 88 37 36 89 36 52 86 13 69 60 69 26 2 -5 48 69 -1 34 47 15 25 64 77 38 44 19 81 58 8 75 93 84 40 40 88 57 2 61 73 2 91 80 26 76 11 14 72 70 89 38 22 88 -8 83 5 29 60 52 43 73 88 26 47 64 52 86 20 97 50 54 51 73 82 2 77 47 48 59 36 33 76 12 95 24 67 28 96 71 4 60 41 33 28 8 29 54 95 48 14 88 -3 -4 74 24 48 69 79 79 24 80 92 -5 27 80 9 60 24 -9 -8 76 27 -5 22 92 10 63 63 61 12 38 67 64 61 45 -7 95 -4 33 95 83 82 42 80 65 36 53 44 0 -3 81 45 30 15 44 90 6 15 22 66 1 43 96 12 -8 -1 97 -4 -8 65 89 28 24 30 79 71 96 73 98 78 95 95 0 22 42 10 34 71 67 -1 14 73 31 89 73 85 77 30 96 47 95 1 13 19 72 -5 -4 -7 57 2 1 77 18 74 53 23 -4 28 29 43 -9 91 8 92 80 30 67 69 7 81 59 29 96 18 19 83 98 11 48 51 54 6 37 49 88 57 58 66 61 60 46 33 98 3 35 30 46 -3 -9 34 12 24 90 19 73 13 17 4 14 12 72 87 36 71 63 13 33 7 74 4 92 23 26 51 17 25 16 56 41 77 48 48 44 15 98 23 78 39 78 67 92 24 32 18 88 83 16 58 36 52 55 58 74 67 28 1 99 61 23 26 15 76 17 7 47 4 -9 1 53 94 48 55 90 40 54 -3 56 28 99 25 96 78 -5 11 49 96 -4 55 41 17 89 40 28 41 85 14 93 35 15 20 76 53 5 39 33 56 63 58 64 20 7 41 79 43 -5 63 38 -8 -1 95 93 -7 -7 12 65 98 23 12 90 70 0 33 36 67 70 17 94 0 83 70 73 15 76 83 48 55 64 3 5 75 74 33 13 56 68 11 53 43 32 73 33 40 74 35 6 10 26 10 44 -6 42 16 39 30 78 75 16 77 -7 35 40 6 87 73 97 0 4 33 48 73 73 12 57 70 14 67 74 69 -1 -7 1 51 80 42 21 67 6 43 51 90 -4 95 70 -5 6 55 48 81 3 63 89 30 24 95 67 9 13 3 0 47 -9 34 12 55 27 70 25 55 -5 14 71 10 51 98 12 88 93 41 76 2 81 22 65 59 4 6 85 -9 48 52 8 22 44 18 51 94 95 69 85 54 90 18 47 11 42 -6 77 20 37 95 46 -3 92 84 52 3 46 20 18 44 57 32 78 57 67 65 62 96 27 23 15 99 86 39 95 77 64 11 34 63 52 2 23 51 30 40 27 6 79 64 0 27 30 43 83 75 66 61 -3 40 97 41 18 11 27 84 96 -7 43 61 77 36 -3 3 5 31 31 47 98 4 69 58 92 25 31 89 98 66 70 84 88 82 12 96 94 41 18 11 18 97 32 46 88 31 68 -1 97 22 15 26 25 78 10 2 88 94 28 93 35 87 75 69 23 44 35 84 -5 61 53 99 62 59 16 63 -9 40 21 83 51 58 14 20 49 74 29 79 80 61 5 42 61 5 13 31 55 41 11 26 28 87 17 53 2 93 71 23 81 20 83 17 71 50 53 87 39 -5 21 15 46 42 20 64 99 30 -6 4 18 24 32 59 93 70 66 -1 2 85 79 44 15 8 77 42 -9 54 8 95 61 -5 5 18 56 15 93 58 20 52 31 98 11 12 37 26 51 55 -8 20 6 38 34 34 73 82 26 8 64 11 -1 34 19 79 -7 44 31 18 74 90 77 66 33 8 97 92 76 35 74 62 58 70 14 90 50 74 42 80 39 35 32 65 83 -8 92 72 79 75 27 94 7 96 79 93 62 28 -7 41 82 56 63 24 76 35 7 4 43 21 54 98 86 30 47 0 4 23 48 56 25 72 7 54 92 -5 61 87 90 65 49 -2 79 3 -4 -3 30 77 61 70 80 28 29 23 10 49 40 52 50 4 56 55 78 71 -2 30 7 73 44 16 56 43 49 47 41 -4 47 86 51 19 26 49 93 74 52 97 46 -3 57 83 96 29 27 1 95 57 -8 -2 1 61 85 26 95 38 3 48 38 60 36 53 22 23 59 86 13 -9 35 91 6 9 45 13 88 2 46 32 94 23 94 46 95 9 76 47 69 60 76 73 -8 15 44 52 73 93 62 89 96 71 82 75 1 25 19 33 70 29 73 3 9 44 45 64 46 89 92 35 19 33 23 8 42 5 31 57 78 72 -1 35 83 99 93 -5 -4 71 54 98 54 85 3 57 11 66 39 96 98 12 41 55 36 86 30 32 23 81 17 43 67 86 94 47 84 61 61 86 21 63 73 63 -1 85 29 27 77 50 14 11 78 33 52 34 24 55 70 45 -3 15 13 28 89 52 81 15 17 39 92 27 3 89 76 5 6 13 82 61 22 36 90 15 15 23 47 39 69 78 53 4 32 57 75 72 45 61 8 72 67 70 16 0 -8 85 -4 79 87 30 37 81 65 57 6 97 -7 94 26 65 29 36 8 31 15 61 19 8 85 24 47 86 -3 30 54 92 91 66 9 21 74 -3 30 6 -1 63 89 32 91 13 23 22 67 52 15 89 87 83 76 18 44 90 18 38 13 84 27 94 94 94 1 97 67 27 66 16 41 96 34 89 63 18 19 33 43 36 71 16 35 60 57 97 98 93 85 41 10 63 42 57 -1 -8 37 32 27 52 83 53 57 16 30 24 87 10 19 11 86 56 12 75 78 19 54 75 16 57 34 81 61 65 5 8 72 87 8 10 66 44 9 45 3 56 84 33 85 91 12 69 38 95 18 58 32 -8 40 81 4 13 12 29 -6 67 7 80 -1 85 75 94 23 7 42 22 93 -6 83 19 18 79 82 92 87 92 42 38 14 20 2 40 84 96 83 64 17 -1 27 88 73 42 89 92 38 26 71 1 86 83 87 92 68 26 30 31 89 56 60 -1 25 70 88 40 50 36 42 83 53 23 82 68 48 -2 37 9 27 29 37 -1 49 97 5 29 89 33 12 27 48 -5 59 36 91 9 52 85 -6 70 85 64 86 21 5 76 67 17 40 5 62 71 46 5 70 95 60 46 30 81 82 54 64 25 2 47 81 69 71 -4 59 89 75 25 50 81 -4 6 -9 12 -3 14 97 26 7 16 82 10 31 28 22 3 83 5 7 31 32 98 37 72 33 77 68 24 18 40 34 35 2 57 99 50 15 46 67 57 32 17 92 4 32 54 60 83 66 89 46 68 95 64 25 88 88 85 -8 -2 82 20 12 12 63 -8 99 22 -5 74 48 9 54 88 57 23 82 63 61 19 43 22 75 72 31 89 99 26 3 31 56 33 15 29 92 47 9 81 20 56 86 18 55 3 23 97 57 92 40 24 61 39 70 -9 41 43 52 24 32 8 57 -2 97 85 36 86 52 0 21 95 90 17 74 18 15 87 99 19 99 81 66 60 5 11 70 0 20 72 -4 16 68 71 -2 90 24 88 81 28 -7 45 39 37 76 10

Expected output: 

78 1119

Actual output: 

78 1119

Run test: 

Test 7: Another large random game
✅ Test passed

3.2.8. Résumé global

✅ Test 1 : Depth 1 game passed
✅ Test 2 : Depth 2, no cutoffs passed
✅ Test 3 : Depth 2, cutoffs passed
✅ Test 4 : Small game passed
✅ Test 5 : Slightly deeper game passed
✅ Test 6 : Random game, deep but narrow passed
✅ Test 7 : Another large random game passed
Passed: 7 (100.0%)
Failed: 0 (0.0%)

3.3. Test Valgrind

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

4. Solution de la communauté

Solution de DaNinja : https://www.codingame.com/training/medium/minimax-exercise/solution?id=15267924 

#include <stdio.h>

int visits=0, move=0, depth, moves, scores[3500];

int negamax(int d,int p,int alpha,int beta,int cutoff){
    if (!cutoff) visits++;
    if (d>=depth) return p*scores[move++];      // score for player p
    int  best=-10000;
    for (int i=0; i<moves; i++){
        int score = -negamax(d+1,-p,-beta,-alpha,cutoff);
        if (!cutoff){
            if (score>best) best=score;
            if (best>alpha) alpha=best;
            if (alpha>=beta) cutoff=1;          // normally would break out of loop here
        }
    }
    return best;
}

int main(){
    scanf("%d%d", &depth, &moves);
    for (int i=0; i<pow(moves,depth); i++) scanf("%d", &scores[i]);
    int best=negamax(0,1,-10000,10000,0);
    printf("%d %d\n",best,visits);
}

J’ai choisi cette solution car elle est très simple et efficace. Elle utilise l’algorithme negamax qui est une version de l’algorithme minimax qui permet de réduire le nombre d’appels récursifs. Elle utilise aussi une technique de coupure alpha-beta qui permet de réduire le nombre d’appels récursifs. Le code est donc très compact et efficace. C’est une bonne solution pour ce problème. On note l’utilisation de variables globales pour stocker les données en entrée. C’est une solution simple mais qui n’est pas forcement très propre.

5. Conclusion

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-03-03

Auteur: Jules Girard

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