Rapport sur Minimax Exercice
Table of Contents
Présentation du problème
Minimax exercice est un problème du site Codingame. Ce problème vise à utiliser les algorithmes minimax et élagage alpha beta. Le but du problème est de trouver le plus grand score qu’un joueur peut obtenir, ainsi que le nombre de noeuds que l’on a visité pour trouver le résultat (voir détail algorithmique). Pour cela le site Codingame nous fourni plusieurs entrées.
- D: la hauteur de l’arbre des possibilitées
- B: le nombre de possibilitées pour chaque tour de jeu
- une ligne de BD nombres: toutes les feuilles de l’arbre contenant le score du joueur
Métode de résolution
Description de la stratégie
Afin de résoudre ce problème, j’ai créé quelques fonctions auxiliaires, une fonction principale minimax, et j’ai récupéré les entrées dans le programme principal. Voici ci dessous la décomposition de mon code en plusieurs parties.
Partie 1: Définition des fonctions auxiliaires
int minimum(int a, int b) // Permet de trouver le minimum { if (a <= b) return (a); return (b); } int maximum(int a, int b) // Permet de trouver le maximum { if (a >= b) return (a); return (b); } int ft_power(int a, int b) // Fonction puissance { if (b < 0) return (0); if (b == 0) return (1); return (a * ft_power(a, b - 1)); }
Dans cette partie, on définie 3 fonctions utiles pour notre code. Une fonction permettant d’afficher le minimum de 2 nombres, une fonction permettant d’afficher le maximum de 2 nombre, et enfin une fonction permettant de faire des calculs de puissance.
Partie 2: Définition de la méthode minimax
int minimax(int *feuille, int branchf, int depht, int a, int b, int joueur, int *compteur) { int i; int value; i = 0; if (depht == 0){ // Si on est au niveau des racine de l'arbre //fprintf(stderr,"%d.\n",*feuille); return (*feuille); } if (joueur == 1){ // Si c'est au joueur 1 de jouer value = -999; // On assigne la pire valeur possible while (i < branchf){ // On test chaque possibilité de jeu //fprintf(stderr,"%p p\n",&feuille[i * ft_power(branchf, depht - 1)]); value = maximum(value, minimax(&feuille[i * ft_power(branchf, depht - 1)], branchf, depht - 1, a, b, 0, compteur)); // La valeur correspond au maximum entre la valeur actuelle et la valeur meilleure valeur disponible dans les branches précedentes (*compteur)++; // On a regardé un noeud de plus if (value >= b){ // Elagage alpha beta break; } a = maximum(value, a); i++; } } if (joueur == 0){ // Si c'est au joueur 0 de jouer value = 999; while (i < branchf){ value = minimum(value, minimax(&feuille[i * ft_power(branchf, depht - 1)], branchf, depht - 1, a, b, 1, compteur)); // Appel de la fonction // C'est au joueur 1 de jouer (*compteur)++; if (value <= a){ // Elagage alpha beta break; } b = minimum(value, b); i++; } } return (value); }
Cette fonction est au coeur de notre programme. On va l’appeler récursivement jusqu’à trouver la racine de l’arbre. Pour chaque valeur, on va parcourir les valeurs du même embranchement et du même étage (cela grace aux entrées D et B fournient par le site), et en fonction de si c’est au joueur 1 ou 0 de joueur, on va lui applqieur l’algorithme minimax. Par exemple si c’est au joueur 1, pour trouver la valeur que l’on retient des feuilles, on cherche la meilleure valeure possible. De plus à chaque visite de noeud on incrémente un compteur de 1, afin de pouvoir récupérer le nombre de noeuds visités. Si l’élagage alpha béta indique qu’il n’est pas utile de visiter la suite des branches, les noeuds ne seront pas comptabilisés comme explorés.
Partie 3: Programme principal
int main() { int D; int B; int i = 0; int j = 0; int answer; int compteur[1]; *compteur = 1; scanf("%d%d", &D, &B); fgetc(stdin); char feuille[40001]; int feuille2[20001]; scanf("%[^\n]", feuille); while (feuille[j]!='\0') // Tant que l'on est pas à la fin de la chaine { feuille2[i] = atoi(&feuille[j]); // On converti en nombre i++; j++; while (feuille[j] != ' ' && feuille[j]) // Tant que l'on regarde toujours un chiffre j++; } answer = minimax(feuille2, B, D, -999, 999, 1, compteur); // Récupération de la solution printf("%d %d\n", answer, *compteur); // Affichage de la solution return 0; }
Le programme principal permet dans un premier temps de récupérer les entrées fournies sous la forme d’une chaine de caractère, et de les convertir en entier. On stockera ces entrées dans un tableau à une dimension que l’on parcourera dans la fonction minimax. Puis on appelle la fonction récursive afin de parcourir l’arbre et de trouver la valeur à la racine de l’arbre.
Détail algorithmique de la méthode
L’essentiel de ce programme se base donc sur l’algorithme minimax, et sur l’élagage alpha beta, deux techniques connues en algorithmie. Dans cette partie nous allons donc nous pencher en détail sur ces 2 méthodes très utiles en théorie des jeux.
Algorithme minimax
La technique minimax consiste en trouver la plus haute valeur que l’on est sûr d’obtenir. C’est-à-dire que l’on ne prend pas en compte le talent du joueur en face. On étudie toutes les possibilitées disponibles et on sélectionne la meilleure (ou la moins pire), celle etant la plus favorable au joueur. Ainsi, on explore l’arbre des possibilitées en recherchant la meilleure.
Dans le cas du problème Codingame on représente les coups par des valeurs. Voici un petit exemple.
Cliquez ici pour agrandir
/Les étages rouges représentent max et les étages cyan représentent min /
Dans cet exemple on explore toutes les possibilitées de l’arbre, et on conserve celle que l’on est sûr d’avoir, et ce grace à l’algorithme minimax. La valeur retenue est donc 5.
Elagage alpha beta
L’algorithme minimax fonctionne à coup sûr et peut-être très utile. Malheuresement sa complexité temporelle est rès importante. En effet, le fait de devoir observer chaque possibilité de jeu le rend très long à executer et très peu optimisé. Ainsi, on a créé des techniques pour le rendre plus efficace. C’est le ca de l’élagage alpha beta qui va diminuer le temps d’execution du programme.
Il permet de ne pas devoir explorer chaque noeud, mais seulement certains noeuds en fonction des valeurs obtenues lors de l’exploration des noeuds précedents. Ainsi, si un noeud situé proche des racines n’est pas exploré, cela fera gagner énormement de temps au programme.Voici un petit exemple.
Cliquez ici pour agrandir
Les étages rouges représentent max et les étages cyan représentent min. Les élements grisés sont ceux que l’on explore pas.
Dans cet exemple on explore pas toutes les possibilitées de l’arbre. Grace à l’élagage alpha beta on se rend compte qu’il n’est pas nécessaire d’explorer le noeud grisé. En effet le noeud min a pris la valeur 4. Donc les prochaines valeurs qu’il pourra prendre seront forcement inférieures à 4. Or la valeur retenue sur le noeud le plus haut sera le maximum entre les deux noeuds du dessous. Un des noeuds possède déja la valeur 5 et ne sera plus modifié. Comme l’autre noeud contiendra une valeur inférieur ou égale à 4, peu importe la valeur du noeud grisé, le noeud retenu sera le noeud cyan avec la valeur 5. La valeur finale retenue est donc 5. L’élagage alpha beta a donc le même résultat que la seule technique minimax, mais est plus rapide que cette dernière.
Exemple concret
Cet exemple se base sur le jeu du morpion.
Cliquez ici pour agrandir
Dans ce cas, le jeu a déja commencé depuis 4 coups, on commence donc notre étude au coup numéro 5. On considère que le joueur rouge a placé le premier coup, ici c’est donc à lui de jouer. On évalue les cas pour qu’ils soient favorables au joueur rouge. Le score 1 représente une victoire, 0 un match nul, -1 une défaite. Les carrés noirs représentent la suite de l’arbre sous forme réduite.
Dès la première observation du graphique, on se rend compte que en jouant parfaitement, avec la configuration initiale, la victoire est asurée. En effet, on va remonter l’arbre en appliquant l’élagage alpha beta et minimax afin de jouer les meilleurs coups posibles. La branche gauche de l’arbre nous montre que si on place mal notre coup au tour 5, la défaite est assurée, car le joueur adverse aura une possibilitée directe de finir la partie. Dans la branche droite, on arrive a une configuration qui nous permet de gagner. En effet, il y a deux manières de gagner de façon direct, donc même si le joueur adverse en bloque une, il nous reste la seconde. On se rend compte qu’il n’est pas nécessaire d’évaluer les autres cas lorsque l’on se trouve au tour 5. En effet, comme la seconde grande branche de l’abre nous permet de gagner, il n’est pas nécessaire de chercher une autre manière de gagner, ou simplement de regarder ce qu’il se passe dans un autre cas, puisque l’objectif est atteint.
Code commenté ayant résolu le problème
Voici ci dessous le code complet m’ayant permis de résoudre le problème.
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> int minimum(int a, int b) // Permet de trouver le minimum { if (a <= b) return (a); return (b); } int maximum(int a, int b) // Permet de trouver le maximum { if (a >= b) return (a); return (b); } int ft_power(int a, int b) // Fonction puissance { if (b < 0) return (0); if (b == 0) return (1); return (a * ft_power(a, b - 1)); } int minimax(int *feuille, int branchf, int depht, int a, int b, int joueur, int *compteur) { int i; int value; i = 0; if (depht == 0){ // Si on est au niveau des racine de l'arbre //fprintf(stderr,"%d.\n",*feuille); return (*feuille); } if (joueur == 1){ // Si c'est au joueur 1 de jouer value = -999; // On assigne la pire valeur possible while (i < branchf){ // On test chaque possibilité de jeu //fprintf(stderr,"%p p\n",&feuille[i * ft_power(branchf, depht - 1)]); value = maximum(value, minimax(&feuille[i * ft_power(branchf, depht - 1)], branchf, depht - 1, a, b, 0, compteur)); // La valeur correspond au maximum entre la valeur actuelle et la valeur meilleure valeur disponible dans les branches précedentes (*compteur)++; // On a regardé un noeud de plus if (value >= b){ // Elagage alpha beta break; } a = maximum(value, a); i++; } } if (joueur == 0){ // Si c'est au joueur 0 de jouer value = 999; while (i < branchf){ value = minimum(value, minimax(&feuille[i * ft_power(branchf, depht - 1)], branchf, depht - 1, a, b, 1, compteur)); // Appel de la fonction // C'est au joueur 1 de jouer (*compteur)++; if (value <= a){ // Elagage alpha beta break; } b = minimum(value, b); i++; } } return (value); } int main() { int D; int B; int i = 0; int j = 0; int answer; int compteur[1]; *compteur = 1; scanf("%d%d", &D, &B); fgetc(stdin); char feuille[40001]; int feuille2[20001]; scanf("%[^\n]", feuille); while (feuille[j]!='\0') // Tant que l'on est pas à la fin de la chaine { feuille2[i] = atoi(&feuille[j]); // On converti en nombre i++; j++; while (feuille[j] != ' ' && feuille[j]) // Tant que l'on regarde toujours un chiffre j++; } answer = minimax(feuille2, B, D, -999, 999, 1, compteur); // Récupération de la solution printf("%d %d\n", answer, *compteur); // Affichage de la solution return 0; }
Présentation des tests
Afin de coder ce programme et de le valider, il a fallut passer plusieurs tests. Alors voici ci dessous les tests qui m’ont permi de résoudre ce problème.
Test 1
Test 2
Test 1 à 7
========Test numero 1 passe======== ==============Sortie============== 3 5 ================================== ========Test numero 2 passe======== ==============Sortie============== 3 7 ================================== ========Test numero 3 passe======== ==============Sortie============== 1 6 ================================== ========Test numero 4 passe======== ==============Sortie============== 0 11 ================================== ========Test numero 5 passe======== ==============Sortie============== -170 37 ================================== ========Test numero 6 passe======== ==============Sortie============== 59 1510 ================================== ========Test numero 7 passe======== ==============Sortie============== 78 1119 ==================================
Remarques sur les tests précedents
Valgrind
Afin d’être certain de ne pas avoir de problèmes de mémoire et autres, que le compilateur n’aurait pas détecté, on utilise valgrind.
valgrind ./minimax < minimaxtest/test7
Cliquez ici pour agrandir
Le programme présenté passe bien valgrind pour tout les test.
Description d’une autre solution au problème
J’ai choisi de présenter la solution de l’utilisateur MJZ. Sa solution est vraiment intéressante car elle est très compacte, et est écrite de manière vraiment intelligente. Son code n’est pas vraiment divisible en plusieurs parties, je vais donc le présenter entièrement ci dessous.
Code commenté de l’utilisateur MJZ
#include <stdio.h> int D, B, nodes = 0; int ab(int depth, int cut, int alpha, int beta) { // Fonction minimax int value, x = depth % 2 ? 10000 : -10000; // Regarde quel joueur joue et fixe la valeur en fonction if(!cut) nodes++; // Si on regarde un noeud if(depth == D) scanf("%d", &x); // Récupération de la prochaine valeur else for(int i = 0; i < B; i++) { value = ab(depth + 1, cut, alpha, beta); // exploration de la branche du dessus if(depth % 2 == 0) { // Si c'est le joueur 0 if(value > x) x = value; // Mise à jour de la valeur if(x > alpha) alpha = x; } else { // Si c'est le joueur 1 if(value < x) x = value; // Mise à jour de la valeur if(x < beta) beta = x; } if(alpha >= beta) cut = 1; // élagage alpha beta } return x; } int main() { scanf("%d%d", &D, &B); fgetc(stdin); // Récupération des entrées int best = ab(0, 0, -10000, 10000); // Appel de minimax printf("%d %d\n", best, nodes); // Affichage du résultat return 0; }
Son programme va d’abord commencer par récupérer la profondeur de l’arbre et la division des branches, puis va appliquer l’algorithme minimax. Afin de détecter quel joueur joue, on va simplement regarder si l’étage que l’on regarde a un numéro pair, car les joueurs jouent chacun leur tours. Donc les scores d’un même joueur seront toujours représentés sur des étages de même parité. Ensuite, on va récupérer les entrées du test, et regarder le maximum ou le minimum entre la valeur récupérée et les bornes. Enfin, grace à une simple condition, on va appliquer l’élagage alpha beta en changeant la valeur d’une variable. Ainsi, si il n’est pas utile de regarder la suite des branches, le programme ne comptera pas les branches suivantes comme explorées.
Doxygene
Pour plus d’information sur ce programme, voici une page de documentation qui s’interesse au code résolvant ce problème.
Bilan de ce travail
Ce travail m’a permi de découvrir un nouvel algorithme, ayant une grande importance dans l’histoire de l’informatique et de l’étude des jeux. Ainsi, cela m’a permi de me pencher de façon plus détaillé sur le fonctionnement d’anciennes machines capables de battre des humains sur des jeux de ce type (bien sur aujourd’hui elles ne sont plus d’actualitée mais c’est intéressant de voir ce qui existait avant).