TP 5 : Programmation en binôme, les algorithmes MiniMax et a-b.

Application à Puissance 4 ou aux dames chinoises

1  Description des algorithmes

1.1  Définition d'un jeu à deux joueurs

Un jeu à deux joueurs est défini classiquement comme un arbre qui a comme noeuds des positions (la racine est appelée la «position initiale du jeu»). Chaque noeud est un noeud «joueur» (i.e. c'est au joueur de jouer son coup) ou un noeud «opposant», et les joueurs s'alternent, de telle sorte que un noeud joueur a comme fils une liste de noeuds opposants, que l'on obtient à partir des différents coups disponibles (symétriquement pour opposant). Si un noeud n'a pas de fils, c'est un noeud terminal, et dans ce cas on associe à ce noeud à l'aide d'une fonction h: noeudterminal® R È¥} une valeur qui indique ce que le joueur a gagné ou perdu. Typiquement, si on s'intéresse seulement à des jeux comme les échecs, on aura +¥ pour gain, -¥ pour perte et 0 pour les autres positions (pat et autres nuls), mais il y a des jeux avec des structures d'évaluation plus complexes, par exemple les jeux où on mise de l'argent.

D'une certaine façon, cet arbre contient toutes les parties possibles que l'on peut jouer à partir de la position initiale. Si on a la possibilité d'explorer tout l'arbre, on peut déterminer s'il existe une stratégie gagnante pour le joueur. Si l'arbre est trop gros (ou si l'on impose des limites de temps) on se contente normalement d'explorer le sous-arbre obtenu en tronquant l'arbre de jeu à une certaine profondeur, et en évaluant les noeuds tronqués à l'aide d'une heuristique h'.

Dans les deux cas, il est déraisonnable de supposer que l'arbre de jeu est donné de façon extensive, et on préfère le présenter de façon implicite par des «règles de jeu» qui disent comment obtenir la liste des fils d'une position donnée.

1.2  La visite MiniMax

L'algorithme MiniMax, dû à Von Neumann, est très simple : on visite l'arbre de jeu pour faire remonter à la racine une valeur (appelée «valeur du jeu») qui est calculée récursivement de la façon suivante :

On peut vérifier que MiniMax(p) est la meilleure valeur possible à partir de la position p, si l'opposant joue de façon optimale. Il est clair que pour appliquer l'algorithme MiniMax il suffit de disposer de

Cela nous donne notre interface C :

/* les positions */
struct position {
  . . . /* Ceci dépend du jeu
         * et ne doit pas être utilisé par la visite de l'arbre */
};

typedef struct position *position;

/* une liste de positions */
typedef struct {
  int nombre;
  position *tableau;
  /* On utilise un tableau, dont le nombre d'éléments est ci-dessus */
  /* Les coups à jouer sont représentés par leur position dans le tableau */
} posliste;

/* enfin, les fonctions propres au jeu */
double h(position p);
int estjoueur(position p);
posliste accessibles(position p);

/* plus une fonction qui permet de libérer de la mémoire */
void libere(posliste pl);

1.3  La visite a-b

L'algorithme a-b est une optimisation du MiniMax, qui «coupe» des sousarbres dès que leur valeur devient inintéressante aux fins du calcul de la valeur MiniMax du jeu. On s'intéressera donc, sur chaque noeud, en plus de la valeur, à deux autres quantités, nommées a et b, qui seront utilisées pour calculer la valeur du noeud.

a d'un noeud
est une approximation par le bas de la vraie valeur du noeud. Elle est égale à la valeur sur les feuilles, et est initialisée à -¥ ailleurs. Ensuite, sur les noeuds joueur elle est maintenue égale à la plus grande valeur obtenue sur les fils visités jusque là, et elle est égale à la valeur a de son prédécesseur sur les noeuds opposant.
b d'un noeud
est une approximation par le haut de la vraie valeur du noeud. Elle est égale à la valeur sur les feuilles, et est initialisée à +¥ ailleurs. Ensuite, sur les noeuds opposant elle est maintenue égale à la plus petite valeur obtenue sur les fils visités jusque là, et elle est égale à la valeur b de son prédécesseur sur les noeuds joueur.
L'algorithme ALPHA-BETA peut être décrit par le pseudo-code suivant :

fonnction ALPHA-BETA(P, A, B) /* ici A est toujours inférieur à B */
  si P est une feuille alors
    retourner la valeur de P
  sinon
    initialiser Alpha de P à -¥ et Beta de P à +¥
    si P est un noeud Min alors
      pour tout fils Pi de P faire
        Val = ALPHA-BETA(Pi, A, Min(B,Beta de P))
        Beta de P = Min(Beta de P, Val)
        Si A >= Beta de P /*ceci est la coupure alpha */
        alors retourner Beta de P 
      finfaire
      retourner Beta de P
    sinon
      pour tout fils Pi de P faire
        Val = ALPHA-BETA(Pi, Max(A,Alpha de P), B)
        Alpha de P = Max(Alpha de P, Val)
        Si Alpha de P >= B /*ceci est la coupure beta */
        alors retourner Alpha de P
      finfaire
      retourner Alpha de P
On sait que la véritable valeur MiniMax v d'un noeud est encadrée par a et b (i.e. a £ v £ b), et si on appelle la fonction ALPHA-BETA avec les valeurs (P,-¥,+¥) on obtient précisément MiniMax(P). ALPHA-BETA permets assez souvent de doubler la profondeur d'exploration d'un arbre à parité de ressources, par rapport à MiniMax.

2  Travaux pratiques

Programmer à plusieurs

Si vous avez à gérer un projet assez important, il est indispensable de pouvoir le décomposer en sous-projets dont les interfaces sont clairement spécifiées, pour permettre que les différentes composantes puissent être developpées en parallèle tout en garantissant la cohérence du résultat final.

Nous allons faire un essai à petite échelle dans le cadre de ce TP : le but est de programmer des algorithmes classiques de visite d'arbres de jeu, d'une part, et de programmer un jeu particulier d'autre part. Ces deux modules, ensemble, nous donneront un «joueur» automatique pour le jeu voulu. Pour cela, regroupez vous en binômes (programmeur A, programmeur B).

En pratique, chaque programmeur écrit les fonctions dont il a la charge dans un fichier C (par exemple visite.c et regles.c). Ces fichiers incluent le fichier «header» (par exemple jeu.h, avec la ligne #include "jeu.h") qui définit l'interface commune. Un troisième fichier C (jeu.c) sert à tester ces fonctions, et on compile par exemple avec gcc -o jeu visite.c regles.c jeu.c. Il est aussi possible de compiler séparément les fichiers visite.c et regles.c (sans produire d'exécutable) avec gcc -c visite.c


Exercice 1  [MiniMax et Tic-Tac-Toe]  . Le programmeur A écrit les fonctions de l'algorithme MiniMax. Le programmeur B écrit l'interface du jeu Tic-Tac-Toe. Compilez ensemble vos deux modules et testez leur correction de deux façons :
en faisant un programme qui calcule la valeur du jeu Tic-Tac-Toe,
en faisant un programme qui permette de jouer à Tic-Tac-Toe contre l'ordinateur.



Exercice 2  [AlphaBeta et Puissance 4]  . Le programmeur A écrit l'interface du jeu Puissance 4. Le programmeur B écrit les fonctions de l'algorithme AlphaBeta. Compilez ensemble ces deux modules.
Essayez aussi la combinaison MiniMax + Puissance 4 et la combinaison AlphaBeta + Tic-Tac-Toe.



Pour ceux qui sont vraiment rapides

Exercice 3   Adapter les exercices ci-dessus aux jeux à plus de deux joueurs. Application : le jeux des dames chinoises.


2.1  Visite de l'arbre de jeu

Pour chaque type de visite, on écrit deux fonctions, en utilisant exclusivement les fonctions de l'interface :
une fonction double val(position p) calcule la valeur du jeu,
une fonction int meilleur(posliste pl) dit quel est le meilleur coup pour le joueur qui doit jouer (on retourne sa position dans la posliste).

Ensuite, on modifie ces fonctions pour permettre de spécifier la profondeur maximale d'exploration de l'arbre de jeu.

2.2  Interface de chaque jeu

Pour chaque jeu, il faut définir le type de données position et programmer les fonctions suivantes :
/* affiche le jeu dans la position p */
void affiche(position p);

/* donne la position de départ */
position start();

/* Fonctions de l'interface */
double h(position p);
int estjoueur(position p);
posliste accessibles(position p);
void libere(posliste pl);

3  Rappels : règles des jeux

3.1  Iic-Tac-Toe

Sur une grille 3×3, chaque joueur coche à tour de rôle une case, celui qui en aligne 3 a gagné.
NB: on peut remarquer que le test d'alignement de 3 valeurs identiques est plus facile si la case vide est codée par 0 et les cases cochées par +1 ou -1.

3.2  Puissance 4

Sur une grille de 7 colonnes de 6 cases, chaque joueur met à tour de rôle un pion dans une colonne, celui-ci descend en bas de la colonne. Celui qui en aligne 4 a gagné.

3.3  Dames chinoises

sur les intersections d'un damier en étoile, chacun des six joueurs a 10 pions de sa couleur, chacun dans l'une des pointes de l'étoile. Le but du jeu est de tous les déplacer dans la pointe opposée. Chacun à son tour déplace un pion, de l'une des deux façons suivantes : vers une case libre contiguë, ou bien en faisant un nombre quelconque de sauts avec ce pion. Chaque saut se fait vers une case libre, par dessus une case occupée. Le Damier