TP3, IFT3335

Jeu d’Othello

Date de remise

À rendre avant midi le 20 novembre, 2007.

A faire en groupe de 2 personnes ou seul.

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.

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.

L’implantation

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

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.

Tâche 1 : Minimax contre l’utilisateur

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.

Tâche 2 : Utiliser une autre heuristique

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.

 

Outils fournis

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.

Forme de prédicat implanté

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>).

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.

 

-         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).

Remise

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.