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.