TP3,
IFT3335
À rendre avant midi le 20
novembre, 2007.
A faire en groupe de 2
personnes ou seul.
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.
Essentiellement, un joueur
possède des pièces noires et l’autre des pièces blanches. En plaçant une pièce
à une case A, si cette case est dans une ligne horizontale, verticale ou
diagonale avec une autre pièce B du même joueur, les pièces de l’adversaire qui
se trouvent entre A et B sont retournées (flip). Dans cette opération de flipping, il ne
devrait pas avoir de case vide entre A et B. Un joueur peut placer une pièce
seulement s’il peut retourner des pièces adversaires. Sinon, il passe son tour.
Le jeu s’arrête quand aucun joueur ne peut placer une pièce. Le joueur ayant le
plus de pièces gagne le jeu.
Pour réduire la complexité, on réduit la taille de grilles à 6X6. La configuration de départ est toujours 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.
Dans ce TP, on ne tient pas
compte du nombre limité de pièces par joueur – On suppose que chaque joueur a
toujours des pièces à sa disposition.
1. On vous demande
d’utiliser l’algorithme minimax pour déterminer l’endroit où il doit poser la
pièce. Ce joueur virtuel est appelé « o2 ». Le joueur o2 peut jouer
contre l’utilisateur, identifié par « u ». Pour limiter la complexité,
cet algorithme explore l’espace d’états à une profondeur de 2 plis. Pour
évaluer la valeur heuristique (ou la chance pour le joueur o2 de gagner) pour
une position possible, on utilise le nombre de pièces supplémentaires que le
joueur o2 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], la
configuration devient la suivante :
|
|
|
|
|
|
|
|
X |
|
|
|
|
|
X |
X |
|
|
|
|
X |
O |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Le nombre de pièces noires
additionnelles qu’il obtient est donc 2.
On
vous demande d’implanter une autre heuristique pour déterminer la valeur
heuristique d’une configuration. Cette heuristique est toujours utilisée à la
profondeur de 2 plis dans l’algorithme Minimax comme dans la tâche 1. Le joueur
virtuel avec cette nouvelle heuristique est identifié par votre login. Vous
devez trouver une heuristique qui arrive à battre le joueur o2 implantée dans
la tâche 1.
Il
existe beaucoup d’heuristique possible. Vous devez en déterminer vous-mêmes. Le
site Web suivant donne une explication à une heuristique :
http://www.tjhsst.edu/~rlatimer/assignments2004/othello.html
Mais
vous pouvez en trouver d’autre sur le Web.
Un
squelette de programme (othello.pl) vous est fourni. Il contient certains
prédicats utiles, ainsi que le joueur Utilisateur (u) et un joueur hasard (r).
Le squelette contient aussi
le prédicat suivant pour lancer un jeu : jeu(Joueur1,
Joueur2). Joueur1 sera toujours attribué les pièces noirs (x), et qui commence
en premier. Par exemple, dans le squelette, vous pouvez essayer avec jeu(r,u) - le hasard joue contre l’utilisateur.
Pour uniformiser, votre
programme doit contenir les prédicats suivants
- jouer(Jeu,Joueur,Piece,Jeu1): Ce prédicat détermine la
meilleur position à jouer selon la stratégie heuristique du Joueur. Joueur peut
prendre les valeurs suivantes :
*Si
Joueur=u, c’est à l’utilisateur de jouer (il entre une position à jouer).
*Si
Joueur=r, on choisit une position possible au hasard.
Si
Joueur=o2, c’est l’algorithme Minimax que vous implantez dans la tâche 1.
Si
Joueur=<votre login>, c’est votre stratégie implantée dans la tâche 2.
Les cas marqués par * sont
déjà implantés dans un squelette fourni. Ainsi, vous devez implanter les deux
autres cas.
Avec cette uniformisation,
il est possible que vous fassiez jouer le jeu entre deux équipes : Vous
chargez les programmes de deux équipes, et vous lancez le jeu par : jeu(<login1>, <login2>).
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.
-
8 points pour le fonctionnement et la performance du
programme : 4 pour la tâche 1, et 4 pour la tâche 2.
-
2 points pour le rapport (Attention : on jugera aussi la
qualité de votre heuristique selon votre description).
Par
le programme
remise
ift3335 TP3 <votre programme>
Votre
remise du programme doit être effectuée avant 20 nov. midi.
Après cette date limite, un point (sur 10) de pénalité par jour sera appliquée.