Atelier d'algorithmique - E3 – PR3001 - TP

Michel Couprie

Important :

Chaque trinome ou binome doit m'envoyer son rapport par courriel à l'adresse suivante :

michel.couprie@esiee.fr

au plus tard le vendredi 22 février.
Le code source et les jeux de test réalisés doivent être inclus.

Version 1

Ecrivez la fonction EvalPosition qui, étant donnés :
N, un entier,
P, un tableau N x N d'entiers, et
A, un entier représentant le nombre de pions alignés nécessaires pour gagner,
retourne un entier entre +1000 et -1000 qui constitue une évaluation de la position dans P : plus cet entier est proche de +1000 et meilleure est la position du point de vue du joueur 1.

Cette évaluation est dite "statique", c'est-à-dire qu'elle ne tient compte que de la position P, et pas des coups pouvant être joués dans le futur par chacun des joueurs.

Ecrivez un programme principal qui joue contre un adversaire humain, en utilisant la fonction EvalPosition pour choisir le coup à jouer. Pour cela on aura aussi besoin de programmer les procédures ou fonctions suivantes :

InitPosition(N,P) : initialise à 0 toutes les cases du tableau P

AffichePosition(N,P) : affiche à l'écran, sous forme texte, la position représentée par P

PlusDeCasesLibres(N,P) : retourne 1 si toutes le cases de P sont non-nulles, et 0 sinon

SaisirCoupJoueur(N,P) : demande à l'utilisateur de saisir un couple de coordonnées, jusqu'à obtenir un coup valide, et modifie P en fonction de ce coup

Version 2

Ecrivez la fonction récursive MinMax qui prend comme paramètres d'entrée :
N, un entier,
P, un tableau N x N d'entiers,
A, un entier représentant le nombre de pions alignés nécessaires pour gagner,
J, le numéro du joueur qui doit jouer, et
D, la profondeur de la récursion.

Cette fonction implémente la stratégie d'évaluation dite "min-max" étudiée en TD (voir aussi la page Wikipedia sur min-max), et retourne un entier entre +1000 et -1000 qui constitue une évaluation de la position dans P : plus cet entier est proche de +1000 et meilleure est la position du point de vue du joueur 1. Elle utilise la procédure EvalPosition pour l'évaluation statique (profondeur 0).

Modifiez votre programme principal pour qu'il utilise cette procédure à la place de EvalPosition pour choisir le coup à jouer.

Versions 3,4,5...

Apportez toutes les améliorations auxquelles vous pensez pour améliorer les performances de votre programme. On peut penser en particulier à :

- améliorer la fonction d'évaluation statique, par exemple en tenant compte des possibilités de "blocage" d'un alignement partiel par un bord ou par un pion de l'adversaire,

- diminuer le nombre de positions évaluées en évitant des évaluations inutiles ou peu pertinentes (voir en particulier la stratégie d'élagage alpha-beta)...

Dernière mise à jour : par Michel Couprie.