Minimax Simple Example

Page web ISIMA
Documentation
Fichier .org source
Défi de programmation - Minimax Simple Example

1. Introduction

Dans cet exercice, il y a 2 joueurs, avec en face d’eux une pile de lettres. Les joueurs jouent un coup chacun et peuvent choisir à leur tour de prendre soit la 1^ère soit la 2^ème lettre de la pile.
A la fin de la partie, le score de chaque joueur est déterminé en fonction des mots qu’ils peuvent composer, chaque mot est associé à un score d’après un dictionnaire donné.

2. Approche utilisée

Aucune de mes tentatives n’ont abouti, c’est pourquoi je présente ici la solution d’un autre utilisateur de Codingame.

2.1. Description synoptique

Le principe de ce programme est de générer toutes les issues possibles du jeu, et d’en déterminer la meilleure à choisir pour le joueur.

2.2. Exemple de partie

A partir des les ’A’, ’S’, ’R’, ’E’, avec pour scores :

Mot	Score
’SA’	2
’SE’	4
’RE’	1
’A’	1

On en détermine l’arbre suivant, et on fait remonter le meilleur score pour le joueur A (on note dA et dB le deck du joueur respectivement A et B) :

2.3. Algorithme

Fonction getscore :
Initialise le scoreTotal à 0.
Parcours tout les mots du dictionnaire, si le mot peut être formé avec les lettres données, ajoute le score du mot au scoreTotal.
La fonction renvoie le scoreTotal.

Fonction proc :
Parcours toutes les lettres de la pile et appelle minimax pour trouver le meilleur coup à jouer.
Met à jour la pile de lettre en fonction du coup trouvé.

Fonction minimax :
Génère toutes les issues possibles et garde celle ayant le score le plus haut pour le joueur A, et le score le plus bas pour le joueur B.

Fonction evaluate :
A partir d’une pile de lettre, détermine les jeux du joueur 1 et 2.
Renvoie la différence de score des 2 jeux.

3. Resolution

3.1. Programme

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int getscore(char  *letters);
int evaluate(char *set);
int minimax(char *set, int depth, int L, int R, int alpha, int beta);
int proc(void);
int N;/*number of letters*/
int Q;/*number of words*/
char letters[26];
char words[100][11];
char set[26];
int scores [100];
int bestmove[2];
int sa,sb;

int main()
{
    scanf("%d%d", &N, &Q);
    for (int i = 0; i < N; i++) {
        char letter[2];
        scanf("%s", letter);
    letters[i]=letter[0];
    }
    for (int i = 0; i < Q; i++) {
        int score;
        scanf("%s%d", words[i], &scores[i]);
    }
    proc();
    printf("%c %d-%d\n",set[0],sa,sb);
    return 0;
}

int getscore(char *letters){
 char *s;
 int score=0;
 for(int i=0; i<Q; ++i){
  s = words[i];
   while((*s) && letters[(*s) - 'A'])
    ++s;
    if(!*s)
       score += scores[i];
 }
 return score;
}

int proc(void){
 for(int i=0,l=0,r=1;i<N;++i,r=r<N?r+1:r){
  minimax(set,i,l,r,-0xffff,0xffff);
 if(!bestmove[i & 1]){
   set[i] = letters[l];
   l = r;
  }else
     set[i] = letters[r];
 }
 evaluate(set);
}

int minimax(char *set, int depth, int L, int R, int alpha, int beta){
  if(depth == N)
        return evaluate(set);
  int val,l,r;
   l = R;
   r = R < N ? R+1: R;
  if(depth & 1){//minimizer
   set[depth] = letters[L];
   val = minimax(set,depth+1,l,r,alpha,beta);
   if(val < beta){
    beta = val;
    bestmove[1] = 0;
    if(beta <= alpha) return beta;//prune
   }
    if(depth == N-1) return val;
   set[depth] = letters[R];
   val = minimax(set,depth+1,L,r,alpha,beta);
   if(val < beta){
    beta = val;
    bestmove[1] = 1;
   }
   return beta;
  }else{//maximizer
   set[depth] = letters[L];
   val = minimax(set,depth+1,l,r,alpha,beta);
   if(val > alpha){
    alpha = val;
    bestmove[0] = 0;
    if(alpha >= beta) return alpha;//prune
   }
   set[depth]=letters[R];
   val = minimax(set,depth+1,L,r,alpha,beta);
   if(val > alpha){
    alpha = val;
    bestmove[0] = 1;
   }
   return alpha;
  }
}

int evaluate(char *set){
char a[26],b[26];
 memset(a,'\0',sizeof(char)*26);
 memset(b,'\0',sizeof(char)*26);
  for(int i=0;i<N;++i){
   if(i & 1)
    b[set[i] - 'A'] = 1;
   else
    a[set[i] - 'A'] = 1;
  }
 sa = getscore(a);
 sb = getscore(b);
 return sa - sb;
}

3.2. Test

A partir du test suivant (minimax2.txt) (même test que dans 2.2. Exemple de partie):

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

Le programme affiche la lettre à choisir et le score final prédit :

S 4-1

4. Bilan

Bien que l’exercice soit facile à comprendre, j’ai eu du mal sur son implémentation et aucune de mes tentatives n’ont abouti.