Quoridor
Le jeu
de Quoridor est
un jeu de société à deux joueurs, qui se joue sur un plateau à cases
usuellement carrées séparées de chaque côté par de petites rigoles1. Un ensemble de joueurs s'affrontent de la manière suivante :
leur objectif consiste à déplacer un pion de leur couleur d'une zone
de départ à une zone d'arrivée. À chaque tour, ils peuvent choisir
soit de déplacer leur pion sur une case voisine, soit de poser un
mur dans une rigole afin de bloquer les déplacements entre deux
cases. Le vainqueur du jeu est celui réussissant à faire rejoindre
à son pion sa zone d'arrivée le premier.
Le jeu a été longuement étudié, et a fait en particulier l'objet d'un mémoire de master par L. Glendenning en 2005, qui s'est intéressée à différents algorithmes de jeu, ainsi qu'à un autre document (résultat aussi probablement d'un master) de P.M.C. Mertens en 2006. Le site QuoridorStrats propose aussi des tutoriels et des exemples de stratégies. De manière assez intéressante et non triviale, le jeu de Quoridor ne termine pas forcément pour des joueurs optimaux, et peut conduire à des situations de match nul, comme discuté dans ce forum. L'objectif de ce projet va consister à mettre en place des stratégies pour jouer aussi efficacement que possible au jeu de Quoridor et certaines de ses généralisations.
(image tirée du site jeuxdenim.be) |
Le jeu a été longuement étudié, et a fait en particulier l'objet d'un mémoire de master par L. Glendenning en 2005, qui s'est intéressée à différents algorithmes de jeu, ainsi qu'à un autre document (résultat aussi probablement d'un master) de P.M.C. Mertens en 2006. Le site QuoridorStrats propose aussi des tutoriels et des exemples de stratégies. De manière assez intéressante et non triviale, le jeu de Quoridor ne termine pas forcément pour des joueurs optimaux, et peut conduire à des situations de match nul, comme discuté dans ce forum. L'objectif de ce projet va consister à mettre en place des stratégies pour jouer aussi efficacement que possible au jeu de Quoridor et certaines de ses généralisations.
Graphes de jeu
Cette section décrit les types de données servant de briques de base
à la réalisation du sujet. Pour la suite, on supposera que les deux
joueurs sont représentés par les entiers
Les composants du graphe sont des matrices creuses définies par la GNU Scientific Library (cf. la section dédiée pour plus de détails). Le graphe contient un nombre de sommets :
Le nombre de murs donnés à chaque joueur en début de partie est le nombre d'arêtes du graphe divisé par 15, dont on prend la partie supérieure. Le jeu standard se jeu sur une grille carrée 9x9 avec 144 arêtes, ce qui donne 10 murs par joueur. Lorsqu'il s'agit de placer un mur sur le graphe, les murs ne peuvent être placés que d'une des manières suivantes :
0
(BLACK
) et 1
(WHITE
). Le
joueur débutant la partie est décidé aléatoirement. Les définitions
des coups et des graphes
utilisés devront se conformer aux
interfaces move.h
et graph.h
suivantes. Il est demandé de ne pas
modifier ces en-têtes.
Les composants du graphe sont des matrices creuses définies par la GNU Scientific Library (cf. la section dédiée pour plus de détails). Le graphe contient un nombre de sommets
num_vertices
(ou n
pour simplifier). La matrice t
est
une matrice d'adjacence de taille n*n
représentant les
arêtes du graphe-
t[i][j]
vaut0
s'il n'y a pas d'arête entre les deux sommetsi
etj
, - il vaut
1
si le sommetj
se situe au nord dei
, - il vaut
2
si le sommetj
se situe au sud dei
, - il vaut
3
si le sommetj
se situe à l'ouest dei
, - il vaut
4
si le sommetj
se situe à l'est dei
,
o
est une
matrice 2*n
codant sur chaque ligne les sommets du
graphe appartenant au joueur correspondant (donc 0
ou 1
).
L'ajout de fonctions supplémentaires à cette interface est
naturellement autorisé, bien que conseillé dans un fichier
différent.
Exemple de graphe : |
|
Les conventions pour jouer sont les
suivantes : les joueurs partent des positions leur appartenant,
et gagnent dès qu'ils atteignent une position appartenant à leur
adversaire.
Le sujet propose de travailler sur 3 graphes de formes différentes,
avec des tailles variables. Comme on assure que les graphes sont des
sous-graphes de la grille carrée, il est toujours possible
d'associer à une arête l'arête opposée lorsqu'elle existe. Le
nombre m
est spécifié sur
la
ligne de commande et permet de spécifier la largeur du graphe.
Graphe carré c |
Graphe torique t , avec m multiple de 3 |
Graphe haché h , avec m multiple de 3 |
Graphe serpent s , avec m multiple de 5 |
Le nombre de murs donnés à chaque joueur en début de partie est le nombre d'arêtes du graphe divisé par 15, dont on prend la partie supérieure. Le jeu standard se jeu sur une grille carrée 9x9 avec 144 arêtes, ce qui donne 10 murs par joueur. Lorsqu'il s'agit de placer un mur sur le graphe, les murs ne peuvent être placés que d'une des manières suivantes
- un mur peut être placé sur les deux arêtes à l'est (resp. à l'ouest) de deux sommets en relation nord-sud;
- un mur peut être placé sur les deux arêtes au nord (resp. au sud) de deux sommets en relation est-ouest.
Coups possibles
Les règles du jeu de Quoridor sont décrites de manière très imagée
dans ce
lien. Par esprit de complétude, on rappelle quelques principes
généraux qui s'appliquent pour les graphes généralisés décrits
avant.
- Pour le tout premier coup de la partie, le type
du
previous_move
est fixé àNO_TYPE
. C'est le seul coup possible ayant ce type. Un coupNO_TYPE
(ou toute autre valeur différente deMOVE
ouWALL
) envoyé en milieu de partie est une erreur. - Initialement, les joueurs disposent d'un pion et d'un
ensemble fini de murs. Le premier coup de la partie pour chaque
joueur est un
MOVE
et consiste à placer son pion sur une des cases qui lui appartiennent dans le graphe (cf. matriceo
). - A chaque tour de jeu après le premier tour, les joueurs
peuvent soit choisir de déplacer leur pion (
MOVE
), soit de placer un mur s'il leur en reste un (WALL
). - Un joueur qui choisit de se déplacer (
MOVE
) doit se déplacer sur une position adjacente dans le graphe de jeu. Il ne peut se déplacer à travers un mur. Si la position où il se déplace est occupée par un pion adverse, il peut sauter ce pion en se déplaçant deux fois dans la même direction (par exemple nord + nord). Si le second déplacement dû à un saut est impossible (pour cause de mur ou de "bord du monde", le 2nd déplacement peut être fait sur n'importe quelle arête voisine du pion adverse, sans revenir à sa position de départ. - Lors d'un
MOVE
, lestruct move_t
envoyé au serveur renseigne le champm
donnant la position d'arrivée. Le champe
est non utilisé. Les champst
etc
doivent être renseignés correctement. - Un joueur qui choisit de placer un mur (
WALL
) ne peut le faire que s'il dispose encore de murs en main. Il doit le placer sur l'une des positions valides décrites plus avant. Les murs ne peuvent pas se recouvrir. Le placement d'un mur ne peut se faire s'il empêche l'un des joueurs de rejoindre au moins une case d'arrivée valide. - Lors d'un
WALL
, lestruct move_t
envoyé au serveur renseigne (entre autres) le champe
donnant la liste des deux arêtes occupées par le mur. Le champm
est non utilisé. Les champst
etc
doivent être renseignés correctement.
Description du projet
L'objectif du projet consiste à implémenter un ensemble de fonctions
permettant de faire jouer deux joueurs à une partie
de Quoridor. Le code sera décomposé en deux
parties distinctes :
Pour les besoins du jeu, le fichier
player.h
décrit l'interface à utiliser pour
communiquer entre client et serveur.
- Un ensemble de clients implémentant tous une interface commune, gérant leur propre plateau de jeu et jouant chacun selon leur objectif propre. Ces clients sont censés être automatiques : ils doivent décider d'un coup à jouer à l'aide d'un algorithme, sans intervention extérieure.
- Un serveur de jeu organisant une partie, faisant jouer chaque client à son tour en lui envoyant les coups joués par son adversaire, enregistrant le coup du client à son tour et notifiant les clients de la fin de la partie.
|
Exemple de début de partie :
sophy->initialize(B, graph, 10) david->initialize(W, graph, 10) sophy->play(7) // return 6 david->play(6) // return 4 sophy->play(4) // ... |
#ifndef _QUOR_PLAYER_H_
#define _QUOR_PLAYER_H_
#include "move.h"
#include "graph.h"
/* Access to player informations
* RETURNS:
* - the player name as an [a-zA-Z0-9 -_]* string
*/
char const* get_player_name();
/* Player initialization
* PARAM:
* - id : the color assigned to the player
* - graph : the graph where the game is played
* - num_walls : the number of walls assigned to the player
* PRECOND:
* - `id` is either BLACK or WHITE
* - `graph` is a heap-allocated copy of the graph where the game is
* played, that must be freed in the end
* - `num_walls` is the number of edges of `graph` divided by 15,
rounded up
* - initialize has never been called before
*/
void initialize(enum color_t id, struct graph_t* graph, size_t num_walls);
/* Computes next move
* PARAM:
* - previous_move: the move from the previous player
* RETURNS:
* - the next move for the player.
*/
struct move_t play(struct move_t previous_move);
/* Announces the end of the game to the player, and cleans up the
memory he may have been using.
* POSTCOND:
* - every allocation done during the calls to initialize and play
* functions must have been freed
*/
void finalize();
#endif // _QUOR_PLAYER_H_
Il est demandé de respecter les principes suivants :
Pour les stratégies implémentables, quelques propositions :
- Les différents clients doivent
être interopérables entre équipes de
projets. A cet effet, il est demandé que chaque client soit
compilé sous la forme d'une bibliothèque partagée
(option
-shared
degcc
) et chargeable de manière dynamique, en utilisant les fonctions de la familledlopen
, définies dansdlfcn.h
. Il sera possible de s'inspirer des instructions données ici. - Il est demandé d'implémenter au moins deux clients différents en terme de stratégie utilisée.
- Il est demandé de faire attention à éviter la duplication du code (en particulier pour les données du plateau de jeu). Remarquer que l'interface interdit toute communication dudit plateau entre client et serveur pendant la partie.
- un joueur choisissant aléatoirement ses coups parmi les coups possibles;
- un joueur choisissant ses coups de façon à réduire la distance entre la position du joueur et la zone d'arrivée;
- un joueur choisissant ses coups de façon à augmenter la distance entre la position du joueur adverse et sa zone d'arrivée;
- un joueur réalisant l'une des ouvertures décrite dans la site QuoridorStrats;
- une stratégie explorant les coups possibles en créant un arbre d'exploration (cf. par exemple les algorithmes de MinMax ou de Monte-Carlo).
- une stratégie accélérant les stratégies précédentes en utilisant un algorithme d'apprentissage (en utilisant par exemple la bibliothèque FANN) 2 .
Détails techniques
Pour les besoins du projet, les fichiers devront être organisés de la
manière suivante dans le dépôt :
Le fichier
/ -- Base directory Makefile -- Global Makefile /src -- Source files /install -- Install directory (should be empty in the repository but for a .keep file)
Makefile
devra fournir :
- une règle
build
qui compilera l'ensemble du code, - une règle
test
qui compilera les tests, sans les exécuter - une règle
install
qui copiera les exécutables (un exécutable nomméserver
, un exécutablealltests
, et un nombre non spécifié de fichiers.so
) à l'intérieur du répertoire désigné, et - une règle
clean
qui supprimera les fichiers compilés et installés.
Le
Le serveur devra charger l'ensemble de ses clients de manière
dynamique en utilisant la syntaxe suivante :
Makefile
doit pouvoir prendre une
variable GSL_PATH
qui indique le répertoire où est
installée la bibliothèque libgsl.so
. Par
exemple :
GSL_PATH=/net/ens/renault/save/gsl-2.6/install make
Cette variable pourra prendre des valeurs différentes selon les
machines sur lesquelles le code sera compilé (en particulier la
forge). Il incombe à l'utilisateur du code (en particulier
à la forge) de faire que les bibliothèques soient accessibles
lors de l'exécution du programme. Par exemple :
LD_LIBRARY_PATH=/net/ens/renault/save/gsl-2.6/install/lib ./server -m 10
./install/server -m [M] -t [T] ./install/player1.so ./install/player2.so
-
L'option
-m
permet de spécifier la largeur du plateau de jeu (ex.-m 10
). -
L'option
-t
permet de spécifier la forme du plateau de jeu (grille carréec
, toriquet
, hachéeh
ou serpents
) (ex.-t h
). - Les clients sont passés en paramètre dans l'ordre 1er joueur / 2nd joueur.
- Les paramètres optionnels doivent pouvoir être placés dans n'importe quel ordre sur la ligne de commande.
alltests
doit être compilé
avec -lgcov
et exécuter tous les tests présents dans
le code. En particulier, il servira d'outil de mesure de la
couverture des tests avec gcov
.
Tout exécutable ou autre
fichier non indispensable au projet
(fichiers temporaires, fichiers objets, fichiers de logs
…) stocké à l'intérieur du dépôt verra la personne
ayant initié le premier commit se voir infliger un blâme. De la
même manière, après avoir exécuté la règle
make
install
, le répertoire install
doit
contenir exactement deux (2) exécutables
nommés server
et alltests
, et des
clients sous la forme de bibliothèques partagées
(fichiers .so
). GSL
La GNU Scientific
Library est une bibliothèque C et C++ permettant de faire des
calculs numériques. Dans le cadre de ce sujet, elle fournit des
implémentations de matrices denses et creuses, ainsi que des
algorithmes de résolution de systèmes linéaires. Malheureusement,
elle ne fournit pas d'algorithmes de
graphes, ce qui laisse toute latitude pour les implémenter.
- Lien vers la documentation;
- Documentation des matrices dans GSL;
- Documentation des matrices creuses dans GSL.
Contact
Pour toute information complémentaire, contacter : David RENAULT.
1. | Oui, des rigoles, la langue française est un bonheur renouvelé à chaque seconde. Des goulottes si vous préférez. Avouez que vous ne lisez ces sujets que pour les notes de base de page. |
2. | Une telle stratégie a besoin d'une fonction d'évaluation un peu sérieuse, et donc ne pourra être envisagée qu'après avoir implémenté certaines des stratégies précédentes. |