TP2, IFT3330/6330

Jeu d’Othello

 

Date de remise

À rendre avant midi lundi le 8 novembre, 2004.

Le jeu

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.

Le devoir

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]]

 

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.

À faire

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.

Barème de correction

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.