TP2,
IFT3330/6330
À rendre avant midi lundi le 8 novembre, 2004.
Ce TP vise à vous familiariser avec les recherches heuristiques.
Il consiste à la réalisation d'un programme pour jouer le jeu d'Othello. La
règle du jeu est décrite au site suivant : http://www.rainfall.com/othello/rules/othellorules.asp.
Ce site offre aussi le jeu en ligne, que vous pouvez essayer.
On vous demande d’implanter ce jeu dans lequel un utilisateur peut jouer contre l’ordinateur (qu’on appelle le joueur Ordi). L’utilisateur (le joueur X) est toujours donné les pièces noires (X), et Ordi les pièces blanches (O). C’est le joueur X qui doit commencer le jeu. Pour réduire la complexité, on réduit la taille de grilles à 6X6. La configuration de départ est donc comme suit :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
O |
X |
|
|
|
|
X |
O |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nous fixons la représentation suivante pour une configuration dans
ce TP : Chaque configuration est représentée comme une liste de 6 listes
de 6 éléments. Les 6 éléments correspondent à une ligne, et les 6 listes aux 5
colonnes. La configuration de départ est donc représentée comme suit :
[[v, v, v, v, v, v],
[v,
v, v, v, v, v],
[v, v, o, x, v, v],
[v, v, x, o, v, v],
[v,
v, v, v, v, v],
[v,
v, v, v, v, v]]
où v signifie que la place est vide,
o (la lettre o) signifie que c’est une pièce blanche, est x une pièce noire.
Quand le joueur utilisateur choisit une place, il l’identifie par
ses coordonnées. Par exemple, [1,2] identifie la deuxième place de la première
ligne.
1. Pour le joueur Ordi, on vous demande d’utiliser l’algorithme
minimax pour déterminer l’endroit où il doit poser la pièce. Pour limiter la
complexité, cet algorithme explore l’espace d’états à une profondeur de 2. Pour
évaluer la valeur heuristique (ou la chance pour le joueur Ordi de gagner) pour
une position possible, on utilise le nombre de pièces supplémentaires que le
joueur Ordi peut obtenir en plaçant sa pièce à cette position. Par exemple, si
l’utilisateur choisit de placer une pièce noire à la place [2,3], le nombre de
pièces noires qu’il va obtenir est 2. La configuration devient la
suivante :
|
|
|
|
|
|
|
|
X |
|
|
|
|
|
X |
X |
|
|
|
|
X |
O |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Bien sûr, quand l’utilisateur a placé sa pièce, le programme doit
modifier la configuration du jeu selon les règles. Dans ce TP, on ne tient pas
compte du nombre limité de pièces par joueur. On suppose que les joueurs ont
toujours des pièces disponibles.
Pour uniformiser, votre programme doit contenir les prédicats
suivants
- meilleur(Jeu, Joueur, Strategie, Profondeur, Position) : Ce prédicat détermine la
meilleure Position à placer une pièce pour le Joueur dans un Jeu, en explorant
à une Profondeur, et en appliquant la Strategie de
calcul de valeur heuristique d’une position. Jeu est une configuration de jeu
(liste de listes comme spécifiée avant), Position est une liste de deux nombres
correspondant à une position possible, et Strategie
peut être soit ‘n’ – signifiant que la valeur est le nombre de pièces
supplémentaires comme expliqué ici, soit ‘h’ – un calcul en utilisant un
critère heuristique que vous devez développer vous-même (voir le point 3).
- valeur(Jeu, Joueur, Strategie,
Val) : Ce prédicat calcule la valeur Val pour le Joueur dans un Jeu, en
utilisant la Strategie de calcul.
Note : Si vous avez besoin d'autre
arguments pour les prédicat meilleur et valeur, on vous autorise des les
ajouter.
Le prédicat pour lancer cette version doit être
"othello_u_o2", qui signifie utiliser la configuration de départ,
l’utilisateur joue contre l’Ordi qui utilise la
calcule ‘n’ et explore à une profondeur de 2. L’exécution doit afficher la
configuration au fur et à mesure. Un prédicat d’affichage vous sera rendu
disponible (voir la page Web du cours).
2. On vous demande d’implanter une deuxième version de
l’algorithme minimax avec la même fonction d’évaluation heuristique que dans le
point 1, mais il explore à une profondeur de 3. Attention, comme à la
profondeur de 3, c’est au tour de l’adversaire de jouer, la valeur que vous
obtenez correspond au nombre de pièces supplémentaires que l’adversaire peut
obtenir.
Utilisez cette deuxième version pour jouer contre la première
version sans intervention de l’utilisateur. Le lancement de cette version se
fait par le prédicat : "othello_o3_o2", qui signifie que l’Ordi qui explore à une profondeur de 3 joue contre l’Ordi qui explore à une profondeur de 2.
3. Utilisez maintenant l’algorithme minimax à une profondeur de 2,
mais changer le calcul de valeur d’une position en utilisant des critères
heuristiques que vous découvrez vous-mêmes. Pour découvrir des heuristiques
utiles, jouez quelques parties du jeu sur le site mentionné plus haut. Comme
pour le point 2, vous devez utiliser cette version pour jouer contre la
première version. Le lancement de cette version se fait
par « othello_h2_o2 » - votre nouvel algorithme heuristique de
profondeur 2 contre l’algorithme de base.
Ce TP compte pour 10 points. En plus de rendre votre programme,
vous devez aussi rédiger un mini-rapport de 3 pages maximum, décrivant
très brièvement votre implantation (surtout votre heuristique), une comparaison
de performance de différentes versions, et une discussion sur les méthodes
implantées.
-
7 points pour le fonctionnement du programme : 3 pour la
version 1, 1 pour la version 2, et 3 pour la version 3 (dont 1 point est
réservé pour la qualité des heuristiques).
-
2 points pour le rapport.
-
1 point pour la structure et le style du programme en Prolog.