Rapport sur sudoku solver

minimax exercise est un problème du site codingame. L’énoncé est poser comme suit:

On nous donne un jeu à 2 joueurs, à somme nulle, où les joueurs alternent leurs tours. La partie dure toujours D tours, et lors de son déplacement, chaque joueur doit choisir parmi B choix. Ainsi, D est la profondeur de l’arbre de jeu, B son facteur de branchement, et selon les choix des joueurs, le jeu a B^D résultats possibles.

En supposant que l’arbre de jeu est suffisamment petit, nous pouvons vérifier tous les résultats et résoudre le jeu (c’est-à-dire calculer la meilleure stratégie pour chaque joueur) en utilisant l’algorithme Minimax ( https://en.wikipedia.org/wiki/Minimax ).

Pour rendre notre algorithme plus efficace, nous pouvons ignorer certains calculs en utilisant la technique d’élagage alpha-bêta ( https://en.wikipedia.org/wiki/Alpha-beta_pruning ).

Votre tâche consiste à calculer le gain minimum pour le premier joueur utilisant Minimax avec des seuils alpha-bêta. Les mouvements doivent être examinés dans l’ordre de gauche à droite, comme indiqué dans l’entrée.

commme dit dans l’énoncé, le problème est de trouver la meilleur solution possible pour le joueur afin qu’il ai le plus de chance de remporter la partie. Il faut pour cela utiliser un algorithme minimax, c’est un algorithme basé sur la théorie des jeux pour des jeux a deux joueurs à somme nulle consistant a minimiser la perte au maximum. On nous donne dans cet exercice en entrée, deux valeurs, D et B qui réprésente dans l’ordre, la profondeur de l’arbre de jeux, ainsi le facteur de ramification. On nous donne ensuite un ligne composée de B^D entiers. Il faut regarder la valeur maximum qu’il est possible de faire grace à un algorithme minimax en fonction de la profondeur et du facteur de ramification, ainsi que compter le nombre de noeud traversé pour atteindre l’objectif.

J’ai choisi de présenter la solution de MJZ qui est une méthode baser sur l’élagage alpha beta

#include <stdio.h>

int D, B, nodes = 0;

int ab(int depth, int cut, int alpha, int beta) {
    int value, x = depth % 2 ? 10000 : -10000;
    if(!cut) nodes++;
    if(depth == D) scanf("%d", &x);
    else
        for(int i = 0; i < B; i++) {
            value = ab(depth + 1, cut, alpha, beta);
            if(depth % 2 == 0) {
                if(value > x) x = value;
                if(x > alpha) alpha = x;
            } else {
                if(value < x) x = value;
                if(x < beta) beta = x;
            }
            if(alpha >= beta) cut = 1;
        }
    return x;
}

int main() {
    scanf("%d%d", &D, &B); fgetc(stdin);
    int best = ab(0, 0, -10000, 10000);
    printf("%d %d\n", best, nodes);
    return 0;
}

Il n’utilise qu’une seule fonction en plus du main, la fonction ab (alphabeta) qui est un algorithme d’elagage alpha beta baser sur un algorithme minimax. Il récupère d’abord les entrées B et D puis appel la fonction ab ou il récupère un à un les valeurs données sur la deuxième ligne d’entrée.

minimax simple example est un exercice du site codingame, l’énoncé est donné comme ceci:

Au début les 2 joueurs voient un tas de lettres, toutes différentes. À tour de rôle, ils peuvent choisir d’obtenir la première ou la deuxième lettre de la pile. Au dernier tour, le dernier joueur n’a d’autre choix que d’obtenir la dernière lettre. Ensuite, les joueurs marquent en fonction des mots qu’ils peuvent construire avec leurs lettres collectées. Un dictionnaire donne les mots possibles avec leurs gains associés. Les lettres peuvent être utilisées plusieurs fois pour former plusieurs mots.

Vous devez 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’.

Ce puzzle est un jeu simple pour implémenter un algorithme minimax. Vous devrez peut-être optimiser votre code avec l’élagage alpha-bêta pour certains tests.

comme dit dans l’énoncé, cet exercice consiste a implémenter un alogrithme minimax avec un elagage alpha beta dans un reel exemple de jeux, Ce jeux ressemble un peut à un scrabble, on nous donne des lettres et il faut former des mots qui ont une valeur en point, et celui qui a le plus de point gagne.

Je n’ai pas réussi à creer une bonne méthode pour résoudre cet exercice, voici le début de code que j’ai essayer de creer en repartant de la base de mon code minimax exercise.

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

typedef struct {
  char mot[26];
  int valeur;
} Mot;

// fonctions min et max qui renvoie le maximum/minimum entre 2 valeurs
int min(int a, int b) { return a >= b ? b : a; }

int max(int a, int b) { return a >= b ? a : b; }

// fonction puissance qui renvoie le nombre de le nombre de valeurs dans le sous
// arbre dont la racine est le noeud sur lequel on se trouve lors de l'appel.
int puissance(int a, int b) {
  if (b < 0)
    return (0);
  if (b == 0)
    return (1);
  return (a * puissance(a, b - 1));
}

// fonction récursive minimax qui applique l'algorithme minimax a l'arbre
// données en entrées avec la profondeur donnée et le facteur de ramification
// donné
int minimax(char *feuille, int branchf, int profondeur, int a, int b,
            int joueur) {
  int i;
  int value;

  i = 0;
  // cas ou nous nous trouvons sur une feuille
  if (profondeur == 0) {
    return (*feuille);
  }
  // cas ou c'est le tour du joueur 1
  if (joueur == 1) {
    value = -999;
    while (i < branchf) {
      value =
          max(value, minimax(&feuille[i * puissance(branchf, profondeur - 1)],
                             branchf, profondeur - 1, a, b, 0));
      if (value >= b)
        break;
      a = max(value, a);
      i++;
    }
  }
  // cas ou c'est le tour du joueur 0
  if (joueur == 0) {
    value = 999;
    while (i < branchf) {
      value =
          min(value, minimax(&feuille[i * puissance(branchf, profondeur - 1)],
                             branchf, profondeur - 1, a, b, 1));
      if (value <= a)
        break;
      b = min(value, b);
      i++;
    }
  }
  return (value);
}

int main() {
  int n;
  int q;
  Mot *l = malloc(q * sizeof(Mot));
  char lettre[26] = {"\0"};
  char mlettre;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < 2 * n; i += 2) {
    char letter[2] = {"\0"};
    scanf("%s", letter);
    strcat(lettre, letter);
  }
  for (int i = 0; i < q; i++) {
    char word[26] = {"\0"};
    int value;
    scanf("%s%d", l[i].mot, &l[i].valeur);
    if (word[0] >= 'A' && word[1] >= 'A' && word[0] <= 'Z' && word[1] <= 'Z') {
      strcat(l[i].mot, word);
      l[i].valeur = value;
    }
  }
  for (int i = 0; i < n; i++) {
    fprintf(stderr, "%c\n", lettre[i]);
  }
  for (int i = 0; i < q; i++) {
    fprintf(stderr, "%s: %d\n", l[i].mot, l[i].valeur);
  }

  // mlettre=minimax(lettre,q,n,-999,999,1);
  // printf("%c",mlettre);
  free(l);
  return 0;
}